现代硬件的算法？

Question

再一次,我发现自己有一套破碎的假设.通过修改经验证的最优算法来考虑虚拟内存,文章本身的性能提升了10倍:

在一个现代多发出CPU上,以几千兆赫的时钟频率运行,最坏情况下每个VM页面故障损失近1000万条指令.如果您使用旋转磁盘运行,则该数字更像是1亿条指令.

如果这些操作导致页面错误和磁盘操作速度慢,那么O(log2(n))算法有什么用呢？对于大多数相关数据集,O(n)或甚至O(n ^ 2)算法可避免页面错误,它将围绕它运行圆圈.

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

澄清:

所讨论的算法并不比经过验证的最佳算法快,因为Big-O符号存在缺陷或无意义.它更快,因为经过验证的最优算法依赖于在现代硬件/操作系统中不正确的假设,即所有内存访问都是相同且可互换的.

Answer 1

当客户抱怨程序运行缓慢或缺少关键截止日期时,您只需要重新检查算法.否则,请注重正确性,稳健性,可读性和易维护性.在实现这些项目之前,任何性能优化都是浪费开发时间.

页面错误和磁盘操作可能是特定于平台的.始终对代码进行概要分析,以了解瓶颈所在.花时间在这些领域将产生最大的好处.

如果您对页面错误和磁盘操作速度感兴趣,可能需要注意:

• 缓存命中 - 面向数据的设计
• 缓存命中 - 减少不必要的分支/跳转.
• 缓存预测 - 收缩循环,使它们适合处理器的缓存.

同样,这些项目只有在达到质量,客户投诉和分析师分析您的计划之后.

Answer 2

一件重要的事情是要认识到 big-O 表示法（谈论运行时复杂性）最常见的用法只是故事的一半- 还有另一半，即空间复杂度（也可以使用 big-O 表示），它可以也非常相关。

一般来说，如今，内存容量的进步已经超过了计算速度的进步（对于单核 - 并行化可以解决这个问题），因此较少关注空间复杂性，但这仍然是一个应该牢记的因素，特别是在具有内存更有限或处理大量数据时。