Flashsort

Flashsort - это алгоритм сортировки распределения , показывающий линейную вычислительную сложность O ( n ) для равномерно распределенных наборов данных и относительно небольшие требования к дополнительной памяти. Оригинальная работа была опубликована в 1998 году Карлом-Дитрихом Нойбертом. ^[1]

Концепция [ править ]

Flashsort является эффективным в месте реализации historgram рода , сам тип ведром рода . Он назначает каждый из n входных элементов одному из m сегментов , эффективно переупорядочивает входные данные для размещения сегментов в правильном порядке, а затем сортирует каждый сегмент. Исходный алгоритм сортирует входной массив A следующим образом:

1. Используя первый проход по вводу или априорное знание, найдите минимальный и максимальный ключи сортировки.
2. Линейно разделите диапазон [ A _min , A _max ] на m сегментов.
3. Сделайте один проход по входу, подсчитав количество элементов A _i, которые попадают в каждую корзину. (Нойберт называет сегменты «классами», а назначение элементов их сегментам «классификацией».)
4. Преобразуйте количество элементов в каждой корзине в префиксную сумму , где L _b - количество элементов A _i в корзине b или меньше. ( L ₀ = 0 и L _m = n .)
5. Перегруппируйте ввод, чтобы все элементы каждой корзины b сохранялись в позициях A _i, где L _{b −1} < i ≤ L _b .
6. Отсортируйте каждую корзину, используя сортировку вставкой .

Шаги 1–3 и 6 являются общими для любой сортировки по сегментам и могут быть улучшены с помощью методов, общих для сортировок по сегментам. В частности, цель состоит в том, чтобы сегменты были примерно одинакового размера ( n / m элементов в каждом) ^[1], при этом идеальным является разделение на m квантилей . Хотя основным алгоритмом является сортировка с линейной интерполяцией , если известно, что входное распределение неоднородно, нелинейное деление будет более точно приближать этот идеал. Аналогичным образом, окончательная сортировка может использовать любой из множества методов, включая рекурсивную сортировку по флэш-памяти.

Что отличает флэш-сортировку, так это шаг 5: эффективный O ( n ) алгоритм на месте для сбора элементов каждой корзины вместе в правильном относительном порядке с использованием только m слов дополнительной памяти.

Реализация с эффективным использованием памяти [ править ]

Фаза перестановки Flashsort выполняется циклически . Элементы начинаются как «неклассифицированные», затем перемещаются в правильный сегмент и считаются «классифицированными». Основная процедура состоит в том, чтобы выбрать неклассифицированный элемент, найти его правильный сегмент, заменить его там неклассифицированным элементом (который должен существовать, поскольку мы заранее подсчитали размер каждого сегмента), пометить его как классифицированный и затем повторить с только что обмененный неклассифицированный элемент. В конце концов, элемент обменивается сам с собой, и цикл заканчивается.

Детали легко понять, используя две (размером в слово) переменные на ведро. Умной частью является исключение одной из этих переменных, что позволяет использовать вдвое больше сегментов и, следовательно, вдвое меньше времени, затрачиваемого на окончательную сортировку O ( n ² ) .

Чтобы понять это с двумя переменными на ведро, предположим, что есть два массива из m дополнительных слов: K _b - (фиксированный) верхний предел ведра b (и K ₀ = 0 ), а L _b - (подвижный) индекс в ведре. b , поэтому K _{b −1} ≤ L _b ≤ K _b .

Мы поддерживаем инвариант цикла, что каждая корзина делится L _b на неклассифицированный префикс ( A _i для K _{b −1} < i ≤ L _b еще не перемещен в их целевые корзины) и классифицированный суффикс ( A _i для L _b < i ≤ K _b все находятся в правильном ведре и больше не будут перемещены). Первоначально L _b = K _b, и все элементы не классифицируются. По мере сортировки L _bуменьшаются до тех пор, пока L _b = K _{b −1} для всех b и все элементы не будут классифицированы в правильную корзину.

Каждый раунд начинается с нахождения первого не полностью классифицированного сегмента c (который имеет K _{c -1} < L _c ) и взятия первого неклассифицированного элемента в этом сегменте A _i, где i = K _{c -1} + 1 . (Нойберт называет это «лидером цикла».) Скопируйте A _i во временную переменную t и повторите:

• Вычислите сегмент b, которому принадлежит t .
• Пусть j = L _b будет местом, где будет храниться t .
• Обменять t на A _j , то есть сохранить t в A _j, при этом получая предыдущее значение A _j, смещенное таким образом.
• Уменьшите L _b, чтобы отразить тот факт, что теперь A _j правильно классифицирован.
• Если j ≠ i , перезапустите этот цикл с новым t .
• Если j = i , этот раунд окончен и выполняется поиск нового первого неклассифицированного элемента A _i .
• Когда неклассифицированных элементов больше нет, распределение по сегментам завершено.

При реализации таким образом с двумя переменными на сегмент выбор начальной точки i для каждого раунда фактически произвольный; любой неклассифицированный элемент может быть использован в качестве лидера цикла. Единственное требование - умение найти лидеров цикла.

Хотя в предыдущем описании K используется для поиска лидеров цикла, на самом деле можно обойтись без него, позволяя удалить весь массив m- слов. (После завершения распределения границы ведра можно найти в L. )

