Когда мы должны использовать Radix Sort?

StackOverflow https://stackoverflow.com/questions/4146843

Вопрос

Кажется, Radix Sort имеет очень хорошую среднюю производительность случая, то есть O (кн): http://en.wikipedia.org/wiki/radix_sort.

Но кажется, что большинство людей все еще используют быстрые сортировки, не так ли?

Это было полезно?

Решение

Быстрый сорт имеет в среднем o (n logn), но он также имеет наихудший случай O (n ^ 2), поэтому даже в большинстве практических случаев он не дойдет до n ^ 2, всегда есть риск того, что вход будет в «плохом порядке» для вас. Этот риск не существует в Sortix Radix. Я думаю, что это дает большое преимущество для Radix Worth.

Другие советы

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

Отредактировано в соответствии с вашими комментариями:

  • Radix Сортировка применяется только к целым числам, строкам фиксированного размера, плавающих точках и «меньше, чем», «больше, чем« или «лексикографический порядок» предикатов сравнения, тогда как сорты сравнения могут вместить различные заказы.
  • K может быть больше, чем журнал N.
  • Быстрый сортировку можно сделать на месте, Radix Worth становится менее эффективным.

Другие ответы здесь ужасны, они не дают примеры при сортировке Radix на самом деле используется.

Примером при создании «массива суффикса» с помощью алгоритма SKEW DC3 (Kärkkäinen-Sanders-Burkhardt). Алгоритм является только линейным временем, если алгоритм сортировки является линейным времени, а Sortix Sortix необходим и полезен здесь, потому что клавиши короткие построения (3-х корты целых чисел).

Если у вас нет огромный Список или чрезвычайно маленькие клавиши, журнал (N) обычно меньше K, редко редко намного выше. Таким образом, выбирая алгоритм сортировки общего назначения с о o (n log n) среднего характеристики случая, не имеет некорректности, чем с использованием sortix.

Коррекция: Как указал @mehrdad в комментариях, аргумент выше не звучит: либо размер ключа постоянна, то Radix сортирует o (n), либо размер ключа k, то Quicksort o (K n log n ). Таким образом, теоретически, Radix Worth действительно имеет лучшую асимптотическое время выполнения.

На практике занятия розами будут доминировать условия, такие как:

  • Radix Сортировка: C1 K N

  • QuickSort: C2 K N Журнал (N)

где C1 >> C2, потому что «извлечение» бит из более длинного ключа, как правило, является дорогой операцией, включающей биты сдвиги и логические операции (или, по меньшей мере, неалигированным доступом памяти), в то время как современные процессоры могут сравнивать клавиши с 64, 128 или даже 256 битами 64, 128 или даже 256 в одной операции. Таким образом, для многих общих случаев, если N не является гигантским, C1 будет больше, чем журнал C2 (N)

Radix Сортировка принимает o (k * n) время. Но вы должны спросить, что является K. k - «Количество цифр» (немного упрощенно, но в основном что-то в этом роде).

Итак, сколько у вас цифры? Вполне отвечает, больше, чем log (n) (журнал используя «размер цифры» в качестве базы), что делает алгоритм Radix O (n log n).

Почему это? Если у вас есть меньше, чем в журнале (n) цифры, то у вас меньше чем возможных номеров. Следовательно, вы можете просто использовать «Count Sort», который принимает o (n) время (просто посчитайте, сколько у вас есть каждый номер). Поэтому я предполагаю, что у вас есть больше, чем k> log (n) цифры ...

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

Когда n> 128, мы должны использовать Radixsort

Когда сортировка INT32S я выбираю Radix 256, так что K = log (256, 2 ^ 32) = 4, что значительно меньше, чем журнал (2, n)

И в моем тесте, 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]来保证原有的顺序不变      
    }
}

k = "длина самого длинного значения в массиве, чтобы быть отсортированным"

n = "длина массива"

O (k * n) = "худший случай работает"

k * n = n ^ 2 (если k = n)

Поэтому при использовании Radix Sort Убедитесь, что «самое длинное целое число короче, чем размер массива» или наоборот. Тогда вы собираетесь победить Quicksort!

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

