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

问题描述

我看到很多地方说的快速排序是好事，因为它适合缓存相关的东西，如维基说：

  

此外，快速排序的顺序和本地化的内存引用了缓存的正常工作

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

谁能给我这个要求一些见解？快速排序是如何与缓存？通常用什么方法在语句缓存？为什么快速排序是一个高速缓存更好？

感谢

解决方案

快速排序改变数组就地 - 数组中，它正在对[不像归并排序，例如 - 这为它创建一个不同的数组。因此，它适用的参考 局部性的原则。

缓存从多种好处访问在存储器中的相同的地方，由于只有第一访问需要被实际采取从存储器 - 的访问的其余部分从高速缓存，这是更快的存取存储器取<。 / P>

归并排序，例如 - 需要更多的内存[RAM]访问 - 因为每一个配件阵列创建 - 再次访问RAM

树木甚至更糟 - 因为2个连续的在一棵树上访问不太可能接近对方。 [缓存填充块，因此对于顺序访问 - 仅在该块中的第一个字节是一个命中，其他的是一个命中。

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

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?

Thanks

解决方案

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.

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

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屋！