Целочисленная сортировка - Integer sorting

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

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

Общие Соображения

Модели вычислений

Границы времени для алгоритмов целочисленной сортировки обычно зависят от трех параметров: числа n значений данных, которые нужно отсортировать, величины K наибольшего возможного ключа для сортировки и количества w битов, которые могут быть представлены в одном машинном слове компьютер, на котором будет выполняться алгоритм. Обычно предполагается, что w ≥ log ₂ (max ( n , K )) ; то есть машинные слова достаточно велики, чтобы представлять индекс в последовательности входных данных, а также достаточно велики, чтобы представлять один ключ.

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

Андерссон, Милтерсен и Торуп (1999) показали, что в некоторых случаях умножения или поиск в таблицах, требуемые некоторыми алгоритмами целочисленной сортировки, можно заменить настраиваемыми операциями, которые легче реализовать на оборудовании, но которые обычно не доступны на компьютерах общего назначения. Thorup (2003) улучшил это, показав, как заменить эти специальные операции командами манипулирования битовыми полями, уже доступными на процессорах Pentium .

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

Сортировка по сравнению с очередями с целочисленным приоритетом

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

Вместо использования очереди с целочисленным приоритетом в алгоритме сортировки можно пойти в другом направлении и использовать алгоритмы целочисленной сортировки в качестве подпрограмм в структуре данных очереди с целочисленным приоритетом. Thorup (2007) использовал эту идею, чтобы показать, что, если возможно выполнить целочисленную сортировку за время T ( n ) для каждого ключа, то такая же временная граница применяется ко времени на операцию вставки или удаления в структуре данных очереди приоритетов. Редукция Торупа сложна и предполагает наличие либо операций быстрого умножения, либо поиска в таблице, но он также предоставляет альтернативную приоритетную очередь, используя только операции сложения и логические операции со временем T ( n ) + T (log n ) + T (log log n ). + ... за операцию, самое большее умножение времени на повторный логарифм .

Юзабилити

Классическое число алгоритмов сортировки по цифровой сортировке , подсчет рода , и Radix рода широко используются и практично. Большая часть последующих исследований алгоритмов целочисленной сортировки была сосредоточена не столько на практичности, сколько на теоретических улучшениях в их анализе наихудшего случая , и алгоритмы, полученные из этого направления исследований, не считаются практичными для современных 64-битных компьютерных архитектур, хотя Эксперименты показали, что некоторые из этих методов могут быть улучшением сортировки по основанию для данных со 128 или более битами на ключ. Кроме того, для больших наборов данных паттерны почти случайного доступа к памяти многих алгоритмов целочисленной сортировки могут затруднять их выполнение по сравнению с алгоритмами сортировки сравнения, которые были разработаны с учетом иерархии памяти.

Целочисленная сортировка обеспечивает один из шести тестов в наборе тестов дискретной математики высокопроизводительных вычислительных систем DARPA и один из одиннадцати тестов в наборе параллельных тестов NAS .

Практические алгоритмы

Сортировка по голубятне или сортировка по подсчету могут одновременно сортировать n элементов данных с ключами в диапазоне от 0 до K - 1 за время O ( n + K ) . При сортировке по ячейкам (часто называемой сортировкой по сегментам) указатели на элементы данных распределяются по таблице сегментов, представленных в виде типов данных коллекции, таких как связанные списки , с использованием ключей в качестве индексов в таблице. Затем все сегменты объединяются вместе, чтобы сформировать выходной список. Сортировка подсчета использует таблицу счетчиков вместо таблицы сегментов, чтобы определить количество элементов с каждым ключом. Затем вычисление суммы префикса используется для определения диапазона позиций в отсортированном выводе, в который должны быть помещены значения с каждым ключом. Наконец, при втором проходе по входу каждый элемент перемещается в позицию своего ключа в выходном массиве. Оба алгоритма включают только простые циклы по входным данным (время O ( n ) ) и по набору возможных ключей (время O ( K ) ), что дает их общий временной интервал O ( n + K ) .

