Флэш-сортировка

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

Концепция

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

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

Шаги 1–3 и 6 являются общими для любой сортировки по сегментам и могут быть улучшены с использованием методов, общих для сортировок по сегментам. В частности, цель состоит в том, чтобы сегменты были примерно одинакового размера ( n / m элементов), каждое идеалом является деление на 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 на Aj _{извлекая} , т.е. сохраните t в Aj _, при этом предыдущее значение Aj _, смещенное таким образом.
• Уменьшите L _b , чтобы отразить тот факт, что A _j теперь правильно классифицирован.
• Если j ≠ i , перезапустите этот цикл с новым t .
• Если j = i , этот раунд завершается и начинается поиск нового первого неклассифицированного элемента A _i .
• Когда неклассифицированных элементов больше нет, распределение по сегментам завершено.

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

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

Предположим, что мы классифицировали все элементы до i −1 и рассматриваем A _i как потенциального нового лидера цикла. легко вычислить Целевой сегмент b . По инварианту цикла он классифицируется, если 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 . Затем продолжайте:

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

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

• Сохраните переменную c, идентифицирующую первую не полностью классифицированную корзину. Пусть c = 1 для начала , а когда c > m , распределение является полным.
• Пусть я = Lc _​ . Если i = L _{c −1} , увеличьте c и перезапустите этот цикл. ( Л ₀ знак равно 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 ² ) = О (1) . Таким образом, время выполнения окончательной сортировки вставкой составляет m ⋅ ​​O(1) = O ( m ) = O ( n ) .

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

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

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

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

См. также

• Интерполяционный поиск , использующий распределение элементов для поиска, а не сортировки.

Внешние ссылки

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