Вот ссылка, которая сравнивает QuickSort и Radixsort:

Радикс сортируется быстрее, чем QuickSort для целочисленных массивов? (да это, 2-3x)

Вот еще одна ссылка, которая анализирует время работы нескольких алгоритмов:

Вопрос о соревнованиях:

Что быстрее на одних и тех же данных; O (N) Сортировать или O (NLOG (N)) Сортировать?

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

Radix Worth - это сортировка на основе сравнения и может сортировать числовые типы, такие как целые числа (включая адреса указателя) и плавающей точкой, и немного сложно портативно поддерживать плавающую точку.

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

Тем не менее, несмотря на узкую применимость, в моем домене я нахожу больше использования для Radix сортов, чем интрапорты или Quicksorts. Я в этом 1% и едва когда-либо работаю, скажем, строковые ключи, но часто нахожу случаи использования для чисел, которые получают выгоду от сортировки. Это связано с тем, что моя кодовая база вращается вокруг индексов к объектам и компонентам (система компонентов на объекте), а также таких вещей, как индексированные сетки, и есть много числовых данных.

В результате Radix Worth становится полезным для всех видов вещей в моем случае. Один общий пример в моем случае устраняет дубликаты индексов. В этом случае мне не очень нужны результаты, которые будут отсортированы, но часто радикс-сорт может устранить дубликаты быстрее, чем альтернативы.

Другой находит, скажем, медиана раскололся для KD-дерева в данном измерении. Там Radix сортировка значений с плавающей запятой точки точки для данного измерения дает мне среднюю позицию быстро в линейном времени, чтобы разделить узел дерева.

Другой - сортировка глубины примитивов более высокого уровня z Для полуприцепной альфа-прозрачности, если мы не будем делать это в фрагристере. Это также относится к программному обеспечению Guis и Vector Graphics к элементам z-заказа.

Другой является кэширующим последовательным доступом с использованием списка индексов. Если индексы проходят много раз, он часто улучшает производительность, если i Radix заранее сортирует их, чтобы обход выполнен в последовательном порядке вместо случайного порядка. Последнее может восполнить Zig-zag в памяти, выселяя данные из линий кэша только для повторного перезагрузки той же области памяти в течение одного и того же цикла. Когда я Radix сортирует индексы сначала до доступа к ним неоднократно, что перестает произойти, и я могу значительно сократить пропустить кеш. Это на самом деле мое самое распространенное использование для сортов 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 мс, как с случаем C ++ std::sort или C's. qsort который определенно приведет к очень очевидным икотам в частоте кадров. Я даже слышал о людях, реализующих Radix сортирует, используя Simd, хотя я понятия не имею, как им это удалось. Я недостаточно умных, чтобы придумать такое решение, хотя даже мой наивный маленький радикс сортирует довольно хорошо по сравнению со стандартными библиотеками.

Одним из примеров будет, когда вы сортируете очень большой набор или массив целых чисел. Сортировка RADIX и любые другие виды распределения типов чрезвычайно быстры, поскольку элементы данных в основном являются в основном в массиве очередей (максимальные очереди 10 для сортировки LSD RADIX) и перенесены в другое местоположение того же входных данных. Там нет вложенных петель, поэтому алгоритм имеет тенденцию вести себя более линейно, поскольку число целых чисел данных ввода данных будет отсортировано, становится значительно большим. В отличие от других методов сортировки, таких как чрезвычайно неэффективный метод Bubblyort, сортировка RADIX не реализует операции сравнения для сортировки. Это просто простой процесс перенаправления целых чисел к различным положениям индекса до тех пор, пока ввод будет окончательно отсортирован. Если вы хотите проверить для себя LSD Radix, я написал один и сохраненный на GitHub, который может быть легко протестирован на IDE js js, таких как кодирующий кодирующий javaScript. Не стесняйтесь играть с ним и посмотрите, как это ведет себя с различными числами n. Я проверил до 900 000 несортированных целых чисел с временем выполнения <300 мс. Вот ссылка, если вы хотите играть с ним.

https://gist.github.com/stbean/4af58d09021899f14dfa585df6c86df6.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top