3.1 什么是算法效率

算法效率主要指的是算法的时间复杂度，在第2章中提到了一种图算法的分类方式，即按照从恒定时间、线性、多项式到指数级复杂度的自低到高的多级分类。需要指出的是，不同的底层计算资源的规模是会影响算法的执行效率的，例如可并发的规模。另外，也需要关注算法的空间复杂度，即用于完成算法执行所需要的存储空间，包括外存与内存等。

评价算法效率的“金指标”就是在相同计算与存储资源条件下，运行时耗越低，算法实现效率越高。换言之，如果有更高配置的计算（及存储）资源，就能够实现更高的计算效率。

算法效率的提升涉及算法逻辑优化、数据结构优化、系统架构优化、代码实现优化等多个方面。但是所有的优化形式在本质上可以总结为两个要点：一是尽可能地实现并发，二是尽可能地让存储的数据靠近计算资源。

图3-1中的7层存储架构示意了算法效率提升的金字塔，可以简单地理解为：

图3-1 多级存储架构与计算效率金字塔

1）网络化存储的计算效率是最低的，特别是当数据之间存在关联关系时。在一个大规模分布式的系统中，多个存储节点需要不断地交换或迁移数据，所造成的时耗是惊人的。而这个时候，即便再高的网络带宽也可能于事无补。举个简单的例子，假设用10Gb/s的速度传输100万个4KB的小文件与传输一个4GB的文件（在文件大小层面，4GB=4KB×104），两者的传输时间差异是多少？答案是前者的时耗至少是后者的100倍以上，这是多实例间大量频繁的I/O操作使然。

2）磁盘的效率较网络存储已经大幅（10倍）提升，因为它已经是一种存储与计算较紧密耦合的架构模式，尽管磁盘I/O依然存在，但是不再需要考虑网络造成的延迟。

3）固态硬盘（包括大容量固态硬盘和高性能固态硬盘）的特点是规避了传统磁盘的可移动的机械部件，而获得了10～100倍于磁盘存储访问的性能提升。尽管固态硬盘经过多次擦写后可能会出现数据遗失的问题，但是在真正追求高性能的系统中，可以通过各种数据冗余与保护机制来规避这个问题。如果只因为担心固态硬盘在经过7000次擦写后可能会遗失数据就彻底规避使用，无异于因噎废食。

4）持久化内存（Persistent Memory）是图3-1的7层堆栈中出现最晚的一种产品形态，本质上它融合了固态硬盘与动态随机存储内存（DRAM）的特点，同时兼具了数据持久化的能力与内存级的访问速度。持久化内存相对于固态硬盘也有了10倍的性能提升。

5）内存相对于固态硬盘有100～1000倍的读写性能提升，但是单位价格却便宜10～20倍。从投入产出比上来说，如果你听过“内存就是新的存储”（Memory is the New Disk!）的说法，背后的原因就在这里。

6）多级存储计算架构中的最后一层是CPU，如果觉得CPU仅仅是用来计算的，就显得有些不求甚解了。实际上，现代CPU的架构设计中都会有多级内置缓存，而多级缓存的价值在于每一层都给CPU与内存之间的数据迁移和加载进行了提速，毕竟内存和CPU之间还存在着千倍级的性能差（图3-1中只体现了10倍差异），而每层缓存都大概有10倍的提速效果。

图3-2示意了这种多级存储加速的效果。

❑ 机械硬盘：单次操作延时如果是3ms，进行一个四千万次的迭代操作，延时就变成了120000s，即1.5天，这就是很多批处理操作的耗时都是T+1、T+2的直接原因。

❑ 固态硬盘：可以带来约30倍的性能提升，与上面同样的操作耗时会降低到1个多小时，可以算作T+0的效果。

❑ 内存：在内存上进行同样的操作时，可以获得上千倍的性能提升，这个时候“批处理”的操作已经可以以近实时的方式完成。

❑ CPU缓存：理论上，如果所有的数据都可以在CPU（借助多级缓存的力量）内完成，时间会缩短到毫秒级，如40ms。

图3-2 多级存储加速与并发计算

事实上，在存储与计算加速的道路上，CPU也不是终点，通过对数据结构、系统架构、最大化并发执行等进行优化，还有可能获得更低的耗时与更高的效率。