performance - 内存数据布局 vs 算法性能

Question

内存中数据的布局如何影响算法性能？例如，归并排序以 O(n log n) 的计算复杂度而闻名。但在现实世界的机器中，处理算法会将内存块加载/卸载到 CPU 缓存/CPU 寄存器中，并在其上花费辅助时间。要排序的集合元素可能非常分散在整个内存中，我想知道与对聚集在一起的元素进行排序相比，这会导致性能降低。

是否有必要考虑集合实际上是如何将数据存储在内存中的？

Answer 1

1. 就大 O 符号而言 - 不。您从中读取每个 block 的时间RAM 到 cpu 缓存受一些常数的限制，让它成为 C，所以即使如果您需要在每次迭代中将每个元素从 RAM 加载到缓存，你将需要 O(C*nlogn) 时间，但由于 C 是常量 - 它仍然是 O(nlogn) 时间复杂度。
2. 在现实世界的应用程序中，尤其是在处理实时应用程序时，缓存性能确实可能是一个因素，应该予以考虑，因此访问数据的顺序可能很重要。这是快速排序通常被认为“更快”的原因之一——它往往具有良好的缓存性能。
   此外 - 开发了一些算法来享受“两个世界中最好的” - O(nlogn) 最坏情况下具有更好的常量，例如 Timsort .

但是，根据经验，您通常应该首先实现“简单方法”，然后进行基准测试以查看它是否足够快，如果不够快则进行分析 - 并优化瓶颈。如果您尝试优化每一段代码以获得最佳缓存性能 - 您可能永远都写不完。