Лучшая основа для Radix Sort

Я прочитал несколько источников по этой теме. Однако мне сложно понять, что именно означают эти формулы. Кажется, что Radix Sort является линейным, когда b = n. Значит ли это, что я должен установить базу равной длине массива?

Если у меня есть массив из 100 миллионов целых чисел в диапазоне от 0 до 1 миллиарда, я должен выбрать базу 100 миллионов?

Если это не так, пожалуйста, постарайтесь заглушить это для меня. Большинство примеров с Radix Sort, которые я могу найти, имеют только базу 10 или базу 2, поэтому либо они медленные для массивов больше 10 или 2 соответственно, либо я просто не понимаю.

Спасибо за любую помощь.


performance sorting algorithm radix radix-sort
person user2587878    schedule 18.04.2014    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Сортировка Radix на самом деле не является линейной по времени, если вы устанавливаете в качестве основы количество записей в массиве. Время выполнения поразрядной сортировки - O (n log b U), где n - общее количество элементов в массиве, b - выбранное основание, а U - максимальное число в массиве. Если вы установите b = n, то время выполнения будет O (n log n U) = O (n log U / log n). Асимптотически это действительно здорово!

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

Вероятно, лучшей идеей было бы профилировать программу по различным базовым вариантам и посмотреть, что лучше всего. По опыту, когда я пробовал использовать сортировку по основанию n, я обнаружил, что она работает медленнее, чем стандартная сортировка по основанию 2 на больших входных данных, в основном из-за проблем с локализацией. Я бы предположил, что 2 не является идеальной базой для сортировки по основанию, но что-то большое, например 2 16, может начать страдать от промахов кеша. Попробуйте поэкспериментировать и дайте нам знать, что вы найдете!

Надеюсь это поможет!

person templatetypedef    schedule 04.09.2014
comment
Привет, вы сказали, что использование сортировки по основанию n по основанию n, я обнаружил, что это медленнее, чем стандартная сортировка по основанию 2 для больших входных данных. И тогда вы говорите: я бы предположил, что 2 не является идеальной базой для сортировки по основанию. когда base-2 быстрее, чем base-n, почему вы говорите последнее утверждение? - person CKM; 02.08.2015
comment
@chandresh Это утверждение в первую очередь имелось в виду, поскольку у меня нет никаких априорных оснований полагать, что два - лучшее из всех возможных оснований. Вполне возможно, что это лучший вариант, но, не проведя дополнительных тестов, я не могу сказать наверняка. - person templatetypedef; 02.08.2015
comment
OK. Я хотел бы получить ваши комментарии по поводу моего вопроса здесь: cstheory.stackexchange.com/questions/32128/ - person CKM; 02.08.2015

arrow_upward
1
arrow_downward

Для вашего случая лучшая база сортировки Radix - 2 ^ 16 (65536) или 2 ^ 8 (256). в 1-м случае вы отсортируете массив по два хода для каждого элемента, во 2-м - по 4 хода.

person olegarch    schedule 04.09.2014
comment
Не могли бы вы пояснить, почему это значение будет лучшим? - person templatetypedef; 07.09.2014
comment
Из-за этого составляет 1/2 или 1/4 размера sizeof (int). С 256 вы будете использовать меньше дополнительной памяти, но всего 4 хода. С 256 * 256 вы получите результат всего за 2 хода (для eqch int), но вам понадобится значительная дополнительная память для счетчиков: sizeof (int) * 2 * 256 * 256 байт = 512 МБ. - person olegarch; 07.09.2014