Кажется Radix сорт имеет очень хорошую среднюю производительность случая, т.е. O (кН): http://en.wikipedia.org/wiki/Radix_sortКогда мы будем использовать сортировку Radix?
но мне кажется, что большинство людей все еще используют Quick Sort, не так ли?
Быстрая сортировка имеет среднее значение O (N logN), но также имеет наихудший случай O (N^2), поэтому даже в большинстве практических случаев он не попадает в N^2, всегда есть риск, что вход будет в «плохом порядке» для вас. Этот риск не существует в сортировке radix. Я думаю, что это дает большое преимущество для сортировки radix.
Это вряд ли будет основным преимуществом.Другие сорта сравнения (например, heapsort или mergesort) не имеют такого плохого худшего поведения, как quicksort. –
сценарий худшего сценария для quicksort не является аргументом, так как люди обычно используют рандомизированную quicksort, т. Е. Перетасовывают входные данные перед фактической их сортировкой. это практически исключает возможность выполнения N^2 времени работы. – nburk
Introsort, который использует quicksort, позаботится об этом. Это не аргумент. – Mehrdad
Отредактировано в соответствии с вашими комментариями:
«Быстрая сортировка может быть сделана на месте» - так может быть двоичная сортировка счисления, хотя это увеличивает вероятность того, что k больше, чем log N. –
Ваша первая точка не совсем правильная - сортировка Radix может быть легко применена к строкам фиксированной длины. И предикат сравнения требуется независимо от того, какой алгоритм сортировки вы используете. –
«Сортировка Radix применяется только к целым числам: почему? Я всегда думал, что если вы сортируете по битам экспоненты и битам мантиссы в правильном порядке, вы можете использовать его для сортировки числа с плавающей запятой. И теоретически вы * можете * использовать его в строках, только k почти всегда будет больше, чем log N. – Niki
Сортировка Radix сложнее обобщить, чем большинство других алгоритмов сортировки. Для этого требуются ключи фиксированного размера, а также стандартный способ разбить ключи на куски. Таким образом, он никогда не находит своего пути в библиотеки.
Если у вас есть огромный список или очень маленькие ключи, log (N) обычно меньше k, он редко намного выше. Поэтому выбор алгоритма сортировки общего назначения с производительностью O (N log N) в среднем случае не обязательно хуже, чем использование сортировки radix.
Коррекция: Как @Mehrdad отметил в комментарии, приведенные выше рассуждения не звучит: Либо размер ключа является постоянным, то Radix сортировки O (N), или размер ключа к, то быстрая сортировка O (k N log N). Итак, теоретически, сортировка radix действительно имеет лучшее асимптотическое время выполнения.
На практике, время автономной работы будет доминировать такие термины, как:
поразрядной сортировки: c1 K N
быстрой сортировки: c2 к N журнал (N)
где c1 >> c2, поскольку «извлечение» битов из более длинного ключа обычно является дорогостоящей операцией, включающей сдвиги бит и логические операции (или, по меньшей мере, неравномерный доступ к памяти), в то время как современные процессоры могут сравнивать ключи с 64, 128 или даже 256 бит за одну операцию. Поэтому для многих распространенных случаев, если N не является гигантским, c1 будет больше, чем c2 log (N)
Это неверно для всех случаев. 'k' не обязательно должно быть битным, например, байтом может быть байтовый счетчик - если вы сортируете 4-байтовые целые числа,' N' должно быть меньше 16 для 'log N' меньше 4 –
O (N log N) является ** ложью **. Такого нет. Это O (k N log N) против O (k N) - если вы мне не верите, спросите себя, как сортировка в мире может быть независима от размера элемента. – Mehrdad
@Mehrdad: Это похоже на аргумент о семантике. Как я это узнал, N в O (N log N) - это размер ввода, например. в битах. Тогда либо элементы имеют постоянный размер, либо только N/k элементов. – Niki
Radix sort принимает значение O (k * n). Но вы должны спросить, что такое K. K - это «количество цифр» (немного упрощенное, но в основном что-то подобное).
Итак, сколько цифр у вас есть? Вполне ответ, больше, чем log (n) (журнал с использованием «разрядного размера» в качестве базы), который делает алгоритм Radix O (n log n).
Почему? Если у вас меньше, чем log (n) цифр, то у вас меньше n возможных чисел. Следовательно, вы можете просто использовать «sort sort», который принимает O (n) время (просто подсчитайте, сколько из каждого числа у вас есть). Поэтому я предполагаю, что у вас больше, чем k> log (n) цифр ...
Именно поэтому люди не используют Radix. Хотя бывают случаи, когда стоит использовать его, в большинстве случаев быстрый сортировка намного лучше.
к = «длина самого длинного значения в массиве должны быть отсортированы»
п = «длина массива»
О (к * п) = «наихудший случай работает»
k * n = n^2 (если k = n)
поэтому при использовании сортировки Radix убедитесь, что «самое длинное целое короче размера массива» или наоборот. Тогда вы собираетесь победить Quicksort!
Недостатком является: большую часть времени вы не можете гарантировать, как большие целые числа становятся, но если у вас есть фиксированный диапазон чисел, то порядок сортировки должен быть способом.
при п> 128, мы должны использовать RadixSort
когда-то int32s, я выбираю Radix 256, поэтому к = лог (256, 2^32) = 4, что имеет существенное значение меньше, чем журнал (2, п)
и в моем тесте, сортировка radix в 7 раз быстрее, чем quicksort в лучшем случае.
public class RadixSort {
private static final int radix=256, shifts[]={8,16,24}, mask=radix-1;
private final int bar[]=new int[radix];
private int s[] = new int[65536];//不使用额外的数组t，提高cpu的cache命中率
public void ensureSort(int len){
if(s.length < len)
s = new int[len];
}
public void sort(int[] a){
int n=a.length;
ensureSort(n);
for(int i=0;i<radix;i++)bar[i]=0;
for(int i=0;i<n;i++)bar[a[i]&mask]++;//bar存放了桶内元素数量
for(int i=1;i<radix;i++)bar[i]+=bar[i-1];//bar存放了桶内的各个元素在排序结果中的最大下标+1
for(int i=0;i<n;i++)s[--bar[a[i]&mask]]=a[i];//对桶内元素，在bar中找到下标x=bar[slot]-1, 另s[x]=a[i]（同时--bar[slot]将下标前移，供桶内其它元素使用）
for(int i=0;i<radix;i++)bar[i]=0;
for(int i=0;i<n;i++)bar[(s[i]>>8)&mask]++;
for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>8)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变
for(int i=0;i<radix;i++)bar[i]=0;
for(int i=0;i<n;i++)bar[(a[i]>>16)&mask]++;
for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
for(int i=n-1;i>=0;i--)s[--bar[(a[i]>>16)&mask]]=a[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变
for(int i=0;i<radix;i++)bar[i]=0;
for(int i=0;i<n;i++)bar[(s[i]>>24)&mask]++;
for(int i=129;i<radix;i++)bar[i]+=bar[i-1];//bar[128~255]是负数，比正数小
bar[0] += bar[255];
for(int i=1;i<128;i++)bar[i]+=bar[i-1];
for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>24)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变
}
}
Неужели radix-256 нуждается в 256-кратной памяти размера исходного массива? –
нет, как вы можете видеть в кодах, ему нужны только бар [256] и s [original.length], это дополнительная 1-кратная память исходного массива – zhuwenbin
Другие ответы здесь ужасны, они не дают примеров, когда радикс рода фактически используется.
Примером является создание «массива суффиксов» с использованием алгоритма косой DC3 (Kärkkäinen-Sanders-Burkhardt). Алгоритм является только линейным, если алгоритм сортировки является линейным временем, а сортировка радикса необходима и полезна здесь, потому что ключи коротки по построению (3 набора целых чисел).
Полностью согласен. Нет упоминаний о том, когда он используется, и нет реальных мировых тестов, которые сравнивают два алгоритма. – johndoevodka
Вот ссылка, которая сравнивает быстрой сортировки и RadixSort:
Is radix sort faster than quicksort for integer arrays? (да это, 2-3x)
Вот еще одна ссылка, которая анализирует запущенные времена нескольких алгоритмов:
Который быстрее по тем же данным; сортировка O (n) или сортировка O (nLog (n))?
Ответ: Это зависит. Это зависит от количества сортируемых данных. Это зависит от аппаратного обеспечения, на котором он выполняется, и зависит от реализации алгоритмов.
Одним из примеров может быть то, что вы сортируете очень большой набор или массив целых чисел. Сортировка счисления по методу редизайна и любые другие виды дистрибуции чрезвычайно велики, поскольку элементы данных в основном помещаются в массив очередей (макс. 10 очередей для сортировки по методу LSD) и переназначаются на другое местоположение индекса для тех же входных данных, которые нужно отсортировать. Нет вложенных циклов, поэтому алгоритм ведет себя более линейно, так как количество целых чисел ввода данных, подлежащих сортировке, становится значительно большим. В отличие от других методов сортировки, таких как крайне неэффективный метод bubbleSort, сортировка radix не выполняет операции сравнения для сортировки. Это простой процесс перекомпоновки целых чисел в разные позиции индекса до тех пор, пока вход не будет окончательно отсортирован.Если вы хотите проверить сортировку LSD radix для себя, я написал один файл и сохранил его на github, который можно легко протестировать на онлайн-js ide, таком как текстовая изолированная песочница javascript. Не стесняйтесь играть с ним и наблюдать, как он ведет себя с разными числами n. Я тестировал до 900 000 несортированных целых чисел с временем выполнения < 300 мс. Вот ссылка, если вы хотите поиграть с ней.
https://gist.github.com/StBean/4af58d09021899f14dfa585df6c86df6
Radix род не сравнение на основе сортировки и могут только сортировать числовые типы, такие как целые числа (включая указатель адреса) и с плавающей точкой, и это немного трудно переносимая поддержки с плавающей точкой.
Возможно, это связано с тем, что он имеет такой узкий диапазон применимости, что многие стандартные библиотеки предпочитают его пропускать. Он даже не позволяет вам предоставлять свой собственный компаратор, поскольку некоторые люди могут не захотеть даже сортировать целые числа непосредственно так же, как использовать целые числа в качестве индексов, чтобы что-то еще использовалось в качестве ключа для сортировки, например. Сопоставления на основе сравнения позволяют использовать всю эту гибкость, поэтому, вероятно, это случай, когда вы предпочитаете обобщенное решение, удовлетворяющее 99% ежедневных потребностей людей, вместо того, чтобы уходить с пути, чтобы удовлетворить 1%.
При этом, несмотря на узкую применимость, в моем домене я нахожу больше использования для сортировки по методу радикса, чем для интросортирования или быстрой сортировки. Я нахожусь в этом 1% и почти никогда не работаю, скажем, с строковыми ключами, но часто нахожу варианты использования чисел, которые могут быть отсортированы. Это связано с тем, что моя кодовая база вращается вокруг индексов для объектов и компонентов (система сущностей), а также таких вещей, как индексированные сетки, и существует множество числовых данных.
В результате сортировка radix становится полезной для всех вещей в моем случае. Одним из распространенных примеров в моем случае является устранение повторяющихся индексов. В этом случае мне не нужны результаты, которые нужно сортировать, но часто сортировка по методу radix может исключать дубликаты быстрее, чем альтернативы.
Другое - найти, скажем, срединный раскол для kd-дерева вдоль заданной размерности. Там radix, сортирующий значения с плавающей запятой точки для данного измерения, дает мне медианную позицию быстро в линейном времени для разделения узла дерева.
Другое - это примитивы более высокого уровня, сортирующие по глубине, на z для полу-правильной альфа-прозрачности, если мы не будем делать это в фразовом шейдере. Это также относится к GUI и программному обеспечению для векторной графики для элементов z-порядка.
Другим является последовательный доступ к кешам с использованием списка индексов. Если индексы пересекаются много раз, это часто повышает производительность, если я радически сортирую их заранее, чтобы обход выполнялся в последовательном порядке, а не в случайном порядке. Последний может выполнять zig-zag взад и вперед в памяти, вытесняя данные из строк кеша только для повторной загрузки одной и той же области памяти в пределах одного и того же цикла. Когда я начинаю сортировать индексы сначала до обращения к ним повторно, это перестает происходить, и я могу значительно сократить промахи в кэше. Это на самом деле самое распространенное использование для сортировок radix, и это ключ к тому, что мой ECS является кэшируемым, когда системы хотят получить доступ к объектам с двумя или более компонентами.
В моем случае у меня есть многопоточная сортировка радикса, которую я использую довольно часто. Некоторые тесты:
--------------------------------------------
- test_mt_sort
--------------------------------------------
Sorting 1,000,000 elements 32 times...
mt_radix_sort: {0.234000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
std::sort: {1.778000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
qsort: {2.730000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
Я усреднять что-то вроде 6-7 мс для сортировки миллиона номеров один раз на моем изящный аппаратное обеспечение, которое не является столь же быстро, как хотелось бы, так как 6-7 миллисекунды до сих пор может быть замечено пользователи иногда в интерактивных контекстах, но все же намного лучше, чем 55-85 мс, как и в случае с std::sort C++ или C qsort, что, безусловно, приведет к очень очевидным иконам в частоте кадров.Я даже слышал о том, что люди внедряют сортировки radix, используя SIMD, хотя я понятия не имею, как они это сделали. Я недостаточно умен, чтобы придумать такое решение, хотя даже моя наивная небольшая сортировка по методу radix довольно хорошо по сравнению со стандартными библиотеками.
Большинство людей используют процедуру сортировки, предоставляемую их предпочтительной структурой, даже не заботясь об алгоритме. –
Сортировка Radix не подходит для разных типов данных, но если вы хотите отсортировать неподписанные int и хотите сделать сортировку на многоядерном процессоре, таком как GPU, сортировка по методу radix выполняется быстрее. – tintin