Практическое применение сортировки по основанию

Question

Сортировка по основанию теоретически выполняется очень быстро, когда вы знаете, что ключи находятся в определенном ограниченном диапазоне, скажем, $ n $ значений в диапазоне $ [0 \ точек n ^ k -1] $, например.Если $ k<\ lg n $ вы просто преобразуете значения в базовые $ n $, что занимает $ \ Theta (n) $ время, выполняете базовую $ n $ сортировку по основанию, а затем конвертируете обратно в исходную базу для общего алгоритма $ \ Theta (nk) $.

Однако я читал, что на практике сортировка по радиусу обычно выполняется намного медленнее, чем, например, рандомизированная быстрая сортировка:

Для больших массивов radix sort имеет наименьшее количество команд, но из-за относительно низкой производительности кэша его общая производительность хуже, чем оптимизированные для памяти версии mergesort и quicksort.

Является ли сортировка по основанию просто хорошим теоретическим алгоритмом, или у него есть общие практические применения?

Answer 1

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

• Загха и Блеллох:Сортировка по основанию для векторных мультипроцессоров. Суперкомпьютинг, 1991: 712-721.
• Блеллох, Лейзерсон, Мэггс, Плакстон, Смит и Загха:Проведено сравнение алгоритмов сортировки для Соединительной машины СМ-2. Симп - параллельные алгоритмы и Arch (SPAA-3):3-16, 1991.
• Арпачи-Дюссо, Арпачи-Дюссо, Каллер, Хеллерштейн и Паттерсон:Высокопроизводительная сортировка в сетях рабочих станций. Conf на Mgt данных, (SIGMOD-1997): 243-254.
• Арпачи-Дюссо, Арпачи-Дюссо, Каллер, Хеллерштейн и Паттерсон.Поиск записи сортировки:опыт настройки СЕЙЧАС-Сортируйте. ACM Sigmetrics Symp Параллельные и распределенные инструменты, (SPDT-2): 124-133, 1998.

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

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

Answer 2

@Robert: Ваша ссылка довольно удивительна (на самом деле я не мог найти цитируемое предложение). Мой личный опыт для случайного ввода, Radix Sort намного быстрее, чем STL std::sort(), который использует вариант QuickSort. Раньше я делал алгоритм быстрее на 50%, заменив std::sort() с нестабильной Radix Sort. Я не уверен, что такое «оптимизированная память версия» QuickSort, но я сомневаюсь, что это может быть вдвое быстрее, чем версия STL.

Этот пост в блоге Оценит сортировку Radix вместе с несколькими другими алгоритмами сортировки. Вкратце, в этой оценке, std::sort() требует 5,1 секунды, чтобы сортировать 50 миллионов целых чисел, в то время как на месте/нестабильной Radix Sort занимает 2,0 секунды. Стабильная Radix Sort должна быть еще быстрее.

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

Answer 3

Radix Sort также является естественным способом сортировки слов с фиксированной длиной по фиксированному алгоритму, например, в алгоритме Kärkkäinen & Sanders (http://www.cs.cmu.edu/~guyb/realworld/paperss04/kasa03.pdf)