Radix sort - это алгоритм сортировки, который работает для ключей большего размера, чем сортировка по ячейкам или сортировка с подсчетом, путем выполнения нескольких проходов по данным. Каждый проход сортирует ввод, используя только часть ключей, используя другой алгоритм сортировки (например, сортировку по ячейкам или сортировку по подсчету), который подходит только для маленьких ключей. Чтобы разбить ключи на части, алгоритм сортировки по основанию системы счисления вычисляет позиционную нотацию для каждого ключа в соответствии с некоторым выбранным основанием системы счисления ; тогда часть ключа, используемая для i- го прохода алгоритма, является i- й цифрой в позиционной записи для полного ключа, начиная с наименее значащей цифры и переходя к наиболее значимой. Чтобы этот алгоритм работал правильно, алгоритм сортировки, используемый при каждом проходе по данным, должен быть стабильным : элементы с одинаковыми цифрами не должны меняться друг с другом. Для наибольшей эффективности, основание системы счисления следует выбирать так, чтобы оно соответствовало количеству элементов данных n . Кроме того, использование степени двойки около n в качестве основания системы счисления позволяет быстро вычислять ключи для каждого прохода, используя только операции быстрого двоичного сдвига и маски. С этими вариантами и с сортировкой по ячейкам или сортировке с подсчетом в качестве базового алгоритма алгоритм сортировки по основанию может сортировать n элементов данных с ключами в диапазоне от 0 до K - 1 за время O ( n log _n K ) .

Теоретические алгоритмы

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

Алгоритмы для маленьких ключей

Ван Эмде Боас дерево может быть использовано в качестве приоритетной очереди для сортировки набора п ключей, каждый в диапазоне от 0 до K - 1 , за время O ( п войти войти K ) . Это теоретическое улучшение по сравнению с сортировкой по основанию, когда K достаточно велико. Однако для использования дерева Ван-Эмде Боаса требуется либо непосредственно адресуемая память из K слов, либо его необходимо моделировать с помощью хеш-таблицы , уменьшая пространство до линейного, но делая алгоритм рандомизированным. Еще одна приоритетная очередь с аналогичной производительностью ( в том числе необходимость рандомизации в виде хэш - таблиц) представляет собой Y-быстро Trie из Уиллард (1983) .

Киркпатрик и Райш (1984) разработали более сложную технику с аналогичным вкусом и с лучшими теоретическими характеристиками . Они заметили, что каждый проход поразрядной сортировки можно интерпретировать как метод уменьшения диапазона, который за линейное время уменьшает максимальный размер ключа в  n раз ; вместо этого их метод уменьшает размер ключа до квадратного корня из его предыдущего значения (уменьшая вдвое количество битов, необходимых для представления ключа), снова за линейное время. Как и в поразрядной сортировке, они интерпретируют ключи как двузначные base- б чисел для базового Ь , которая приблизительно √ К . Затем они группируют элементы, которые нужно отсортировать, в сегменты в соответствии с их старшими цифрами за линейное время, используя либо большую, но неинициализированную память с прямым адресом, либо хеш-таблицу. У каждого ведра есть представитель, предмет в ведре с самым большим ключом; Затем они сортируют список пунктов, используя в качестве ключей старшие цифры для представителей и младшие цифры для не-представителей. Снова группируя элементы из этого списка в сегменты, каждый сегмент может быть размещен в отсортированном порядке, и путем извлечения представителей из отсортированного списка сегменты могут быть объединены вместе в отсортированный порядок. Таким образом, в линейном времени проблема сортировки сводится к другой задаче рекурсивной сортировки, в которой ключи намного меньше, квадратный корень из их предыдущей величины. Повторение этого сокращения диапазона до тех пор, пока ключи не станут достаточно маленькими для сортировки по сегментам, приводит к алгоритму со временем работы O ( n log log _n K ) .

Сложный рандомизированный алгоритм Han & Thorup (2002) в модели вычислений word RAM позволяет уменьшить эти временные границы еще больше, до O ( n √ log log K ) .

Алгоритмы для больших слов

Алгоритм целочисленной сортировки называется неконсервативным, если для него требуется размер слова w , значительно превышающий log max ( n , K ) . В качестве крайнего случая, если w ≥ K и все ключи различны, то набор ключей может быть отсортирован за линейное время, представив его как битовый вектор , с 1 битом в позиции i, когда i является одним из входных ключей, а затем многократно удаляя младший бит.

Неконсервативная упакована сортировки алгоритм Альберса и Хагеруп (1997) использует подпрограмму, на основе Кен Батчер «s bitonic сети сортировки , для слияния два отсортированных последовательности ключей, каждый из которых достаточно коротких , чтобы быть упакованы в единое машинное слово. Вход в алгоритм упакованной сортировки, последовательность элементов, хранящихся по одному на слово, преобразуется в упакованную форму, последовательность слов, каждое из которых содержит несколько элементов в отсортированном порядке, с помощью этой подпрограммы многократно, чтобы удвоить количество элементов, упакованных в каждую. слово. Когда последовательность упакована, Альберс и Хагеруп используют для ее сортировки форму сортировки слиянием; когда две последовательности объединяются в одну более длинную последовательность, одна и та же подпрограмма битонной сортировки может использоваться для многократного извлечения упакованных слов, состоящих из наименьших оставшихся элементов двух последовательностей. Этот алгоритм получает достаточное ускорение от своего упакованного представления для сортировки входных данных за линейное время всякий раз, когда одно слово может содержать ключи Ω (log n log log n ) ; то есть, когда log K log n log log n ≤ cw для некоторой константы c > 0 .

