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 мс, как в случае C ++ std::sort или C qsort, что определенно приведет к очень очевидным сбоям в частоте кадров.Я даже слышал о людях, использующих радикальные сортировки с использованием SIMD, хотя я понятия не имею, как им это удалось.Я не достаточно умен, чтобы придумать такое решение, хотя даже мой маленький наивный метод radix довольно хорош по сравнению со стандартными библиотеками.