Как быстрая сортировка связана с кешем?

Question

Я видел много мест, где быстрая сортировка хороша, потому что она подходит для вещей, связанных с кэшированием, таких как сказано в вики

Кроме того, последовательные и локализованные обращения к быстрой сортировке хорошо работают с кешем

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

Может ли кто-нибудь дать мне некоторое представление об этом утверждении? Как быстрая сортировка связана с кешем? Обычно, что означает, что кэш в заявлении? Почему быстрая сортировка лучше для кеша?

Спасибо

Answer 1

быстрая сортировка изменяет массив на месте - в массиве, с которым он работает [в отличие от сортировки слиянием, например, - который создает для него другой массив]. Таким образом, применяется принцип местность отсчета .

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

Например, сортировка слиянием - требует гораздо больше обращений к памяти [RAM] - поскольку каждый создаваемый вами вспомогательный массив снова обращается к RAM.

Деревья еще хуже - поскольку два последовательных доступа к дереву вряд ли будут близки друг к другу. [Кэш заполняется в блоках, поэтому для последовательного доступа - только первый байт в блоке является «промахом», а остальные - «попаданием»].

Answer 2

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

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

Answer 3

Быстрая сортировка - это алгоритм сортировки на месте. Он перемещает элементы влево и вправо от оси с помощью свопов. Каждый раз, когда происходит обмен, вполне вероятно, что строка кэша загружена, и последующий обмен будет происходить из той же строки кэша.