快速排序如何与缓存相关？ [英] How is quicksort is related to cache?

问题描述

我已经看到很多地方说quicksort是很好的，因为它适合缓存相关的东西，例如在维基中说：

I have seen many places say quicksort is good because it fits to cache-related stuff, such as said in wiki

此外，快速排序的顺序和本地化内存引用可以很好地与缓存一起使用

Additionally, quicksort's sequential and localized memory references work well with a cache

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

有人可以给我一些关于这个说法的洞察力？快速链接如何与缓存相关？通常意味着缓存在语句中？为什么quicksort更适合缓存？

Could anyone give me some insight about this claim? How is quicksort related to cache? Normally what means that cache in the statement? Why quicksort is better for a cache?

谢谢

推荐答案

quicksort更改数组inplace - 在它正在处理的数组中[不同于合并排序，例如，为其创建不同的数组）。因此，它适用了参考地点的原则。

quicksort changes the array inplace - in the array it is working on [unlike merge sort, for instance - which creates a different array for it]. Thus, it applies the principle of locality of reference.

缓存从对存储器中相同位置的多次访问中获益，因为仅需要从存储器实际获取第一次访问 - 其余访问取自缓存，访问内存的速度要快得多。

Cache benefits from multiple accesses to the same place in the memory, since only the first access needs to be actually taken from the memory - the rest of the accesses are taken from cache, which is much faster the access to memory.

合并排序为实例 - 需要更多的内存[RAM]访问 - 因为您创建的每个附件数组 - 正在访问再次是RAM。

Merge sort for instance - needs much more memory [RAM] accesses - since every accessory array you create - is accessing the RAM again.

树更糟糕 - 由于树中的2次连续访问不太可能彼此靠近。 [缓存填充块，所以对于顺序访问，只有块中的第一个字节是miss，而其他的是hit]。

Trees are even worse - since 2 sequential accesses in a tree are not likely to be close to each other. [Cache is filled in blocks, so for sequential accesses - only the first byte in the block is a "miss" and the others are a "hit"].

这篇关于快速排序如何与缓存相关？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！