Какой алгоритм сортировки является лучшим для многопоточного программирования?

Question

Я хочу отсортировать массив целых чисел длиной от 1.000.000 до 100.000.000. Я хочу запустить эту программу на компьютере core2duo с 2 Мб кеша, используя библиотеку pthread. Я хочу самый быстрый алгоритм!

Я написал полупараллельный код сортировки, который использует алгоритм сортировки слиянием. Но это не достаточно быстро!

          ___ sort___   
         /           \        
        /____ sort ___\     __ merge __
    ___/               \___/           \___ merge 
       \ ____ sort ____/   \__ merge __/    
        \             /      
         \___ sort __/      

Answer 1

Прошло много времени с тех пор, как я учился в университете, но я помню, что PSRS алгоритм был хорош для такого рода вещей. Я уверен, что Google покажет множество реализаций / псевдокода.

Answer 2

Поскольку вы используете core2duo, я бы посмотрел алгоритм параллельной быстрой сортировки. Он сортирует на месте, экономит память и может достигать прироста производительности, пропорционального количеству процессоров, вплоть до небольшого числа процессоров.

Алгоритм параллельной быстрой сортировки в основном выполняет шаг разбиения, а затем выполняет быструю сортировку в левом и правом подсписках в отдельных процессах. Это может быть достигнуто путем сохранения границ в общем стеке, который в конечном итоге становится предметом спора при запуске с большим числом потоков.

Существуют и другие алгоритмы, такие как PSRS, которые масштабируются до большего числа процессоров, но, поскольку вы работаете с core2duo, который, вероятно, позволит максимально использовать 2 настоящих ядра + два гиперпоточных ядра, дополнительная память, необходимая для PSRS, будет вероятно, это пустая трата времени. Учитывая количество элементов, которые вы хотите отсортировать, вам, вероятно, потребуется сохранить память.

Я реализовал оба в Java на Github. Дайте мне знать, если вы хотите посмотреть на код как на руководство по реализации чего-либо с помощью pthreads.

Answer 3

Быстрая сортировка прекрасно подходит для многопоточности.

При разбиении одна сторона раздела сортируется в текущем потоке, а другая - в новом.