CPU效率高的算法？

探查器

首先，当您超越明显的算法效率低下时，想要找到一个不错的分析器。探查器具有以下优点：

1. 向您显示精确的度量（花费的时间，缓存未命中，分支预测错误等）。
2. 追逐最热门的热点将倾向于快速加快您的学习过程，并直觉导致微观层面瓶颈的原因（例如：内存层次结构和分支）。
3. 将使您成为更好的优先事项。它还将教您什么代码不需要优化，这意味着您可以集中精力关注其他指标，例如生产率（可维护性，安全性等）。

对我来说，＃2实际上是很大的一个。直到手头有一个探查器，我才真正开始非常快地学习很多这些东西。通过一种实际的，相当大的项目并查找中间出现的东西，您可以通过这种方式学习很多编程知识。同样，当您逐个追踪一个热点并研究其存在的原因时，使用探查器可以更轻松地学习微效率和计算机体系结构。

记忆体最佳化

除此之外，可能超出算法复杂性（关于可伸缩性而不是某种绝对的性能）的第一件事就是内存效率。

_{注意：这将有点简化，并且不会涉及诸如寄存器分配和堆栈溢出甚至是内存层次结构的非常详细描述之类的编译器设计主题。}

机器和操作系统的工作方式以内存的分层形式建立，范围从绝对最快但最小的内存（寄存器）到绝对最慢和最大的内存（磁盘）。

当访问内存时，系统会将较慢的内存块以较大的对齐块的形式从较慢的内存加载到较快的内存中。例如，操作系统可能会将内存从辅助存储设备分页到4 KB块的物理内存（DRAM）中。

[4 kilobyte chunk][*4 kilobyte chunk][4 kilobyte chunk][...]
// '*' indicates the chunk that's loaded in.

当您请求访问对齐的4 KB块周围的任何地方的虚拟内存时，系统将在该块中分页到DRAM。但是我们还没有完成。通常，在执行任何操作之前，我们必须从DRAM加载到CPU缓存中，而CPU缓存本身又被划分为层次结构。在这些情况下，内存可能会加载到64字节对齐的缓存行块中，如下所示：

[64-byte chunk][64-byte chunk][*64-byte chunk][...]

...因此，内存访问最终以这种方式从DRAM加载到CPU缓存中。当您请求访问这些64字节块之一附近的DRAM中的内存时，整个64字节块将被加载到CPU缓存中。

然后将CPU高速缓存本身划分为一个层次结构（尽管通常都使用相同的高速缓存行大小），然后将内存下移到速度更快但较小的CPU高速缓存中（最快为L1）。最后但并非最不重要的一点是，在执行诸如算术之类的操作之前，L1高速缓存中的内存已加载到寄存器中，例如，对于通用CPU寄存器，其大小可能为64位。在那种情况下，我们最终将我们的CPU高速缓存内存布置在64字节的高速缓存行中：

[64 bits][64 bits][64 bits][*64 bits][64 bits][...]

因此，最后，我们将工作降到最小和最快的内存之后，对寄存器执行了一些算术指令，然后通常将结果移回层次结构。

现在，这有点简化了，以后我可能会为此感到尴尬。但是要记住的是，CPU将内存从较慢的较大区域按对齐的块取到较快的较小区域。它通过连续的少数几个获取内存。这样做的希望是，您最终要多次访问该内存块（空间/时间局部性），然后才能将该存储块逐出。

记忆体最佳化

请牢记这一点，通常要从代码中获得最大性能就需要开始对内存布局和访问进行优先级排序（当然，除了算法和数据结构之外）。没有有效的内存访问，最快的算术指令将无济于事。

这里值得牢记的事情之一是连续数组。连续排列并按顺序模式访问的数据对于这种内存层次结构是理想的。这是因为计算机可能抢占了一块很大的旧内存（页面，缓存行），然后我们依次进行浏览，并在逐出之前以更快的内存形式访问整个内存块。

在收回数据之前使用数据

最坏的情况是，当您最终装入一个很大的旧内存块而只使用其中的一小块，然后在使用其余的内存之前让系统将其逐出。这样的场景可以显示在链接结构（如链接列表和树）中（缺少内存分配器，无法为它们提供更连续的表示），最终我们可能会为节点周围的内存区域加载一大块内存，从而只能访问其中的一个节点。然后驱逐它。

出现这种情况的另一种情况是在托管语言中，每种用户定义的类型都必须单独分配（例如，通过垃圾收集器分配），但必须聚合为基于数组的列表结构。在那种情况下，即使我们存储这些对象的数组，每个对象实际上也通过引用（如指针）来表示，该引用指向内存中的其他位置。

这可能是使用C或C ++之类的语言的最令人信服的原因之一。它们允许用户定义的类型连续聚合以及在堆栈上分配（具有很大的时间局部性）。

TL; DR

如果您想了解更多有关这些主题的信息，建议您调查参考文献的位置。这篇文章也是必须的：http : //lwn.net/Articles/250967/

最后但并非最不重要的一点是，如果我允许花大量时间来回答一个悬赏问题的无耻插件，那么在结构中表示小值的最有效方法是什么？。

但是无论如何，首先要做的是抓探探查器并开始追踪热点。这是最快的学习方式，也是最有效的优化方式。

更新

Jenz很好的回答中的智慧建议也给了我加入免责声明的冲动，因为算法效率仍然是人们最担心的第一件事。我处理过那些整天都在讨论高速缓存效率和多线程的类型，同时又处理了大多数次优的算法，这是无效的优先级划分。作为一个公然的例子，微优化或并行化一百万个元素的气泡排序远没有效果。

在那些只能触摸每个元素（无法降低线性复杂度的方法）的连续情况下，许多内存优化技术往往最能为您提供帮助。例如，需要处理每个粒子的粒子模拟器，必须影响每个像素的图像处理算法，涉及大量矩阵的矩阵乘法。在这些情况下，由于必须处理每个元素，因此无法以算法方式跳过大部分工作并仍然获得相同的结果。在那些时候，内存优化技术甚至可以比并行化更有效，并且可以提供更多并行化功能。

然而，数据结构和算法的核心还存在内存效率问题。纯粹由于内存效率的原因，在实际情况下，数组的快速排序仍然倾向于击败合并排序。甚至在某些情况下，线性运算法则可能会击败线性运算法则，前提是前者的存储效率要高得多。

内存分配器

我之前提到了树和链接列表之类的链接结构的缓存不友好性，但这是假设每个节点都是针对通用分配器分配的（可能不是一次分配所有）。实际上甚至可以使像单链列表之类的结构真正变得更加适用的一件事是使用内存分配器，该内存分配器为其节点提供了原本通常不会缺少的空间局部性。因此，有一些方法可以挖掘您的数据结构并利用内存分配器，并使它们更加有效，而无需实际使用全新的分配器。

还存在诸如展开列表之类的数据结构，由于与链表相比没有算法优势，因此经常被忽略。然而，从内存效率的角度来看，它们提供了更大的好处，在那些我们有两个数据结构具有相似算法复杂性但内存布局差异很大的情况下，赢家往往是拥有更高效内存布局和访问模式的数据结构。展开的列表将元素的数组链接在一起，而不是将单个元素链接在一起，而且，空间局部性强烈支持基于数组的连续表示。

然而，几乎所有的微优化都会降低代码的直接性和可维护性。因此，一般而言，优化的关键是确定优先级，这是探查器至少可以在某种程度上帮助您保持控制的能力（从生产率的角度来看，探查器具有向您展示无法优化的东西的巨大好处，否则您可能会被诱惑。尝试）。