И снова про сортировки: выбираем лучший алгоритм

Недавно на хабре в очередной подняли тему алгоритмов сортировки, а именно был хорошо описан метод Timsort.

Он, имея сложность не более O(n log n), ускоряется в случае сортировки частично упорядоченных данных и имеет сложность O(n), если данные изначально отсортированны. Но это не единственный алгоритм с такими заявленными свойствами. Существует еще как минимум два более-менее известных метода с похожей сложностью — это Smoothsort и сортировка Шелла.

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


Обычно реальное время работы разных алгоритмов с одинаковой сложностью на одинаковых данных может отличаться в несколько раз. Давайте вспомним, почему так получается и спросим у википедии что значит фраза «алгоритм имеет сложность O(n log n)»

Сложность алгоритма O(n log n) означает, что при больших n время работы алгоритма (или общее количество операций) не более чем C · n log n, где C — некая положительная константа.

И вот этот коэффициент C и влияет на реальное время работы агоритма. Чем сложнее алгоритм, чем более продвинутые структуры данных используются в нем, тем большее количество операций необходимо выполнить при исполнении программы для поддержки всех нужных переменных и структур. То есть больше коэффициент C и реальное время работы. Конечно, еще этот коэффициент зависит от конкретной реализации, но, если уделять внимание коду, который вы пишите, и знать особенности языка разработки, основной вклад в эту константу будет вносить именно алгоритм.

Поэтому было интересно посмотреть какой реальный выигрыш в производительности дает каждый из указанных алгоритмов в случае частично упорядоченных данных, и насколько этот выигрыш, если он есть, существенен. Для этого было проведено несколько экспериментов. Но для начала я хочу, не вдаваясь в подробности, напомнить как работают вышеназванные алгоритмы. Если кому не интересно, прошу сразу к сравнению.

Сравниваемые алгоритмы


Timsort


Хорошее описание здесь, просто процитирую основную идею:
  1. Специальный алгоритм разделяет входной массив на подмассивы
  2. Каждый подмассив сортируется обычной сортировкой вставками
  3. Отсортированные подмассивы собираются в единый массив с помощью модифицированной сортировки слиянием

Сложность в лучшем случае (входные данные отсортированы в любом порядке, может даже и обратном требуему) составляет O(n), а в общем не хуже O(n log n).
Требуется O(n) дополнительной памяти.

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

Smoothsort


Был изобретен небезызвестным Э. В. Дейкстрой в 1981 году и является развитием идеи Heapsort — сортировки с помощью двоичной кучи (ну или пирамиды, кому как больше нравится).

Для начала напомню, как работает Heapsort:
  1. Построить кучу, добавляя в нее по одному элементу (сложность O(log n) на каждый, всего O(n log n))
  2. Извлекать максимальный элемент, который лежит в корне построенной кучи, до тех пор, пока она не станет пуста. Так как при удалении корня куча распадается на две независимых, требуется собрать их в одну за O(log n). В сумме для n элементов — также O(n log n)

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

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

Числа Леонардо определяются рекуррентно следующим образом:
L(0) = 1, L(1) = 1, L(i) = L(i - 2) + L(i - 1) + 1
Вот первые несколько членов этой последовательности:
1, 3, 5, 9, 15, 25, 41, ...

k-ая куча Леонардо — это двоичное дерево с количеством вершин L(k), удовлетворяющее следующим условиям:
  1. Число, записанное в корне не меньше чисел в поддеревьях (потому и куча)
  2. Левым поддеревом является (k-1)-я куча Леонардо
  3. Правым — (k-2)-я

Кучи должны быть упорядочены по размеру (самая большая — слева), а значения их корней должны неубывать слева направо, откуда следует что максимальным элементом структуры всегда будет являться корень самой правой кучи. Структура хранится в исходном массиве, размер дополнительной памяти — O(1).

Любое натуральное число можно разложить в сумму чисел Леонардо, а это значит что вышеописанную структуру можно построить для любого количества чисел.


Пример структуры из куч Леонардо для 13 элементов. Используются три кучи: 4-я, 2-я и 1-я.

