Radix sort в линейном времени по сравнению с преобразованием ввода в нужную базу

Question

Я думал о проблеме линейной сортировки по времени, которая появляется в довольно многих источниках, что позволяет сортировать массив чисел в диапазоне от 0 до n^3-1 в линейном времени ,

Так один из способов сделать это состоит в использовании базисного вида, который обычно проходит в O(wn) где w это максимальный размере слова, заметив, что мы можем получить размер слова 3 для любого числа в этом диапазоне, используя базу n.

И в этом мой вопрос - пока он выглядит нормально на бумаге, на практике конвертируя все числа в базу n, наивный путь займет довольно много времени, возможно, даже больше, чем более поздняя сортировка. Есть ли способ конвертировать в базу n быстрее, чем наивно или как-то обмануть выход из этого ограничения или вам просто нужно жить с ним?

Answer 1

Одно из полезных наблюдений заключается в том, что время выполнения этого алгоритма одинаково, если вы выбираете в качестве базы не число n, а наименьшую мощность, равную двум, большим или равным n. Представим себе, что это число 2 ^k. Теперь, чтобы считывать цифры-цифры ^k, вы можете просто проверить блоки битов размера k в числе, что можно выполнить довольно быстро, используя некоторые сдвиги бит и логические символы AND. Это, вероятно, будет быстрым, даже если ваши номера будут сохранены в виде целых чисел переменной длины, считая, что целое число переменной длины использует некоторую красивую двоичную кодировку.

Answer 2

Идеальный размер для выбора k бит-полей для использования 2 ^k в качестве основы для сортировки radix в зависимости от размера массива, но это не имеет большого значения, менее 10% для выбора r = 8 (1 проход для прохода + 4 байта сортировки), по сравнению с r = 16 (1 проход для чтения + 2 байта сортировки), потому что r = 8 больше подходит для кеша. В моей системе (Intel 2600K 3.4 ghz), для размера массива = 2^20, r = 8 немного быстрее. Для размера массива = 2^24 r = 10.67 (с использованием поля 10,11,11 бит) немного быстрее. Для размера массива = 2^26 r = 16 немного быстрее.

Для целых значных знаков знаковый бит можно переключать во время сортировки по методу radix.

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