quicksort與緩存有什麼關係？

Question

我看到很多地方說的快速排序是一件好事，因爲它適合於高速緩存相關的東西，如維基說

此外，快速排序的順序和本地化內存引用了緩存

正常工作http://en.wikipedia.org/wiki/Quicksort

任何人都可以給我一些關於這種說法的見解嗎？快速排序與緩存有什麼關係？通常情況下，該語句中的緩存是什麼意思？爲什麼quicksort更適合緩存？

感謝

Answer 1

快速排序更改數組inplace - 它正在處理的數組[不同於合併排序，例如 - 爲它創建一個不同的數組]。因此，它適用locality of reference的原則。

由於只有第一次訪問需要實際從內存中獲取 - 其餘訪問都是從緩存中獲取的，所以對內存中的同一位置進行多次訪問對緩存有好處，這對訪問內存來說要快得多。

合併排序例如 - 需要更多的內存[RAM]訪問 - 因爲您創建的每個配件陣列 - 正在再次訪問RAM。

樹更糟 - 因爲樹中的2個順序訪問不可能彼此靠近。 [高速緩存填充塊，因此對於順序訪問 - 只有塊中的第一個字節是「未命中」，其他則是「命中」]。

Answer 2

什麼進入高速緩存由算法幾乎猜測你將很快使用基於您目前正在請求什麼什麼決定。這通常意味着彼此接近的內存塊，比如數組。

經過幾次迭代後，quicksort將使用完全適合緩存的塊，這大大提高了性能。 （比較說，選擇排序，這可能是訪問與大多數操作相隔很遠的內存位置。）

Answer 3

Quicksort是一種就地排序算法。它通過使用交換將元素移動到樞軸的左側和右側。每次交換髮生時，高速緩存行都可能被加載，並且隨後的交換將從同一高速緩存行發生。