Для добавления элемента в такую структуру требуется перестроить некоторые из куч, чтобы сумма их размеров стала равна новому количеству элементов, а также проследить за тем, чтобы корни куч остались упорядочены по возрастанию. Такая операция имеет сложность не более O(log n).


При добавлении элемента требуется перестроить кучи (Свойство 1 куч Леонардо на картинке не восстановлено)

Извлечение же максимума похоже на добавление элемента и также имеет сложность не более O(log n).

Сам алгоритм сортировки Smoothsort работает в два этапа, как и Heapsort:
  1. Добавляя по одному, строится множество куч Леонардо для всех элементов (не более O(log n) на каждый)
  2. По очереди извлекаются максимальные элементы из построенной структуры (максимумом всегда будет корень самой правой кучи) и структура восстанавливается необходимым образом (не более O(log n) на каждый элемент)

Преимуществом использования такой структуры является то, что в случае уже отсортированной входной последовательности, операции построения куч и извлечения всех элементов будут иметь суммарную сложность O(n). И утверждается, что при уменьшении степени упорядоченности данных, которые следует отсортировать, сложность будет плавно(smoothly) возрастать от O(n) до O(n log n). Отсюда и название — Smoothsort.

Вообще, алгоритм далеко нетривиален, а в добавок не очень понятно описан. Материалы:
Статья на википедии
Оригинальная статья — непонятная, надо долго разбираться
Оригинальная статья, откомментированная Hartwig Thomas — тоже самое, но нормальный шрифт + поясняющие комментарии. Но легче все равно не становится :)
Исследование алгоритма от K. Schwarz — уже понятнее, но некоторые существенные оптимизации не описаны вообще. Иллюстрации вставлены оттуда.

Shellsort (Сортировка Шелла)


Сортировка Шелла — это надстройка над сортировкой вставками; вместо одного прохода мы делаем несколько, причем на i-ом проходе мы сортируем подмассивы из элементов, стоящих друг от друга на расстоянии di.

При этом на последнем проходе di должно быть равно 1 (то есть последний шаг — это обычная сортировка вставками), это гарантирует корректность алгоритма.

Для примера: пусть необходимо отсортировать массив из 12 элементов, количество проходов равно 3, d1 = 5, d2 = 3, d3 = 1
На первом шаге будут сортироваться следующие массивы:
(a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10)

На втором:
(a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12)

А на третьем массив (a1,..., a12) целиком

Преимущество над обычной сортировкой вставками заключается в том, что на первых проходах элементы массива перемещаются шагами не по 1, а по di, а к последнему проходу уже достигнута некая локальность (элементы находятся близко к своим итоговым местам), поэтому не приходится производить большое количество обменов.

Сложность алгоритма зависит от выбора количества проходов и значений di, и может сильно варьироваться; в википедии есть специальная таблица. Для тестирования я выбрал вариант, описанный здесь, в худшем случае его сложность составляет O(n4/3), а в среднем O(n7/6).

Если данные изначально отсортированы в нужном порядке, то не будет произведено ни одного обмена, все проходы пройдут «в холостую». Потому сложность в таком случае зависит лишь от количества проходов. Если же их количество фиксировано, то это будет просто O(n).

Требуется O(1) дополнительной памяти.

Почитать подробнее можно здесь, тут и вот тут.

Сравнение


Собственно, вот и самая интересная часть — протестировать все вышеупомянутые методы на разных данных и сравнить их реальное время работы.

В тестировании приняли участие следующие реализации, весь код написан на чистом Си:
  • TimSort — реализация David R. Maclver, написанная для его статьи о TimSort — Хорошая, оптимизированная реализация
  • SmoothSort — одна из моих реализаций, самая быстрая что мне удалось написать
    Вообще, написать этот алгоритм более-менее эффективно не очень просто. Вероятно можно написать и быстрее, и оптимальнее, но после четырех попыток я решил не продолжать :)
  • ShellSort — реализация, написанная по мотивам примера отсюда
  • Также в сравнение были добавлены обычные рекурсивные реализации quicksort и heapsort для того, чтобы можно было оценить преимущества рассматриваемых методов над традиционными