Алгоритмы для нескольких предметов

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

Ранний результат в этом направлении был предоставлен Ajtai, Fredman & Komlós (1984) с использованием модели вычислений с использованием зондирования ячейки (искусственная модель, в которой сложность алгоритма измеряется только количеством выполняемых им обращений к памяти). Основываясь на своей работе, Фредман и Уиллард (1994) описали две структуры данных, Q-heap и атомарную кучу, которые можно реализовать на машине с произвольным доступом. Q-heap - это бит-параллельная версия двоичного дерева , которая позволяет выполнять операции с приоритетной очередью, а также запросы преемников и предшественников в постоянное время для наборов из O ((log N ) ^1/4 ) элементов, где N ≤ 2 ^w - размер предварительно вычисленных таблиц, необходимых для реализации структуры данных. Атомарная куча - это B-дерево, в котором каждый узел дерева представлен как Q-куча; он позволяет выполнять операции очереди с постоянным приоритетом времени (и, следовательно, сортировку) для наборов (log N ) ^{O (1)} элементов.

Андерссон и др. (1998) предоставляют рандомизированный алгоритм, называемый сортировкой по сигнатуре, который позволяет выполнять линейную сортировку по времени наборов до 2 ^{O ((log w ) 1/2 - ε )} элементов за раз для любой константы ε> 0 . Как и в алгоритме Киркпатрика и Райша, они выполняют сокращение диапазона, используя представление ключей в виде чисел с основанием  b для тщательного выбора b . Их алгоритм сокращения диапазона заменяет каждую цифру подписью, которая представляет собой хешированное значение с O (log n ) бит, так что разные значения цифр имеют разные подписи. Если n достаточно мало, числа, сформированные этим процессом замены, будут значительно меньше, чем исходные ключи, что позволяет неконсервативному алгоритму упакованной сортировки Albers & Hagerup (1997) сортировать замененные числа за линейное время. Из отсортированного списка замененных чисел можно сформировать сжатое дерево ключей за линейное время, а потомки каждого узла в дереве могут быть рекурсивно отсортированы с использованием только ключей размера b , после чего обход дерева дает отсортированный порядок предметов.

Транс-дихотомические алгоритмы

Фредман и Уиллард (1993) представили трансдихотомическую модель анализа для алгоритмов целочисленной сортировки, в которой ничего не предполагается о диапазоне целочисленных ключей и нужно ограничивать производительность алгоритма только функцией количества значений данных. В качестве альтернативы, в этой модели предполагается , что время работы алгоритма для набора из n элементов является временем работы наихудшего случая для любой возможной комбинации значений K и  w . Первым алгоритмом этого типа был алгоритм сортировки дерева слияния Фредмана и Уилларда , который выполняется за время O ( n log n / log log n ) ; это улучшение по сравнению со сравнительной сортировкой для любого выбора K и  w . Альтернативная версия их алгоритма, которая включает использование случайных чисел и операций целочисленного деления, улучшает это до O ( n √ log n ) .

С момента их работы были разработаны еще более совершенные алгоритмы. Например, многократно применяя технику сокращения диапазона Киркпатрика – Райша до тех пор, пока ключи не станут достаточно маленькими для применения алгоритма упакованной сортировки Альберса – Хагерупа, можно выполнить сортировку за время O ( n log log n ) ; однако часть этого алгоритма для уменьшения диапазона требует либо большой памяти (пропорциональной √ K ), либо рандомизации в виде хеш-таблиц.

Han & Thorup (2002) показали, как сортировать за время O ( n √ log log n ) . Их методика включает использование идей, связанных с сортировкой сигнатур, для разделения данных на множество небольших подсписок, размер которых достаточно мал, чтобы сортировка сигнатур могла эффективно сортировать каждый из них. Также можно использовать аналогичные идеи для детерминированной сортировки целых чисел по времени O ( n log log n ) и линейному пространству. Используя только простые арифметические операции (без умножений или поиска в таблице), можно выполнить сортировку за рандомизированное ожидаемое время O ( n log log n ) или детерминированно за время O ( n (log log n ) ^{1 + ε} ) для любой константы ε> 0 .

использованная литература

Сноски

Вторичные источники

Основные источники