Как quicksort связан с кешем?

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

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

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

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

Спасибо

Ответы

Ответ 1

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

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

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

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

Ответ 2

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

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

Ответ 3

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