Параметры тестирования


Замерялось только время срабатывания алгоритма сортировки (в секундах), время генерации тестовых данных не учитывалось. Каждый алгоритм запускался на одних и тех же данных по три раза, брался в расчет лучший результат (чтобы кратковременные нагрузки системы не повлияли на наш честнейший эксперимент :) )

Железо: ноутбук HP dv3510er, Intel Core 2 Duo 2Ггц, 2Гб RAM.
ОС: Ubuntu 11.10

Проведено четыре эксперимента на разных данных:

Эксперимент 1: Работа на обычных данных


Задачей этого экспериментая является сравнение быстродействия алгоритмов на произвольных, никак не упорядоченных данных. Было сгенерировано 10 наборов по 108 случайных натуральных чисел, для каждого алгоритма было замерено среднее время работы.

Сложность всех тестируемых алгоритмов в случае произвольных данных равна (кроме ShellSort) O(n log n). Собственно, здесь можно проследить влияние той самой константы C.



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

Эксперимент 2: Независимые отсортированные группы равного размера


Дано 108 различных натуральных чисел, отсортированных по возрастанию. Группируем их по k последовательных элементов и переставляем все группы в обратном порядке.
Пример для десяти чисел: 1 2 3 4 5 6 7 8 9 10
k = 1: 10 9 8 7 6 5 4 3 2 1
k = 3: 8 9 10 5 6 7 2 3 4 1
k = 5: 6 7 8 9 10 1 2 3 4 5
k = 10: 1 2 3 4 5 6 7 8 9 10

Группы «независимы» друг от друга в том смысле, что они не пересекается по диапазону хранимых в них значений. То есть элементы любой группы больше элементов всех групп, стоящих правее, а также меньше тех, что стоят левее.

Замеры производились для всех k, равных степеням 10.



Можно заметить следующие закономерности:
  • Quicksort и Heapsort тоже любят, когда данные частично отсортированы (сравните оба графика). На асимптотическую сложность это не влияет, но скорость работы все равно возрастает в разы
  • Timsort'у все равно, в каком порядке отсортированы данные, в обоих случаях он работает очень быстро
  • Smoothsort имеет свое понимание частичной упорядоченности данных. Реальный прирост производительности в этом тесте заметен лишь при полностью отсортированных данных. Даже в том случае, когда массив представляет из себя небольшое количество полностью отсортированных кусков, для того чтобы переставить их местами, алгоритму требуется произвести огромное количество операций со кучами Леонардо, которые довольно «тяжелые»
  • Shellsort, несмотря на большую сложность (при n = 108 n7/6 > n log n), часто работает за меньшее время, чем Smoothsort. Это связано с относительной простотой алгоритма. Но при полностью отсортированных данных, Shellsort все равно вынужден сделать все проходы, пусть даже и не переставляя ни одного элемента. Поэтому при k = 108 результат почти самый худший из рассматриваемых алгоритмов

Эксперимент 3: Отсортированные группы разных размеров, ограниченный диапазон значений


Дано 108 целых чисел из ограниченного дипазона (в нашем случае [0… 100000]) и они упорядочены группами произвольного размера от 1 до k.

Такой набор данных уже как-то соответствует данным из реальных задач, мне пришлось столкнуться с таковыми для подсчета коэффициентов близости Дайса



В этом примере Smoothsort снова показал себя с не самой лучшей стороны, он работает дольше чем Heapsort, а ведет себя так же. Timsort снова впереди.

Эксперимент 4: Произвольные перестановки


Сгенерируем частично упорядоченные данные другим способом: возьмем 108 произвольных натуральных чисел, отсортируем их и сделаем k произвольных перестановок двух элементов местами.



А этот эксперимент наконец-то позволяет Smoothsort'у «раскрыться»: становится заметным ускорение при увеличении степени отсортированности входных данных. Это связано с тем, что, в отличие от предыдущих экпериментов, здесь алгоритм «двигает» по кучам Леонардо лишь не очень большое фиксированное количество элементов, что не влечет за собой большого количества операций по перемещению элементов внутри куч. Но после определенного момента он снова становится слишком «долгим».

