Когда следует использовать сортировку Radix?

Быстрая сортировка имеет среднее значение O (N logN), но также имеет наихудший случай O (N ^ 2), поэтому даже из-за того, что в большинстве практических случаев он не дойдет до N ^ 2, всегда существует риск того, что ввод будет для вас в "плохом состоянии". Этот риск не существует при сортировке по основанию счисления. Я думаю, что это дает большое преимущество радииксной сортировке.

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

В других ответах здесь не приводятся примеры того, когда действительно используется поразрядная сортировка.

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

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

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

Если у вас нет огромного списка или очень маленьких ключей, log (N) обычно меньше k, но редко бывает намного больше. Таким образом, выбор универсального алгоритма сортировки с производительностью среднего случая O (N log N) не обязательно хуже, чем использование сортировки по основанию.

Исправление: как @Mehrdad указал в комментариях, приведенный выше аргумент неверен: либо размер ключа постоянен, тогда сортировка по основанию системы счисления равна O (N), либо размер ключа равен k, затем быстрая сортировка - O (k N log N). Так что теоретически у поразрядной сортировки действительно лучшая асимптотическая среда выполнения.

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

• сортировка по основанию системы счисления: c1 k N

• быстрая сортировка: c2 k N log (N)

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

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

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

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

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

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

при сортировке int32s я выбираю систему счисления 256, поэтому k = log (256, 2 ^ 32) = 4, что значительно меньше, чем log (2, n)

и в моем тесте radix sort в лучшем случае в 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 не является сортировкой на основе сравнения и может сортировать только числовые типы, такие как целые числа (включая адреса указателей) и числа с плавающей запятой, и немного сложно переносимо поддерживать числа с плавающей запятой.

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

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

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

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

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

Другой - последовательный доступ с удобством кеширования с использованием списка индексов. Если индексы просматриваются много раз, производительность часто повышается, если я заранее сортирую их по основанию, чтобы обход выполнялся в последовательном, а не в случайном порядке. Последний мог перемещаться по памяти зигзагами, вытесняя данные из строк кэша только для того, чтобы повторно загружать одну и ту же область памяти в одном и том же цикле. Когда я сначала сортирую индексы перед повторным обращением к ним, это перестает происходить, и я могу значительно уменьшить количество промахов в кеше. На самом деле это мое наиболее частое использование для сортировки по основанию, и это ключ к тому, чтобы моя 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 ++ или qsort C ++, что определенно привело бы к очень очевидным сбоям в частоте кадров. Я даже слышал о людях, реализующих радикальную сортировку с помощью SIMD, хотя понятия не имею, как им это удалось. Я недостаточно умен, чтобы придумать такое решение, хотя даже моя наивная небольшая сортировка по основанию системы счисления работает довольно хорошо по сравнению со стандартными библиотеками.

k = "длина самого длинного значения в массиве для сортировки"

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

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

k * n = n^2 (if k = n)

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

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

Вот ссылка, которая сравнивает быструю сортировку и радикальную сортировку:

Является ли сортировка по основанию счисления быстрее, чем быстрая сортировка для целочисленных массивов? (да, 2-3 раза)

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

своего рода вопрос:

Что быстрее на тех же данных; сортировка O (n) или сортировка O (nLog (n))?

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

Одним из примеров может быть сортировка очень большого набора или массива целых чисел. Радиксная сортировка и любые другие сортировки распределения типов выполняются чрезвычайно быстро, поскольку элементы данных в основном помещаются в очередь в массив очередей (максимум 10 очередей для LSD-сортировки по основанию) и переназначаются в другое место индекса тех же входных данных для сортировки. Вложенных циклов нет, поэтому алгоритм имеет тенденцию вести себя более линейно, поскольку количество входных целых чисел, подлежащих сортировке, становится значительно больше. В отличие от других методов сортировки, таких как крайне неэффективный метод пузырьковой сортировки, поразрядная сортировка не реализует операции сравнения для сортировки. Это простой процесс переназначения целых чисел на разные позиции индекса до тех пор, пока ввод не будет окончательно отсортирован. Если вы хотите протестировать LSD-сортировку по основанию для себя, я написал ее и сохранил на github, которую можно легко протестировать в онлайн-среде js ide, такой как песочница для кодирования красноречивого javascript. Не стесняйтесь поиграть с ним и посмотреть, как он ведет себя с разными числами n. Я тестировал до 900 000 неотсортированных целых чисел со временем выполнения <300 мс. Вот ссылка, если вы хотите поиграть с ней.

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

в Integer 32bit Sort он будет выполнять быструю сортировку 7-10 раз, но на элементах 1b потребуется заметная память, например, несколько ГБ. Таким образом, вы можете сначала использовать сортировку Radix или Counter только в том случае, если ваши данные n большие, но исходные значения в данных маленькие, или вы можете использовать сортировку любого огромного целочисленного списка, когда вы можете обменять память на скорость