Comments 15
В этом алгоритме получается после фазы разбиения запустить сортировки подчастей параллельно.
Не очень удачное решение с точки зрения параллельности. Мне кажется, более thread-friendly было бы разбить массив на N одинаковых частей и запустить для каждой части quicksort в своем потоке.
Но ведь потом придется сливать куски в один, а это уже только в один поток.
Ну а у вас в самом-самом начале std::partition весь массив жуёт тоже в один поток.
Не так уж это и долго, особенно если составить хороший алгоритм для слияния.
Научите сливать K кусков суммарного размера N быстрее чем за O(NK)?
И, конечно, без использования разного рода логарифмических структур данных, типа сетов, мапов и прочего. При маленьких K они сильно затормозят финальную стадию процесса.
А разве нельзя рекурсивно посливать по два в сумме за O(N log(K))?
Для слияния O(N log K) наилучшая асимптотика. Правда там константа очень маленькая, и можно реализовать не-рекурсивную версию, будет ещё быстрее.
Но можно подойти с другой стороны, и перед сортировкой обработать массив неким подобием quicksort, который не сортирует, а просто разбивает массив на K частей (при этом K — степень двойки) таким образом, что каждый элемент 1-ой части меньше любого элемента 2-ой части и т.д. Т.е. после сортировки в K потоков мы получаем уже окончательный массив.
Но можно подойти с другой стороны, и перед сортировкой обработать массив неким подобием quicksort, который не сортирует, а просто разбивает массив на K частей (при этом K — степень двойки) таким образом, что каждый элемент 1-ой части меньше любого элемента 2-ой части и т.д. Т.е. после сортировки в K потоков мы получаем уже окончательный массив.
Это уже не совсем quicksort будет.
Интересно, а если предположить что процессоров бесконечное количество, хотя бы сравнимо с log(N)… реально ли будет добиться O(N log K)? или даже O(N)?
Много ядер уже сейчас можно найти в GPU (там только куча ограничений для эффективного доступа к оперативке), в будущем, я думаю, ситуация с многопроцессорными сопроцессорами будет только улучшаться.
Много ядер уже сейчас можно найти в GPU (там только куча ограничений для эффективного доступа к оперативке), в будущем, я думаю, ситуация с многопроцессорными сопроцессорами будет только улучшаться.
А брать-то надо не среднее время выполнения, а наименьшее. Результаты выше минимального просто больше «пострадали» от отсутствия данных в кеше CPU, переключения процессов и др.
Не совсем понял как работает такая многопоточность. Task Manager показывает сначала 8 потоков, а потом на 3-ем или 4ом проходе количество потоков на приложении увеличивается до 13ти.
По идее, если ограничить число потоков по количеству ядер, то будет меньше переключений, лучше доступ к памяти и т.п. Интересно было бы проверить, будет ли быстрее.
ЗЫ в инклюде присутствует future и chrono, это буст приходит в студию, или это уже входит стандарт c++11?
По идее, если ограничить число потоков по количеству ядер, то будет меньше переключений, лучше доступ к памяти и т.п. Интересно было бы проверить, будет ли быстрее.
ЗЫ в инклюде присутствует future и chrono, это буст приходит в студию, или это уже входит стандарт c++11?
Sign up to leave a comment.
Многопоточный QuickSort на С++ 2011