| Учебный класс | Алгоритм сортировки |
|---|---|
| Структура данных | Множество |
| Наихудшая производительность | [1] [2] |
| Лучшая производительность | [3] |
| Средняя производительность | |
| Сложность пространства в наихудшем случае |
Timsort представляет собой гибрид стабильного алгоритма сортировки , полученный из сортировки слияния и вставки сортировки , предназначенная для хорошо работать на многих видах реальных данных. Он был реализован Тимом Петерсом в 2002 году для использования в языке программирования Python . Алгоритм находит подпоследовательности данных, которые уже упорядочены (запускаются), и использует их для более эффективной сортировки остатка. Это делается путем объединения прогонов до тех пор, пока не будут выполнены определенные критерии. Timsort является стандартным алгоритмом сортировки Python начиная с версии 2.3. Он также используется для сортировки массивов непримитивного типа в Java SE 7 , [4] на платформе Android ,[5] в GNU Octave , [6] в V8 , [7] Swift , [8] и Rust . [9]
В нем используются методы из статьи Питера Макилроя 1993 г. «Оптимистическая сортировка и теоретическая сложность информации». [10]
Операция [ править ]
Timsort был разработан, чтобы использовать преимущества прогонов последовательных упорядоченных элементов, которые уже существуют в большинстве реальных данных, естественных прогонов . Он выполняет итерацию по элементам сбора данных в прогоны и одновременно помещает эти прогоны в стек. Когда запуски на вершине стека соответствуют критерию слияния , они сливаются. Это продолжается до тех пор, пока не будут пройдены все данные; затем все прогоны объединяются по два за раз, и остается только один отсортированный прогон. Преимущество объединения упорядоченных прогонов вместо слияния подсписков фиксированного размера (как это делается при традиционной сортировке слиянием) состоит в том, что оно уменьшает общее количество сравнений, необходимых для сортировки всего списка.
Каждый прогон имеет минимальный размер, который зависит от размера входных данных и определяется в начале алгоритма. Если серия меньше этого минимального размера серии, сортировка вставкой используется для добавления дополнительных элементов в серию до тех пор, пока не будет достигнут минимальный размер серии.
Критерии слияния [ править ]
Timsort - это стабильный алгоритм сортировки (сохраняется порядок элементов с одним и тем же ключом), который стремится выполнять сбалансированные слияния (слияние, таким образом, объединяет прогоны одинакового размера).
Чтобы добиться стабильности сортировки, объединяются только последовательные прогоны. Между двумя непоследовательными запусками может быть элемент с одним и тем же ключом элементов внутри запусков, и объединение этих двух запусков изменит порядок равных ключей. Пример этой ситуации ([] - это упорядоченные прогоны): [1 2 2] 1 4 2 [0 1 2]
В поисках сбалансированных слияний Timsort рассматривает три прогона на вершине стека, X , Y , Z , и поддерживает инварианты:
- | Z | > | Y | + | X |
- | Y | > | X | [11]
Если какой-либо из этих инвариантов нарушается, Y объединяется с меньшим из X или Z, и инварианты проверяются снова. Как только инварианты соблюдаются, можно начинать поиск нового прогона в данных. [12] Эти инварианты поддерживают слияния как приблизительно сбалансированные, сохраняя при этом компромисс между отложением слияния для баланса, использованием новых запусков в кэш-памяти и относительно простыми решениями о слиянии.
Накладные расходы на объединение пространства [ править ]
Первоначальная реализация сортировки слиянием отсутствует, и у нее накладные расходы на пространство N (размер данных). Существуют реализации сортировки слиянием на месте, но они требуют больших затрат времени. Чтобы достичь среднего срока, Timsort выполняет сортировку слиянием с небольшими затратами времени и меньшими затратами места, чем N.
Сначала Timsort выполняет двоичный поискчтобы найти место, где первый элемент второго прогона будет вставлен в первый упорядоченный прогон, сохраняя его в порядке. Затем он выполняет тот же алгоритм, чтобы найти место, где последний элемент первого прогона будет вставлен во второй упорядоченный прогон, сохраняя его упорядоченным. Элементы до и после этих местоположений уже находятся на своих местах, и их не нужно объединять. Затем меньший из оставшихся элементов двух прогонов копируется во временную память, а элементы объединяются с большей серией в теперь свободное пространство. Если первый прогон меньше, слияние начинается с самого начала; если второй меньше, слияние начинается в конце. Эта оптимизация снижает количество необходимых перемещений элементов, время работы и временные накладные расходы на пространство в общем случае.
Пример: два прогона [1, 2, 3, 6, 10] и [4, 5, 7, 9, 12, 14, 17] должны быть объединены. Обратите внимание, что оба прогона уже отсортированы по отдельности. Наименьший элемент второго прогона - 4, и его нужно добавить в 4-ю позицию первого прогона, чтобы сохранить его порядок (при условии, что первая позиция прогона равна 1). Самый большой элемент первого прогона - 10, и его нужно будет добавить в 5-ю позицию второго прогона, чтобы сохранить его порядок. Следовательно, [1, 2, 3] и [12, 14, 17] уже находятся в своих конечных положениях, и прогоны, в которых требуются перемещения элементов, - это [6, 10] и [4, 5, 7, 9]. Обладая этими знаниями, нам нужно только выделить временный буфер размером 2 вместо 5.
Направление слияния [ править ]
Слияние может выполняться в обоих направлениях: слева направо, как при традиционной сортировке слиянием, или справа налево.
Галопирующий режим во время слияния [ править ]
Отдельное объединение прогонов R1 и R2 ведет к подсчету последовательных элементов, выбранных из прогона. Когда это число достигает минимального порога галопирования ( min_gallop ), Timsort считает, что вероятно, что многие последовательные элементы все еще могут быть выбраны из этого прогона, и переключается в режим галопирования. Предположим, что R1 отвечает за его запуск. В этом режиме алгоритм выполняет экспоненциальный поиск , также известный как поиск скачком, следующего элемента x цикла R2 в цикле R1. Это делается в два этапа: первый находит диапазон (2 k - 1, 2 k + 1- 1) где x. На втором этапе выполняется двоичный поиск элемента x в диапазоне, найденном на первом этапе. Галопирующий режим - это попытка адаптировать алгоритм слияния к шаблону интервалов между элементами в прогонах.
Галоп не всегда эффективен. В некоторых случаях режим «галопом» требует большего количества сравнений, чем простой линейный поиск . Согласно тестам, проведенным разработчиком, галопирование выгодно только тогда, когда начальный элемент одного запуска не является одним из первых семи элементов другого запуска. Это подразумевает начальный порог 7. Чтобы избежать недостатков режима галопирования, предпринимаются два действия: (1) Когда обнаруживается, что галопирование менее эффективно, чем бинарный поиск , из режима галопирования выходят. (2) Успех или неудача скачки используются для настройки min_gallop . Если выбранный элемент принадлежит к тому же массиву, который ранее возвращал элемент, min_gallopуменьшается на единицу, что способствует возвращению в режим галопирования. В противном случае значение увеличивается на единицу, что препятствует возврату в режим галопирования. В случае случайных данных значение min_gallop становится настолько большим, что режим галопирования никогда не повторяется. [13]
По убыванию [ править ]
Чтобы также воспользоваться преимуществами данных, отсортированных в порядке убывания, Timsort инвертирует строго убывающие прогоны, когда находит их, и добавляет их в стек прогонов. Поскольку нисходящие прогоны позже слепо меняются местами, исключение прогонов с равными элементами поддерживает стабильность алгоритма; т.е. равные элементы не будут перевёрнуты.
Минимальный размер тиража [ править ]
Поскольку слияние наиболее эффективно, когда количество запусков равно или немного меньше, чем степень двойки, и особенно менее эффективно, когда количество запусков немного больше, чем степень двойки, Timsort выбирает minrun, чтобы попытаться гарантировать бывшее состояние. [11]
Minrun выбирается из диапазона от 32 до 64 включительно, так что размер данных, деленный на minrun , равен или немного меньше степени двойки. Последний алгоритм берет шесть наиболее значимых битов размера массива, добавляет один, если установлен какой-либо из оставшихся битов, и использует этот результат в качестве minrun . Этот алгоритм работает для всех массивов, включая массивы меньше 64; для массивов размером 63 или меньше это устанавливает minrun равным размеру массива, а Timsort сокращается до сортировки вставкой. [11]
Анализ [ править ]
В худшем случае Timsort выполняет сравнения для сортировки массива из n элементов. В лучшем случае, когда входные данные уже отсортированы, он выполняется за линейное время, что означает, что это адаптивный алгоритм сортировки . [3]
Это выгодно по сравнению с Quicksort для сортировки ссылок на объекты или указателей, потому что они требуют дорогостоящего косвенного обращения к памяти для доступа к данным и выполнения сравнений, а преимущества согласованности кэша Quicksort значительно снижаются.
Официальная проверка [ править ]
В 2015 году голландские и немецкие исследователи из проекта EU FP7 ENVISAGE обнаружили ошибку в стандартной реализации Timsort. [14]
В частности, инварианты размеров стека обеспечивают жесткую верхнюю границу максимального размера требуемого стека. Реализация предварительно распределила стек, достаточный для сортировки 2 64 байта ввода, и избежала дальнейших проверок переполнения.
Однако гарантия требует, чтобы инварианты применялись к каждой группе из трех последовательных запусков, но реализация проверяла это только для трех лучших. [14] Используя инструмент KeY для формальной проверки программного обеспечения Java, исследователи обнаружили, что этой проверки недостаточно, и они смогли найти длины прогонов (и входные данные, которые генерировали эти длины прогонов), которые привели бы к более глубокому нарушению инвариантов. в стеке после слияния вершины стека. [15]
Как следствие, для определенных входов выделенный размер недостаточен для хранения всех несвязанных прогонов. В Java это генерирует для этих входных данных исключение выхода за пределы массива. Наименьший вход, который вызывает это исключение в Java и Android v7, имеет размер67 108 864 (2 26 ). (Более старые версии Android уже вызывали это исключение для определенных входов размера65 536 (2 16 ))
Реализация Java была исправлена путем увеличения размера предварительно выделенного стека на основе обновленного анализа наихудшего случая. В статье также показано, с помощью формальных методов, как установить предполагаемый инвариант, проверив, что четыре самых верхних прогона в стеке удовлетворяют двум правилам, указанным выше. Этот подход был принят в Python [16] и Android.
Ссылки [ править ]
- ^ Петерс, Тим. "[Python-Dev] Сортировка" . Список рассылки разработчиков Python . Проверено 24 февраля 2011 года .
[Timsort] также имеет хорошие аспекты: он стабилен (элементы, которые сравниваются равными, сохраняют свой относительный порядок, поэтому, например, если вы сортируете сначала по почтовому индексу, а второй раз по имени, люди с тем же именем по-прежнему отображаются в порядке увеличения почтовый индекс; это важно в приложениях, которые, например, уточняют результаты запросов на основе ввода данных пользователем). ... У него нет плохих случаев (O (N log N) - худший случай; N − 1 сравнения - лучший).
- ^ "[КАПЛИ]" . Проверено 1 сентября 2018 года .
TimSort - это интригующий алгоритм сортировки, разработанный в 2002 году для Python, сложность наихудшего случая которого была объявлена, но не доказана до нашего недавнего препринта.
- ^ а б Чандрамули, Бадриш; Гольдштейн, Джонатан (2014). Терпение - это добродетель: пересмотр слияния и сортировки на современных процессорах . SIGMOD / PODS.
- ^ "[# JDK-6804124] (coll) Заменить" измененную сортировку слиянием "в java.util.Arrays.sort на timsort" . Система ошибок JDK . Проверено 11 июня 2014 .
- ^ "Класс: java.util.TimSort <T>" . Документация по Android Gingerbread . Архивировано из оригинала 16 июля 2015 года . Проверено 24 февраля 2011 года .
- ^ "liboctave / util / oct-sort.cc" . Mercurial репозиторий исходного кода Octave . Строки 23-25 исходного блока комментариев . Проверено 18 февраля 2013 года .
Код по большей части украден из Python, listobject.c, который сам по себе не имеет заголовка лицензии.
Тем не менее, спасибо Тиму Петерсу за части кода, которые я скопировал.
- ^ "Получение сортировки в V8 · V8" . v8.dev . Проверено 21 декабря 2018 .
- ^ "Стабильна ли sort () в Swift 5?" . Форумы Swift . 4 июля 2019 . Дата обращения 4 июля 2019 .
- ^ "ломтик - Ржавчина" . doc.rust-lang.org . Проверено 17 сентября 2020 года .
- ↑ Макилрой, Питер (январь 1993 г.). «Оптимистическая сортировка и теоретическая сложность информации». Материалы четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . С. 467–474. ISBN 0-89871-313-7.
- ^ a b c "listsort.txt" . Исходный код Python . 10 февраля 2017.
- ^ MacIver, David R. (11 января 2010). «Что такое timsort, часть 1: Adaptive Mergesort» . Дата обращения 5 декабря 2015 .
- ^ Петерс, Тим. "listsort.txt" . Репозиторий CPython git . Проверено 5 декабря 2019 .
- ^ а б де Гау, Stijn; Rot, Jurriaan; де Бур, Франк С .; Бубель, Ричард; Хенле, Райнер (июль 2015 г.). «Java.utils.Collection.sort () OpenJDK не работает: хорошие, плохие и худшие случаи» (PDF) . Компьютерная проверка : 273–289. DOI : 10.1007 / 978-3-319-21690-4_16 .
- ^ Де Gouw, Stijn (24 февраля 2015). «Доказательство того, что алгоритм сортировки Android, Java и Python не работает (и показано, как это исправить)» . Дата обращения 6 мая 2017 .
- ^ Отслеживание проблем Python - Проблема 23515: Плохая логика в merge_collapse в timsort
Дальнейшее чтение [ править ]
- Оже, Николас; Никауд, Кирилл; Пивото, Карин (2015). «Стратегии слияния: от сортировки слиянием до TimSort» . хал-01212839 .
- Оже, Жуже, Нико, Пивото (2018). «О сложности TimSort в наихудшем случае» . ESA 2018.
- Сэм Басс, Александр Кноп. «Стратегии стабильной сортировки слиянием». SODA 2019.
Внешние ссылки [ править ]
- timsort.txt - оригинальное объяснение Тима Петерса
