Комментарии 19
У графиков подписи одинаковые и вывод отличается от максимальной цифры в табличке :)
а std::sort(std::execution::par_unseq,....) за сколько посчитает?
у меня получается, что std:sort with par_unseq быстрее примерно в два раза.
divideand... не может на 100% нагрузить cpu, а std::sort может
Время выполнения (divide): 2246 миллисекунд, для размера 10000000
Время выполнения (std_sort, par_unseq): 1130 миллисекунд, для размера 10000000
Время выполнения (divide): 4575 миллисекунд, для размера 20000000
Время выполнения (std_sort, par_unseq): 2350 миллисекунд, для размера 20000000
Время выполнения (divide): 6874 миллисекунд, для размера 30000000
Время выполнения (std_sort, par_unseq): 3544 миллисекунд, для размера 30000000
Время выполнения (divide): 9172 миллисекунд, для размера 40000000
Время выполнения (std_sort, par_unseq): 4878 миллисекунд, для размера 40000000
Время выполнения (divide): 11478 миллисекунд, для размера 50000000
Время выполнения (std_sort, par_unseq): 6222 миллисекунд, для размера 50000000
Ну так всегда лучше использовать стандартные алгоритмы. Тут человек явно для примера всё пишет.
Не ставил себе такую задачу. Чтобы посчитать par_unseq надо С++ 17 стандарт врублять и новую библиотеку подключать.
Пересказ статьи MapReduce?
С учётом того, как у вас в конце отсортированные массивчики объединяются в один большой массив за... наверно, n log n проходов, пожалуй было бы эффективнее первым действием разбить массив на куски, примерно как первый шаг быстрой сортировки, только не на 2, а наnumThreads частей - потом не пришлось бы сливать. То есть, если у вас массив содержит числа от 0 до 100, то при numThreads == 4первым шагом вы делите его на 4 куска (скажем, 0-20, 21-60, 61-77, 78-99), а потом быстро-сортируете уже эти куски.
А может и не было бы быстрее, надо тестировать.
Ну и да, как бы ни было заманчиво ускорение от потоков, настоящий прирост оно даст или при огромных массивах (обычно массивы сильно короче десятков миллионов (но, конечно, зависит от предметной области), так что расходы на запуск тредов всю выгоду съедят), либо при наличии пула этих самых тредов, чтоб создать 1 раз, а затем переиспользовать.
за... наверно, n log n проходов
не, каждый цикл for - один проход по всему целому массиву, step изначально равен размеру чанка, после каждого цикла удваивается, так что должен быть n log k, где k - количество потоков.
Непонятно другое - зачем было городить огород со своей реализацией квиксорта, можно было-бы взять что-нибудь типа std::sort и на нем уже показывать преимущества параллельности. Былобы более наглядно, тем более, как тут уже подсказали, у него есть опции для параллельной сортировки, можно было тогда заодно сравнить и с ними, да еще и показать чем они отличаются и почему их больше одной. Раз уж писать про параллельные сортировки.
Ну и где же тут быстрая сортировка? Когда у вас в листингах сортировка слиянием используется… Да ещё и на первом и втором этапах листинг один и тот же. Хотя нет, разные, строчка с вызовом сортировки отличается — на первом этапе std::inplace_merge, а на втором — (самописная?) merge
Не понимаю, почему всем так и хочется, чтобы написанные алгоритмы были быстрее дефолтных, а как же фундаментальные исследования.
Для "фундаментальности" этого исследования не хватает анализа области применимости и ответов на смежные вопросы.
Какого размера массивы обычно сортируются (5, 50, 10 000, 10 000 000 000 элементов?) и начиная с какого количества элементов распараллеленный алгоритм начинает выигрывать у обычного?
Как эта величина зависит от количества потоков?
Не буду же я запускать 16 потоков, чтоб отсортировать вектор на 50 элементов, верно?
Как изменится время работы, если вместо int у нас будут структуры с несколькими полями (хотя бы типичное фамилия-имя-отчество-год рождения), и для сравнения будет применяться не просто арифметическое сравнение, а функция (перегруженный оператор или лямбда)? Скорее всего лишь пропорционально замедлится, но вдруг нет?
Как "ускорение" отличается на Windows и Linux, у них ведь потоки сильно по-разному работают.
Почему для 70М элементов ускорение получилось больше, чем для 100М (4,11 против 4,00)?
Ну и в чистом виде быстрая сортировка в C++ не используется, std::sort (по крайней мере в GCC) внутри себя использует introsort - потому что уже в С++11 есть требование заканчивать сортировку за не более чем O(n log n) операций, а быстрая сортировка может скатиться до O(n^2). Поэтому, кстати, std::sort обычно заметно быстрее qsort (можете сами протестировать).
То есть как демонстрация того, что в каких-то отдельных случаях многопоточность помогает - хорошо, наглядно. Но назвать это исследованием я не решусь.
“VectorType pivot = arr[high]; // Выбираем последний элемент в качестве опорного”
A почему не arr[high-1] ?
Спасибо за статью! Понимаю, что статья - для новичков. Но, говоря про подводные камни распараллеливания, хотелось бы, чтобы тема так же была рассмотрена с точки зрения инвалидации хешей, false cache sharing, и как с этим бороться.
Параллельный метод сортировки массива std::thread