какая временная сложность у алгоритма сортировки timsort

Timsort

Timsort — гибридный алгоритм сортировки, сочетающий различные подходы.

Данный алгоритм является относительно новым и был придуман Тимом Петерсом. На массивах данных, которые содержат упорядоченный подмасивы, алгоритм Тима Петерса показывает себя намного лучше других сортировок. В настоящее время Timsort является стандартной сортировкой в Python и GNU Octave, реализован в OpenJDK 7 и Android JDK 1.5.

Содержание

Основная идея алгоритма [ править ]

Алгоритм Timsort состоит из нескольких частей:

Рассмотрим теперь каждый шаг в отдельности.

Алгоритм [ править ]

Обозначения [ править ]

Шаг 1. Вычисление minrun [ править ]

Нетрудно понять, что после таких вычислений, [math]\mathtt<\dfrac<>> [/math] будет равно степени двойки или немного меньше степени двойки.

Шаг 2. Алгоритм разбиения на подмассивы и их сортировка [ править ]

Шаг 3. Слияние [ править ]

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

Основная цель этой процедуры — сохранение баланса. Изменения будут выглядеть как на картинке, а значит и размеры подмассивов в стеке эффективны для дальнейшей сортировки слиянием.

Описание процедуры слияния [ править ]

Пример [ править ]

Модификация процедуры слияния подмассивов (Galloping Mode) [ править ]

Рассмотрим процедуру слияния двух массивов:

Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге [math]10000[/math] сравнений и [math]10000[/math] копирований. Timsort предлагает в этом месте модификацию, которая получила называет галоп. Алгоритм следующий:

Доказательство времени работы алгоритма [ править ]

Источник

Timsort — самый быстрый алгоритм сортировки, о котором вы никогда не слышали

Timsort: Очень быстрый, O(n log n), стабильный алгоритм сортировки, созданный для реального мира, а не для академических целей.

Timsort — это алгоритм сортировки, который эффективен для реальных данных, а не создан в академической лаборатории. Tim Peters создал Timsort для Python в 2001 году.

Timsort сначала анализирует список, который он пытается отсортировать, и на его основе выбирает наилучший подход. С момента его появления он используется в качестве алгоритма сортировки по умолчанию в Python, Java, платформе Android и GNU Octave.

Нотация Big O для Timsort — это O(n log n). Чтобы узнать о нотации Big O, прочтите это.

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

Peters разработал Timsort для использования уже упорядоченных элементов, которые существуют в большинстве реальных наборов данных. Он называет эти упорядоченные элементы «natural runs» (естественные пробеги). Они итеративно перебирают данные, собирая элементы в пробеги и одновременно объединяя несколько этих пробегов в один.

Если массив (array), который мы пытаемся отсортировать, содержит менее 64 элементов, Timsort выполняет сортировку вставкой.

Сортировка вставкой — это простая сортировка, которая наиболее эффективна для небольших списков. Она функционирует довольно медленно при работе с большими списками, но при этом быстро работает с маленькими списками. Идея сортировки вставкой заключается в следующем:

Просматривать элементы по одному

Построить отсортированный список, вставляя элемент в нужное место

Вот таблица, показывающая, как сортировка вставкой сортирует список [34, 10, 64, 51, 32, 21].

В данном случае мы вставляем только что отсортированные элементы в новый подмассив (sub-array), который начинается от начала массива.

Вот gif, показывающий сортировку вставкой:

Больше о пробегах

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

Таким образом, если пробег уменьшается, он будет выглядеть следующим образом (пробег выделен жирным шрифтом):

Если не происходит уменьшение, то это будет выглядеть следующим образом:

Алгоритм выбирает minrun из диапазона от 32 до 64 включительно, таким образом, чтобы длина исходного массива при расчете была меньше или равна степени числа 2.

Если длина пробега меньше minrun, необходимо рассчитать длину этого пробега относительно minrun. Используя это новое число выполняется сортировка вставкой для создания нового пробега.

Итак, если minrun равен 63, а длина пробега равна 33, вы выполняете вычитание: 63-33 = 30. Затем вы берете 30 элементов из run[33], и делаете сортировку вставкой для создания нового пробега.

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

Слияние

Теперь Timsort использует сортировку слиянием, чтобы объединить пробеги. Однако Timsort следит за тем, чтобы сохранить стабильность и баланс слияния во время сортировки.

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

Когда Timsort находит пробеги, он добавляет их в стек. Простой стек выглядит следующим образом:

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

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

Чтобы добиться компромисса, Timsort отслеживает три последних элемента в стеке и создает два правила, которые должны выполняться для этих элементов:

По словам Tim Peters:

Обычно объединить соседние пробеги разной длины очень сложно. Еще сложнее то, что мы должны поддерживать стабильность. Чтобы обойти эту проблему, Timsort выделяет временную память. Он помещает меньший (называя оба пробега A и B) из двух побегов в эту временную память.

Galloping*

*Модификация процедуры слияния подмассивов

Пока Timsort объединяет A и B, обнаруживается, что один пробег «выигрывает» много раз подряд. Если бы оказалось, что A состоял из гораздо меньших чисел, чем B, то A оказался бы на прежнем месте. Слияние этих двух пробегов потребовало бы много работы c нулевым результатом.

Чаще всего данные имеют некоторую уже существующую внутреннюю структуру. Timsort предполагает, что если многие значения пробега A меньше, чем значения пробега B, то, скорее всего, A будет и дальше содержать меньшие значения, чем B.

