Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Системное программирование и WinAPI > Сортировка, многоядерный процессор

Автор: User008 28.1.2010, 07:24

Как наиболее быстро отсортировать массив с многоядерным процессором?

Автор: comcon1 28.1.2010, 08:17

изучайте:
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm

З.Ы. "кто быстрее" этот как "чья девка красивее"

Автор: User008 28.1.2010, 13:58

Хотелось бы увидеть пример сортировки для многоядерного процессора.
Я вот думаю используя быструю сортировку, получить количество ядер, и создавать поток, если есть свободные ядра. Может есть более удобный способ?

Автор: xvr 28.1.2010, 14:31

Цитата(User008 @ 28.1.2010, 13:58)

Я вот думаю используя быструю сортировку, получить количество ядер, и создавать поток, если есть свободные ядра. Может есть более удобный способ?

Есть. Использовать компиляторы с поддержкой OpenMP. И прописать соотвествующие прагмы в соотвествующие места

Автор: comcon1 28.1.2010, 15:15

Ты хочешь изобретать велосипед или хочешь сортировать?

Автор: User008 28.1.2010, 19:45

Хочу посмотреть пример

Автор: comcon1 29.1.2010, 12:39

Блин, за вас за всех надо гуглить?
http://www.dreamincode.net/forums/showtopic84296.htm

Автор: User008 31.1.2010, 08:21

Код


void sort(unsigned int *beg, unsigned int *end)
{
    unsigned  x = beg[(end-beg)/2];
    unsigned *p = beg, *q = end;

    do { 
        while (*p < x) ++p; 
        while (*q > x) --q;
        if (p <= q)
        {
            std::iter_swap(p, q);
            ++p; --q;
        }
    } while (p <= q);

    #pragma omp parallel sections
    {
        #pragma omp section
        if (beg < q) sort(beg, q);

        #pragma omp section
        if (p < end) sort(p, end);
    }
}

Сделал так, но сортироваться стало намного дольше

Автор: xvr 31.1.2010, 12:18

Цитата

Сделал так, но сортироваться стало намного дольше

Параллелить нужно цикл, а не рекурсивные вызовы процедур. QSort в чистом виде не очень удобен для распараллеливания.
Лучше порезать массив на части, в каждой из них сделать (в параллель) QSort, а затем сделать слияние результатов.