Оптимизация сортировки слиянием по размеру строки кэша?

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

В то время как BigO предполагает обратное, его предложение кажется интуитивно понятным. Может ли кто-нибудь подтвердить или опровергнуть это и/или предоставить дополнительную информацию о том, как и почему это работает?

Спасибо за помощь, ребята!


arrays caching sorting mergesort insertion-sort
person Harsha Nori    schedule 16.10.2015    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Комбинация сортировки вставками для создания небольших тиражей с последующим переключением на сортировку слиянием называется сортировкой по времени. Вики-статья:

http://en.wikipedia.org/wiki/Timsort

person rcgldr    schedule 16.10.2015

arrow_upward
0
arrow_downward

Ну, (несколько абстрактный) ответ заключается в том, что Big-O полезен только для больших чисел: он отбрасывает постоянные множители: O(n)=O(3n), он отбрасывает члены более низкого порядка: O(n²+3n) = О (n²). Так что да, по нотации Big-O этого не скажешь.

Кроме того, нотация Big-O обычно используется в очень простой модели, где каждая «операция» стоит всего 1, и она не знает о кэшах.

Вот почему модель не говорит вам, что это может быть полезно. Я думаю, вы могли бы взглянуть на «Сортировку и поиск» Дональда Кнута, где он проводит анализ времени выполнения до более низких терминов (но все еще не учитывает кеш, IIRC) на вымышленном языке ассемблера.

person Ulrich Schwarz    schedule 16.10.2015

arrow_upward
0
arrow_downward

Анализ сложности с использованием O (Ω, Θ и т. д.) предназначен только для описания того, как алгоритм работает при увеличении размера входных данных. Если вы посмотрите на фактическую функцию, вы увидите, что постоянные факторы становятся менее важными по мере роста входных данных. В целом размер ввода доминирует над функцией.

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

Сортировка вставками довольно эффективно использует кеш, как правило, до тех пор, пока данные помещаются в кеш. Поскольку он последовательный, он также хорошо взаимодействует с предиктором. Обе часто являются причинами, по которым лучше использовать меньшие входные данные. Другим хорошим примером является QuickSort, который технически является O(n^2), но по-прежнему часто используется на практике, поскольку имеет лучшие характеристики кэша. TimSort (по умолчанию в Python и Java) также использует сортировку вставками для небольших входных данных.

person Jason    schedule 16.10.2015
comment
В моей системе Intel 2600K 3,4 ГГц время сортировки 4 194 304 64-битных целых чисел без знака псевдослучайных данных: сортировка по основанию - 203 мс; сортировка слиянием — 297 мс; Microsoft std::sort — 344 мс; Microsoft std::stable_sort — 375 мс. std::sort — это начальная сортировка. std::stable_sort — это сортировка слиянием снизу вверх, в которой используется временный массив размером в 1/2 размера исходного массива, делается несколько дополнительных копий и завершается этап слияния. - person rcgldr; 17.10.2015
comment
Сортировка подсчетом с использованием растрового изображения способна выполнить сортировку на моем ноутбуке (процессор x86_64 Intel(R) Core(TM) i7-3632QM @ 2,20 ГГц) за 250 мс, даже если компилятор генерирует неверный код (314 мс для std::sort). У него больше накладных расходов на память, чем у вводной сортировки, но он псевдо-безветвящийся, как сортировка по основанию (1/4 пропущенных ветвей), поэтому он по-прежнему обеспечивает более высокую пропускную способность инструкций (2/цикл против 1,9/цикл). Я не уверен, почему сортировка слиянием превосходит ее. Я думаю, что расширенная сортировка также показала, что в некоторых сценариях она превосходит интро-сортировку. - person Jason; 17.10.2015