У меня есть 10^4 числа в диапазоне 10^12, каково оптимальное количество бункеров, которые будут использоваться в сортировке радикса? Как определить лучший размер бункера в сортировке radix?Каков оптимальный размер бункера для сортировки по радиусу?
Это компромиссное пространство. Чем больше бункеров вы используете, тем больше памяти вам нужно, но вам потребуется меньше проходов. Так что это действительно зависит от того, как вы определяете «оптимальный».
Также больше бинов = меньше времени не обязательно выполняется из-за эффектов кеша и потому, что в конце каждого прохода необходимо прокладывать бункеры. Таким образом, количество элементов может также сыграть важную роль в этом решении. –
Big bin может ввести лишнюю трату времени для инициализации, а размер кэша причин может быть пропущен. – minorlogic
Ну 10^12 ~ 2^40, так что попробуйте 2^14, 2^10, 2^8, ... и просто измерьте, что быстрее ... –
Это очень зависит от архитектуры процессора и реализации. Простейший способ, попробуйте разные размеры и измерьте время выполнения. – minorlogic