现代硬件的算法？

我再一次发现自己有一套不成立的假设 http://queue.acm.org/detail.cfm?id=1814327。该文章本身介绍了通过修改经过验证的最佳算法来解决虚拟内存问题，从而实现 10 倍的性能提升：

在现代多问题 CPU 上，运行 在一些千兆赫兹时钟频率下， 最坏情况损失近千万 每个虚拟机页面错误的指令。如果你 与旋转盘一起运行， 数字更像是一亿 指示。

O(log2(n)) 算法有什么好处 如果这些操作导致页面错误 和缓慢的磁盘操作？对于大多数 相关数据集 O(n) 甚至 O(n^2)算法，避免页面 故障，就会绕着它转圈。

还有更多这样的算法吗？我们是否应该重新审视我们教育的所有这些基本组成部分？自己写的时候还需要注意什么吗？

澄清：

该算法并不比经过验证的最佳算法更快，因为 Big-O 表示法有缺陷或毫无意义。它更快，因为经过验证的最佳算法依赖于现代硬件/操作系统中不正确的假设，即所有内存访问都是平等且可互换的。

仅当您的客户抱怨您的程序运行缓慢或错过了关键的最后期限时，您才需要重新检查您的算法。否则，请关注正确性、稳健性、可读性和易于维护性。在实现这些目标之前，任何性能优化都是浪费开发时间。

页面错误和磁盘操作可能是特定于平台的。总是profile您的代码以查看瓶颈在哪里。花时间在这些领域将产生最大的好处。

如果您感兴趣，除了页面错误和磁盘操作缓慢之外，您可能还想了解：

• 缓存命中——面向数据的设计
• 缓存命中——减少不必要的 分支/跳跃。
• 缓存预测——缩小循环 它们适合处理器的缓存。

同样，这些项目只有在质量达到、客户投诉以及分析员分析了您的程序之后才会出现。