Pull to refresh

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

Reading time 9 min
Views 143K
Недавно на хабре в очередной подняли тему алгоритмов сортировки, а именно был хорошо описан метод 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'ом — так как он дает лучшую из простых в написании алгоритмов производительность.

Спасибо, что прочитали. Надеюсь, вам было интересно.
Tags:
Hubs:
+111
Comments 32
Comments Comments 32

Articles