[Из песочницы] Сортировка: определяем лучший алгоритм
Как нетрудно догадаться, я знаю ответ на этот вопрос, но, поскольку моя статья с описанием алгоритма сортировки «воронкой» была здесь встречена, мягко говоря, нервозно, я решил провести-таки тестирование «по образу и подобию» тех, которые обычно проводятся — в основном, конечно, по материалам статей, представленных здесь же, на Хабре.
В Интернете не представлены трудные массивы для алгоритмов сортировки (мне, во всяком случае, их найти не удалось), а многочисленные «сравнительные анализы» алгоритмов на массивах в несколько сотен или тысяч элементов, просто смешны, а потому я решил прогнать «воронкой» те массивы, на которых проводились исследования с количеством элементов, по крайней мере, 10^5 и более.
Сначала небольшой обзор того, что пишут про алгоритмы сортировки с моими комментариями:
На собеседованиях часто спрашивают, какая сортировка самая быстрая. Вопрос с подвохом. В ответ вы должны спросить: «А для какого случая выбирается оптимальная по времени сортировка?» И лишь тогда, когда будут озвучены условия, можно смело перебирать имеющиеся варианты.
Моя версия очевидна: алгоритм «воронки» идеален для любых «условий», озвучивать которые совершенно не обязательно.
Подумайте, как будут вести себя эти и другие алгоритмы сортировки для таких случаев входных данных (иногда вырожденных) как:
1. уже отсортированный массив;
2. отсортированный в обратном порядке массив;
3. частично упорядоченный массив;
4. массив с повторяющимися элементами;
5. массив, все значения которого одинаковы.
Первый, второй и пятый случай, очевидно, имеют линейную сложность, два других зависят от того, насколько «частично упорядочен массив» и сколько там «повторяющихся элементов». Чем больше, тем быстрее пойдёт сортировка! Впрочем, у «воронки» нет «трудных» входных данных!
Основную цель конструирования новых алгоритмов можно определить следующим образом: уменьшение общего времени сортировки массива.
Именно! А не минимизация этого несчастного «количества сравнений»!
В качестве тестовых данных используются различные массивы целых четырехбайтовых чисел:
— псевдослучайные неупорядоченные числа;
— числа, расположенные по не возрастанию;
— числа, расположенные по не убыванию.
Два последних варианта, очевидно, линейные. Сортировка интов, очевидно, куда проще сортировки строк. Ну, так и быть: если попадутся тестовые массивы для интов, доработаю чуток алгоритмы чтения, записи и сравнения элементов.
Как показывает практика, между числом операций и временем выполнения программы не всегда есть линейная зависимость. Как показано далее, подобная ситуация складывается при оценке времени сортировки больших объёмов данных. Выяснение причин такого явления выходит за рамки рассматриваемых вопросов, однако его наличие — факт установленный и с ним следует считаться при построении эффективных последовательных и параллельных алгоритмов.
Аксиома! О чём я и писал в своей заметке и многочисленных комментариях к ней.
Использование стандартной процедуры «быстрой сортировки» qsort нецелесообразно по следующим причинам:
— алгоритм в наихудшем случае требуется порядка O (n^2) операций, что не позволяет выполнять сортировку произвольных массивов сколько-нибудь значительного размера за приемлемое время;
— время выполнения сортировки с помощью процедуры qsort больше, чем время работы других рассматриваемых алгоритмов, даже в среднем случае. Вероятно, это является платой за универсальность интерфейса (процедура qsort позволяет обрабатывать данные любого типа) и происходит за счет неэффективного доступа к элементам сортируемого массива.
Даже так? Как я уже писал, лично мне достаточно и первого пункта.
Непосредственное использование рекурсии в алгоритме сортировки слиянием требует значительных накладных расходов. Главным образом, они вызваны необходимостью применения дополнительных массивов при слиянии упорядоченных фрагментов.
Так уберите рекурсию! Как я уже писал, нормальные люди просто начинают сливать массивы, начиная с единичных элементов! И не нужно будет «на каждом шаге выполнить копирование результата, что значительно замедляет обработку».
При четырех процессорах, даже имеющих доступ к общей памяти (в этом случае затраты на передачу массивов от процессора к процессору можно считать равными нулю), ускорение не превысит 3.5. При использовании 32 процессоров на общей памяти ускорение не превысит 10.
Ну так и не мучайтесь! И одного процессора вполне достаточно! Алгоритм ведь достаточно быстрый — чай, не задача коммивояжёра! Тем более, что «заключительное слияние двух половин всего массива выполняется на одном процессоре».
Массив из 100 миллионов четырехбайтовых чисел отсортирован на 640 процессорах за 1.21 сек. Одному процессору этой системы для сортировки того же массива требуется 83.51сек.
Я и говорю: не мучайтесь! Займите лучше процессоры каким-нибудь другим полезным делом!
Теперь посмотрим на две статьи Хабра.
Первая статья: habr.com/ru/post/133996
Сравнивать я, разумеется, ничто ни с чем не собираюсь — просто прогоню «воронкой» те же массивы, если это окажется возможным.
Каждый алгоритм запускался на одних и тех же данных по три раза, брался в расчет лучший результат (чтобы кратковременные нагрузки системы не повлияли на наш честнейший эксперимент). Железо: ноутбук HP dv3510er, Intel Core 2 Duo 2Ггц, 2Гб RAM. ОС: Ubuntu 11.10
Ну, три так три. Железо у меня примерно такое -же (чуток получше): двухъядерник 2.8ГГц, 2Гб RAM. ОС WinXP.
Эксперимент 1: Работа на обычных данных
Было сгенерировано 10 наборов по 10^8 случайных натуральных чисел, для каждого алгоритма было замерено среднее время работы.
Ну, 10 так 10… что тут у нас… rand от WATCOM генерит инты в диапазоне 32К? Как-то маловато будет. Ладно, запишем дважды — в младшие и в старшие байты инта по рандому. Ну и, до кучи, объединим все 10 массивов в один — получим ещё данные и для массива в 10^9 элементов.
Эксперимент 2: Независимые отсортированные группы равного размера
Дано 10^8 различных натуральных чисел, отсортированных по возрастанию. Группируем их по k последовательных элементов и переставляем все группы в обратном порядке.
Господи, чего только ни придумают! :) Ну, для k=10^8, как я понимаю, это и будет тот самый «отсортированный массив». Для для k=10^0 — он же, но отсортированный в обратном порядке. А для остальных, соответственно… ну, вроде как сгенерил. Эти массивы мы тоже сольём в один — элементов там будет на 100 миллионов меньше, чем в первом «обобщённом» тесте.
Эксперимент 3: Отсортированные группы разных размеров, ограниченный диапазон значений
Дано 10^8 целых чисел из ограниченного диапазона (в нашем случае [0: 100000]) и они упорядочены группами произвольного размера от 1 до k.
Ну, и как это прикажете понимать? Я вот ВООБЩЕ не понял алгоритма генерации! Ладно, этот тест пропускаем.
Эксперимент 4: Произвольные перестановки
Сгенерируем частично упорядоченные данные другим способом: возьмем 10^8 произвольных натуральных чисел, отсортируем их и сделаем k произвольных перестановок двух элементов местами.
Этот тоже пропускаем — это вообще не тест: вначале идёт чисто отсортированный массив с ничножным количеством искажений, а в конце просто случайный массив. Ну да, так и есть: все алгоритмы выстроились в той же последовательности, что и в первом тесте, и даже время у них практически совпадает!
Вторая статья: habr.com/ru/post/335920
Описания алгоритмов, описания… описания… описания…, а тесты-то где? Ага, вот они: Железо и система: Процессор: Intel Core i7–3770 CPU 3.40 GHz ОЗУ: 8 ГБ
Здесь железо чуть получше моего, но неважно.
Все тесты поделены на четыре группы. Первая группа — массив случайных чисел по разным модулям (10, 1000, 10^5, 10^7 и 10^9). Вторая группа — массив, разбивающийся на несколько отсортированных подмассивов. Фактически брался массив случайных чисел по модулю 10^9, а далее отсортировывались подмассивы размера, равного минимуму из длины оставшегося суффикса и случайного числа по модулю некоторой константы. Последовательность констант — 10, 100, 1000 и т.д. вплоть до размера массива. Третья группа — изначально отсортированный массив случайных чисел с некоторым числом «свопов» — перестановок двух случайных элементов. Последовательность количеств свопов такая же, как и в предыдущей группе. Наконец, последняя группа состоит из нескольких тестов с полностью отсортированным массивом (в прямом и обратном порядке), нескольких тестов с исходным массивом натуральных чисел от 1 до n, в котором несколько чисел заменены на случайное, и тестов с большим количеством повторений одного элемента (10%, 25%, 50%, 75% и 90%).
А здесь, собственно, и проверять нечего! Либо то, что уже было, либо ещё более привлекательное для воронки «большое количество повторений». Ну, и что тут гонять «по 20 запусков»? В общем, даю результаты по тестам из первой статьи:
Тесты первой группы:
0: N=2602009514 T=195 sec
1: N=2602148436 T=193 sec
2: N=2601943056 T=191 sec
3: N=2602055129 T=194 sec
4: N=2601888286 T=195 sec
5: N=2602105643 T=191 sec
6: N=2601928733 T=191 sec
7: N=2601947256 T=196 sec
8: N=2601891575 T=193 sec
9: N=2602105643 T=196 sec
0–9: N=29495155841 T=3210 sec (8 tmp-файлов)
Как-то очень уж ровненько и по времени, и по числу сравнений.
Тесты второй группы:
0: N=199999998 T=18 sec
1: N=1923669691 T=57 sec
2: N=1683854900 T=46 sec
3: N=1480233649 T=42 sec
4: N=1249780062 T=39 sec
5: N=996602000 T=33 sec
6: N=666000198 T=26 sec
7: N=340000016 T=21 sec
8: N=99999999 T=16 sec
0–8: N=11462881951 T=968 sec (7 tmp-файлов)
Во всех случаях время приведено «грязное», то есть туда входит время загрузки исходного массива в ОЗУ, собственно сортировка и время записи результатов в файл (для крупных массивов ещё и время слияния временных файлов). Результаты говорят сами за себя (причём во время сортировки «миллиардера» я и написал эту заметку). Программа сортировки практически та же, что и для сортировки строк: чтение и запись элементов производится побайтно (просто длина строки всегда 4 байта), и только в процедуре сравнения элементов сравниваются не строки, а инты (как UI32). Так что выбрасывайте, господа, все алгоритмы на помойку — алгоритм сортировки «воронкой» ИДЕАЛЕН! :)
