Практическое применение Radix Sort

20

Radix sort теоретически очень быстр, когда вы знаете, что ключи находятся в определенном ограниченном диапазоне, скажем, например, значений в диапазоне . Если вы просто конвертируете значения в базу что занимает время , выполните сортировку по основанию и затем преобразуйте обратно в исходную базу для общего алгоритма .N[0...NК-1]К<Л.Г.NNΘ(N)NΘ(NК)

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

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

Радикальная сортировка - это всего лишь хороший теоретический алгоритм, или она имеет практическое применение?

Роберт С. Барнс
источник

Ответы:

15

Сортировки Radix на практике часто являются самыми быстрыми и наиболее полезными на параллельных машинах.

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

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

Блуждающая логика
источник
Паттерсон и Хеннесси делают то же самое, что и вышеупомянутая связанная статья Ламарки в их книге «Организация компьютеров и дизайн».
Роберт С. Барнс
Ваше упоминание о Паттерсоне напомнило мне о важной работе, которую Андреа Арпачи-Дюссо проделала над сортировкой по кластерам около 15 лет назад. (Паттерсон был соавтором). В статье 1997 года они фактически решили, что сортировка с частичным основанием предпочтительнее, чем быстрая сортировка на отдельных узлах. (Я добавил ссылки на ответ).
Блуждающая логика
Это интересно. В четвертом издании CompOrg 2009 года они ссылаются на работу Ламарка над предыдущими версиями сортировки Radix, которая кеша недружелюбна (стр. 489), но затем на странице 490 под графиками, сравнивающими сортировку Quicksort и Radix, говорится: «Из-за таких результатов появляются новые версии Изобретены радикальные сортировки, которые принимают во внимание иерархию памяти, чтобы восстановить свои алгоритмические преимущества ». Мне интересно, как работают эти новые версии Radix Sort.
Роберт С. Барнс
Я подозреваю, что Ламарка только что использовал глупую радикальную сортировку (такую, которая хранит свои ведра в виде связанных списков). Никто никогда бы этого не сделал. Вы бы реализовали сегменты, используя некоторый оптимизированный динамический массив (например, C ++ vector). Но я не знаю, так как я не читал газеты Ламарки.
Блуждающая логика
@WanderingLogic, где сортировка radix использует сегменты? Вы имеете в виду сортировку ведра здесь?
Бар
3

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

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

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

user172818
источник