Предположим, что мы классифицировали все элементы до i −1 и рассматриваем A _i как потенциального нового лидера цикла. Легко вычислить его цель ведро б . По инварианту цикла он классифицируется, если L _b < i ≤ K _b , и неклассифицируется, если i находится вне этого диапазона. Первое неравенство легко проверить, но второе, похоже, требует значения K _b .

Оказывается, из предположения индукции о том, что все элементы до i −1 классифицируются, следует, что i ≤ K _b , поэтому нет необходимости проверять второе неравенство.

Рассмотрим ведро c, в которое попадает позиция i . То есть K _{c −1} < i ≤ K _c . По предположению индукции все элементы ниже i , включая все корзины до K _{c −1} < i , полностью классифицируются. Т.е. в остальной части массива не остается элементов, принадлежащих этим сегментам. Следовательно, невозможно, чтобы b < c .

Единственный оставшийся случай - это b ≥ c , откуда K _b ≥ K _c ≥ i , QED

С учетом этого алгоритм распределения flashsort начинается с L, как описано выше, и i = 1 . Затем продолжайте: ^{[1] [2]}

• Если i > n , распределение завершено.
• Для данного A _i вычислите ведро b, которому оно принадлежит.
• Если i ≤ L _b , то A _i не классифицируется. Скопируйте временную переменную t и:
  • Пусть j = L _b будет местом, где будет храниться t .
  • Обменять t на A _j , то есть сохранить t в A _j, при этом получая предыдущее значение A _j, смещенное таким образом.
  • Уменьшите L _b, чтобы отразить тот факт, что теперь A _j правильно классифицирован.
  • Если j ≠ i , вычислить сегмент b, которому принадлежит t, и перезапустить этот (внутренний) цикл с новым t .
• Теперь A _i правильно классифицирован. Увеличьте i и перезапустите (внешний) цикл.

При экономии памяти Flashsort имеет тот недостаток, что пересчитывает корзину для многих уже классифицированных элементов. Это уже делается дважды для каждого элемента (один раз на этапе подсчета ведра и второй раз при перемещении каждого элемента), но для поиска первого неклассифицированного элемента требуется третье вычисление для большинства элементов. Это может быть дорого, если сегменты назначаются с использованием более сложной формулы, чем простая линейная интерполяция. Вариант сокращает количество вычислений с почти 3 n до не более 2 n  +  m  - 1 , принимая последний неклассифицированный элемент в незаконченном ведре в качестве лидера цикла:

• Поддерживайте переменную c, идентифицирующую первую не полностью классифицированную корзину. Пусть для начала c = 1 , а когда c > m , распределение завершено.
• Пусть i = L _c . Если i = L _{c −1} , увеличьте c и перезапустите этот цикл. ( L ₀ = 0. )
• Вычислите сегмент b, которому принадлежит A _i .
• Если b < c , то L _c = K _{c −1} и мы закончили с ведром c . Увеличьте c и перезапустите этот цикл.
• Если b = c , классификация тривиальна. Уменьшите L _c и перезапустите этот цикл.
• Если b > c , то A _i не классифицируется. Выполните тот же цикл классификации, что и в предыдущем случае, затем перезапустите этот цикл.

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

Производительность [ править ]

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

Как и в случае со всеми типами ковшей, производительность критически зависит от баланса ковшей. В идеальном случае сбалансированного набора данных каждая корзина будет примерно одинакового размера. Если количество сегментов m линейно относительно входного размера n , каждое ведро имеет постоянный размер, поэтому сортировка одного ведра с помощью алгоритма O ( n ² ) , такого как сортировка вставкой, имеет сложность O (1 ² ) = O (1) . Таким образом, время выполнения заключительных сортировок вставкой составляет m ⋅ O (1) = O ( m ) = O ( n ) .

Выбор значения для m , количества сегментов, снижает время, затраченное на классификацию элементов (высокий m ), и время, затраченное на заключительный шаг сортировки вставкой (низкий m ). Например, если m выбрано пропорционально √ n , то время выполнения заключительных сортировок вставки, следовательно, будет m ⋅ O ( √ n ² ) = O ( n ^3/2 ) .

В наихудших сценариях, когда почти все элементы находятся в нескольких сегментах, сложность алгоритма ограничивается производительностью последнего метода сортировки сегментов, поэтому снижается до O ( n ² ) . Варианты алгоритма улучшают производительность в худшем случае за счет использования более эффективных сортировок, таких как быстрая сортировка или рекурсивная флэш- сортировка, для сегментов, размер которых превышает определенный предел. ^{[2] [3]}

Для m = 0,1 n с равномерно распределенными случайными данными flashsort выполняется быстрее, чем heapsort для всех n, и быстрее, чем quicksort для n > 80 . Он становится примерно в два раза быстрее, чем быстрая сортировка при n = 10000 . ^[1] Обратите внимание, что эти измерения были сделаны в конце 1990-х, когда иерархия памяти была гораздо менее зависима от кэширования.

Из-за перестановки на месте , которую выполняет flashsort в процессе классификации, flashsort не является стабильным . Если требуется стабильность, можно использовать второй массив, чтобы элементы можно было классифицировать последовательно. Однако в этом случае алгоритму потребуется O ( n ) дополнительной памяти.

См. Также [ править ]

• Поиск с интерполяцией , использование распределения элементов для поиска, а не сортировки

Ссылки [ править ]

Внешние ссылки [ править ]

• Реализации рандомизированной сортировки на больших параллельных машинах (1992)
• Реализация параллельных алгоритмов (1992)
• Визуализация Flashsort