Почему Radix Sort не используется чаще?

Он стабилен и имеет временную сложность O (n). Это должно быть быстрее, чем алгоритмы, такие как Quicksort и Mergesort, но я вряд ли когда-либо видел его использование.

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

Также вы должны понимать, что O (f (n)) действительно означает в порядке K * f (n), где K - некоторая произвольная постоянная. Для радикальной сортировки это K оказывается довольно большим (по крайней мере, порядок количества бит в отсортированных целых числах), с другой стороны, быстрая сортировка имеет один из самых низких значений K среди всех алгоритмов сортировки и средняя сложность n * log (n). Таким образом, в реальной ситуации быстрая сортировка будет очень часто быстрее, чем сортировка по основанию.

Большинство алгоритмов сортировки общего назначения. Имея функцию сравнения, они работают с чем угодно, а алгоритмы, такие как Quicksort и Heapsort, будут сортировать с O (1) дополнительной памятью.

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

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

Очень редко ключи, по которым вы сортируете, на самом деле являются целыми числами в известном разреженном диапазоне. Обычно у вас есть буквенные поля, которые выглядят так, как будто они поддерживают несравнительную сортировку, но поскольку строки реального мира не распределены равномерно по алфавиту, это не работает так, как должно быть в теории.

В других случаях критерий определяется только оперативно (учитывая две записи, вы можете решить, что будет первым, но вы не можете оценить, насколько «далеко» вниз по шкале находится изолированная запись). Таким образом, этот метод часто неприменим, менее применим, чем вы думаете, или просто не быстрее, чем O (n * log (n)).

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

Базовым примером является радикальная сортировка точек по заданному измерению как часть поиска или медианного разбиения или быстрый способ обнаружения совпадающих точек, фрагментов глубины или радикальная сортировка массива индексов, используемых в нескольких циклах, чтобы обеспечить более дружественный к кэшу доступ паттерны (не возвращаться назад и вперед в памяти, а только возвращаться и перезагружать ту же память в строку кэша). По крайней мере, в моем домене есть очень широкое применение (компьютерная графика) только для сортировки по 32-битным и 64-битным цифровым ключам фиксированного размера.

Я хотел бы сказать одну вещь: сортировка по основанию может работать с числами и отрицаниями с плавающей точкой, хотя сложно написать версию FP, которая была бы настолько переносимой, насколько это возможно. Кроме того, хотя это O (n * K), K просто должно быть числом байтов размера ключа (например, миллион 32-битных целых чисел обычно занимал бы 4 прохода размером в байт, если в корзине 2 ^ 8 записей ). Схема доступа к памяти также имеет тенденцию быть более дружественной к кэшу, чем квикорты, хотя для этого обычно требуется параллельный массив и небольшой массив сегментов (обычно второй может нормально помещаться в стеке). QS может выполнить 50 миллионов операций перестановки, чтобы отсортировать массив из миллиона целых чисел со случайными шаблонами произвольного доступа. Радикальная сортировка может сделать это за 4 линейных, дружественных к кэшу передачи данных.

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

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

Некоторые тесты:

Sorting 10000000 elements 3 times...

mt_sort_int: {0.135 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

mt_radix_sort: {0.228 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

std::sort: {1.697 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

qsort: {2.610 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

И это только с моей наивной реализацией ( mt_sort_intэто также радикальная сортировка, но с более быстрой ветвью кода, учитывая, что он может предполагать, что ключ является целым числом). Представьте, насколько быстрой может быть стандартная реализация, написанная экспертами.

Единственный случай, когда я нашел радикальную сортировку хуже, чем в действительно быстром, основанном std::sortна С ++ сравнении, был для очень небольшого числа элементов, скажем, 32, и я считаю, что в этот момент я std::sortначинаю использовать сортировки, лучше подходящие для наименьшего числа элементов, таких как heapsorts или вставка сортирует, хотя в тот момент моя реализация просто использует std::sort.

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

В реальном мире я на самом деле реализовал сортировку radix один раз, Это было в старые времена, когда память была ограничена, я не мог перенести все свои данные в память сразу. Это означало, что количество обращений к данным было гораздо важнее, чем O (n) против O (n log n). Я сделал один проход по данным, распределяя каждую запись в корзину (по списку записей, в которых она находилась, фактически ничего не перемещая). Для каждого непустого контейнера (мой ключ сортировки был text, было бы много пустые контейнеры) Я проверил, могу ли я действительно перенести данные в память - если да, внесите их и используйте быструю сортировку. Если нет, создайте временный файл, содержащий только элементы в корзине, и рекурсивно вызовите процедуру. (На практике несколько корзин переполнится.) Это вызвало две полные операции чтения и одну полную запись в сетевое хранилище и примерно 10% от этого в локальное хранилище.

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

Если все ваши параметры являются целыми числами и если у вас более 1024 входных параметров, тогда сортировка по основанию всегда быстрее.

Зачем?

Complexity of radix sort = max number of digits x number of input parameters.

Complexity of quick sort = log(number of input parameters) x   number of input parameters

Так что сортировка по основанию быстрее, когда

log(n)> max num of digits

Максимальное целое число в Java - 2147483647. Длина 10 цифр

Так что сортировка по осям всегда быстрее, когда

log(n)> 10

Поэтому радикальная сортировка всегда быстрее, когда n>1024