Затем Timsort переходит в режим galloping. Вместо того чтобы сверять A[0] и B[0] друг с другом, Timsort выполняет бинарный поиск соответствующей позиции b[0] в a[0]. Таким образом, Timsort может полностью переместить A. Затем Timsort ищет соответствующее местоположение A[0] в B. После этого Timsort также может полностью перемещает B.

Давайте посмотрим на это в действии. Timsort проверяет B[0] (который равен 5) и, используя бинарный поиск, ищет соответствующее место в A.

Оказывается, что действие не имеет смысла, если подходящее место для B[0] находится очень близко к началу A (или наоборот), поэтому режим gallop быстро завершается, если он не приносит результатов. Кроме того, Timsort принимает это к сведению и усложняет вход в режим gallop, увеличивая количество последовательных «побед» только в A или только в B. Если режим gallop приносит результаты, Timsort облегчает его повторный запуск.

Если говорить коротко, Timsort делает две вещи невероятно хорошо:

Обеспечивает высокую производительность при работе с массивами с уже существующей внутренней структурой

Создает возможность поддерживать стабильную сортировку

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

Если вас не интересует код, смело пропускайте эту часть. Под этим разделом есть дополнительная информация.

Если вы хотите увидеть оригинальный исходный код Timsort во всей его красе, посмотрите его здесь. Timsort официально реализован на C, а не на Python.

Timsort фактически встроен прямо в Python, поэтому этот код служит только в качестве пояснения. Чтобы использовать Timsort, просто напишите следующее:

Если вы хотите узнать, как работает Timsort, и понять его суть, я настоятельно рекомендую вам попробовать применить его самостоятельно!

Эта статья основана на оригинальном вступлении Tim Peters к Timsort, которое можно найти здесь.

Если вам интересно узнать о курсе больше, приглашаем на день открытых дверей онлайн.

Источник

Алгоритм сортировки Timsort

Для сортировки в CPython используется алгоритм Timsort, который его создатель Тим Петерс застенчиво назвал в честь себя. Timsort — это комбинация сортировки вставками и сортировки слиянием, заточенная под работу с реальными данными. Дело в том, что на практике массивы, которые нужно сортировать, часто бывают частично упорядочены и Timsort пользуется этим предположением для ускорения работы.

Логика работы Timsort на самом деле довольно прозрачная:

Но дьявол кроется в деталях.

Делим на подмассивы

Части, на которые алгоритм делит входной массив, в описании алгоритма автор называет run’ами. Так на какое количество run’ов следует разделить входной массив? Здесь два соображения. Во-первых, части должны быть достаточно короткими, чтобы их было выгодно сортировать вставками. А еще мы хотим, чтобы пары последовательностей, которые позже поступят в сортировку слиянием, были примерно одинаковой длины. Дальше происходит магия, которая учитывает эти соображения и выбирает длину подпоследовательности minrun между 32 и 64 элементами. При этом если входной массив короче 64 элементов, то на части он не делится.

Сортируем run’ы

Перед тем, как приступить к сортировке подмассива, алгоритм ищет изначально упорядоченные участки. Если они слишком короткие и не дотягивают до минимального размера, то алгоритм удлинняет их бинарной сортировкой (http://www.geneffects.com/briarskin/theory/binary/index.html). Бинарная сортировка — это разновидность сортировки вставками, которая помещает элементы на свои места, используя двоичный поиск. Сортировки вставками как раз эффективны в случаях небольших частично упорядоченных массивов. Сам Петерс пишет, что это лучшее, что можно было выбрать, учитывая ограничения более утонченных алгоритмов.

Сливаем подмассивы

По мере того, как упорядоченные run’ы формируются, сортировкой слияния они объединяются попарно во всё более крупные отсортированные куски. При этом, если алгоритм при слиянии последовательностей встречает два участка вида

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

Вывод

Объем алгоритма в исходнике примерно 2к строк и, как можно догадаться по описанию, код довольно запутанный. Зато за счет использования упорядоченности в реальных данных сложность Timsort в лучшем случае линейная. В худшем случае, если входные данные случайные, timsort справится за O(n log n), а это неплохо для сортировки. Кстати, несмотря на то, что Timsort изначально был придуман в Python-сообществе, сейчас он используется еще в Java, Swift и Android platform.

Вот что нужно запомнить о Timsort:

Визуализацию работы алгоритма можно посмотреть здесь:

Видно, как сначала строятся run’ы и как они сливаются. Обратите внимание, что в обоих прогонах всегда объединяются примерно равные по размеру части

Источник

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

Недавно на хабре в очередной подняли тему алгоритмов сортировки, а именно был хорошо описан метод 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

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

Smoothsort

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

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

Числа Леонардо определяются рекуррентно следующим образом:

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

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

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

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

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

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

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

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

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

Для примера: пусть необходимо отсортировать массив из 12 элементов, количество проходов равно 3, d₁ = 5, d₂ = 3, d₃ = 1
На первом шаге будут сортироваться следующие массивы:

(a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12)

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

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

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

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

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

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

Сравнение

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

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

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

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

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

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

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

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

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

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

Дано 10 8 различных натуральных чисел, отсортированных по возрастанию. Группируем их по 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.

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

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

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

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

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

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

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

Итоги

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

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

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

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

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

Спасибо, что прочитали. Надеюсь, вам было интересно.

Источник