Итоги


Как можно было убедиться, практическая польза от описанных алгоритмов есть, со своей задачей они с переменным успехом справляются. Абсолютным лидером стал Timsort — дающий заметное ускорение при увеличении степени упорядоченности данных и работающий на уровне Quicksort в обычных случах. Не зря он признан и встроен в Python, OpenJDK и Android JDK.

Про Smoothsort в сети довольно немного информации (по сравнению с остальными алгоритмами) и не спроста: из-за сложности идеи и спорной производительности он скорее является алгоритмическим изыском, нежели применимым методом. Я нашел всего лишь одно реальное применение этого алгоритма — в библиотеке sofia-sip, предназначенной для построения IM- и VoIP-приложений.

Появление Shellsort в данном тесте является довольно спорным моментом, потому что его асимптотическая сложность несколько больше, чем у остальных двух алгоритмов. Но у него есть два больших преимущества: простота идеи и алгоритма, которая позволяет почти всегда обходить Smoothsort по скорости работы и простота реализации — работающий код занимает всего пару десятков строк, в то время как хорошие реализации Timsort и Smoothsort требуют более сотни строк.

Хочу заметить, что я сравнивал именно производительность, и специально не заострял внимание на других параметрах (вроде использования дополнительной памяти).

Мой субъективный вывод — если нужен очень хороший алгоритм сортировки для встраивания в библиотеку или в большой проект то лучше всего подойдет Timsort. В случае же небольших задач, где нет времени и необходимости писать сложные алгоритмы, а результат нужен быстро — то вполне можно обойтись и Quicksort'ом — так как он дает лучшую из простых в написании алгоритмов производительность.

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

Подробнее
Реклама
Комментарии 32
  • +22
    Я болел за Timsort.
    • +1
      Жаль, что mergesort не вошёл в сравнение, а аспект распараллеливания не был затронут.
      • +1
        Всё равно бы тимсорт победил — его суть в сортировке частей, а значит распараллеливание ему только на руку.
        • 0
          Да, из рассмотренных алгоритмов только timsort хоть как-то использует подход «разделяй и властвуй»
          • +2
            Почему же, quicksort параллелится очень просто. Каждая итерация делит массив на две части, знай только да создавай новые треды на них. Только самая долгая, самая первая итерация не параллелится.

            Тоже хотелось бы посмотреть результаты в параллельной обработке. И конечный результат и прирост от параллелизма. На 4х-ядернике желательно, или более.
            • 0
              Да, вы правы, про quicksort что-то я забыл
          • 0
            Это зависит от того, какой процент общего времени занимает слияние массивов. Этот этап тяжело распараллелить.
          • +1
            Из классических алгоритмов выбор пал только на heapsort и quicksort из-за того, что первый идейно близок к smoothsort, а второй является самым быстрым из них. Подозреваю, что «чистый» mergesort находился бы где-то в районе shellsort — heapsort на графиках, хотя точно сказать не могу, не проверял. А распараллеливание — это уже отдельная большая тема для рассмотрения, честно, даже не подумал об этом)
            • 0
              Обогнать «чистый» mergesort на случайных данных практически невозможно, особенно, если его аккуратно написать, минимизируя число ненужных копирований. Он не столь популярен, как quicksort, только потому, что требует слишком много дополнительной памяти.
          • 0
            Как насчёт старой-доброй поразрядной сортировки? O(n) при ограниченном диапазоне значений (что на практике всегда выполняется). Было бы интересно погонять его вместе с прочими.
            • 0
              Для целых 32-битных чисел на длине массива 10^8 поразрядная сортировка по основанию 256 примерно в 3 раза быстрее, чем std::sort.
            • 0
              И все таки, сортировка Хоара остается одной из лучших. Хотя Timsort, конечно, выглядит великолепно. Хотел спросить: а распараллеливать алгоритмы не пытались? После этого картина станет немного другой.
              • 0
                Жаль, что на случайных данных Timsort уступает ~30% quicksort'у. Не будь этого, брал бы, не задумываясь.
                • 0
                  Зато он стабилен, я б его только за это брал, даже если б он на 100% медленнее был :) за 30% и думать не стоит
                • 0
                  Еще интересно было бы сравнить алгоритмы неполного упорядочивания данных для поиска медианы (сам таким анализом полностью не занимался: просто сразу взял готовые алгоритмы из Numerical Recipies. Но интересно: вдруг что побыстрей есть).
                  • 0
                    > Было сгенерировано 10 наборов по 10^8 случайных натуральных чисел, для каждого алгоритма было замерено среднее время работы.

                    вопрос к автору: не сликом ли маленькая статистика? вроде для получение более или менее адекватных средних нужно прогонять каждый тест раз по 10^4 — 10^5. Или большая размерность входных данных позволяет делать нормальные выводы?

                    просто если мало прогонов, то в это время мог какой-нибудь бекграунд-таск операционки затесаться, например, — и время выполнения для какого-то алгоритма сильно ухудшится. я не прав?
                    • 0
                      Статистика конечно не огромная, но в моем понимании для получения общей картины вполне достаточная. Как я уже писал, на каждом тестовом наборе все алгоритмы запускались по три раза, и выбиралось минимальное время из этих запусков. Собственно так я пытался избавиться от всяких непредусмотренных нагрузок. Плюс все это дело запускалось на ночь, систему я сам дополнительно никак не грузил.

                      Если бы была возможность, тестировал бы больше, но, к сожалению, чтобы прогнать все представленные тесты и так потребовалось несколько часов.

                      И вдобавок, на каждом наборе тестовых данных все алгоритмы запускались по очереди, так что долговременные бекграунды не должны были избирательно повлиять на некоторые алгоритмы)
                      • 0
                        ок, я понял, спасибо)

                        > И вдобавок, на каждом наборе тестовых данных все алгоритмы запускались по очереди

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

                        > Если бы была возможность, тестировал бы больше, но, к сожалению, чтобы прогнать все представленные тесты и так потребовалось несколько часов.

                        несколько часов — это еще хорошо, что не несколько дней
                        эх, вспоминаю, как мы тестировали МВГ. вот тут понимаешь, как ничтожны все эти мегагерцы и ядра в процессоре ))
                        • 0
                          Ну в свою защиту еще могу сказать, что пока все это дело писалось, все алгоритмы запускались большое количество раз, и результаты на ненагруженной системе всегда были почти одинаковыми)

                          > несколько часов — это еще хорошо, что не несколько дней

                          Был бы второй комп, можно было бы и больше тестировать) А так, самый большой промежуток что я могу не трогать систему — это время сна)
                    • 0
                      Посмотрев на графики я бы выбрал Quick. Даже не знаю почему абсолютным лидером стал Tim :)
                      • 0
                        Лидером из трех алгоритмов, которые работают за O(n) при упорядоченных данных)
                        • 0
                          потому что в отличие от быстрой сортировки, TimSort стабилен.
                      • 0
                        Первая диаграма меня несколько сконфузила. Называется она «Средняя скорость...», поэтому ожидаешь, что чем выше столбик, тем круче. А нет, на вертикальной оси оказывается отложено затраченное время. Было бы неплохо поправить несоответствие названия и данных.
                        • 0
                          Учту, постараюсь вечером исправить)
                        • 0
                          Ещё есть Dual-Pivot Quicksort.
                          • 0
                            вопрос такой — я правильно понял, 100млн рандомных интов quicksort сортирует за 35 секунд?
                            • 0
                              Вообще-то, за 12-13 секунд. Если работать на одном ядре, и если пользоваться «родной» операцией <, а не передавать функцию. Но это на 3.8 ГГц.
                            • 0
                              Возможно я что то не понял, но почему на графиках на позициях где количество элементов массива равно 10^1 10^2 скорость сортировки 13 сек. и выше? Почему так много?
                              • 0
                                А все понятно, просто невнимательно прочитал

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.