2.3编程中应知道何时和如何考虑可伸缩性
摘要
小心数据的爆炸性增长：不要进行不成熟的优化，但是要密切关注渐近复杂性。处理用户数据的算法应该能够预测所处理的数据量耗费的时间，最好不差于线性关系。如果能够证明优化必要而且非常重要，尤其在数据量逐渐增长的情况下，那么应该集中精力改善算法的O(N)复杂性，而不是进行小型的优化，比如节省一个多余的加法运算。
讨论
本条款阐述了第8条“不要进行不成熟的优化”和第9条“不要进行不成熟的劣化”之间的一个重要的平衡点。所以，这个条款非常难写，不小心就可能将其错误地解释成“不成熟的优化”了。请注意，我们绝不是这个意思。
这一问题的背景和缘起是这样的：内存和硬盘空间一直在以指数速度增长。例如，从1988年到2004年，硬盘空间每年增长112％（差不多每10年增长1900倍），然而即使是摩尔定律也不过是每年增长59％（每10年100倍）。这种现象所导致的一个显然的结果就是，无论今天你的代码如何，明天它都会被要求处理更多的数据——多得多的数据。一个算法如果具有恶性（差于线性）的渐近行为，那么再强大的系统也迟早会在其面前臣服：只需扔给它足够的数据就行了。
防范可能的未来，也就是说我们要避免设计中含有面对更大的文件、更大的数据库、更多像素、更多窗口、更多进程和更多线路上传输的数据时会出现的性能陷阱的现象。C++标准库能够成功防范未来的重大因素之一，就是它已经保证了STL容器操作和算法的性能复杂性。
如何取得平衡呢？使用不够清晰的算法，为永远都不会成为现实的大数据量做好准备，这样的不成熟的优化显然是错误的。但是，对算法复杂性——O(N)复杂性，即计算的代价是所处理数据的元素量的函数故意视而不见，这样的不成熟劣化显然也同样是错误的。
这一问题的建议可以分为两部分。首先，即使不知道数据量是否会大到成为某个特定计算的问题，默认情况下也应该避免使用不能很好地应付用户数据量（可能增加）的算法，除非这种伸缩性不好的算法有明显的清晰性和可读性方面的好处（见第6条）。在这方面，我们遇到的意外情况简直是太多了：编写10段代码，满以为它们永远不会处理巨量的数据集合，而且对于其中的9段代码而言，情况也确实如此，但是第10段代码就让我们遇到了性能陷阱——我们都碰到过这种情况，而且我们知道你们也都会碰到，也许已经碰到了。当然，我们可以进行修补，然后给客户发布补丁，但最好还是能避免这样的尴尬和返工。既然所有事物都是平等的（包括清晰性与可读性），那么应该预先做这些事情。
使用灵活的、动态分配的数据，不要使用固定大小的数组。那种“比我所需要的最大数组还要大”的数组，在正确性和安全性方面都存在严重问题（见第77条）。只有在编译时大小固定不变的数组才是可接受的。
了解算法的实际复杂性。要留心那些不易发觉的陷阱，比如看似线性的算法实际上要调用其他线性操作，结果算法实际上是二次的。（见第81条中的例子。）
优先使用线性算法或者尽可能快的算法。常数时间复杂性的算法，比如push_back和散列表查询，是最完美的（见第76条和第80条）。O(logN)对数复杂性的算法，比如set/map操作和带有随机迭代器的lower_bound和upper_bound，也不错（见第76条、第85条和第86条）。O(N)线性复杂性的算法，比如vector::insert和for_each，也可以接受（见第76条、第81条和第84条）。
尽可能避免劣于线性复杂性的算法。例如，如果面对的是一个O(NlogN)或者O(N2)算法，就必须花费精力寻找替代方案，这样代码才不至于在数据量显著增长的情况下陷入深度激增的性能深潭。例如，这是在第81条中建议使用范围成员函数（通常是线性的）而不是反复调用单元素替代函数的主要原因（后者会很容易在一个线性操作要调用另一个线性操作时变成二次复杂性的，见第81条中的例1）。
永远不要使用指数复杂性的算法，除非你已经山穷水尽，确实别无选择。在决定接受指数算法之前，必须尽力寻找替代方案，因为对于指数算法来说，即使是数据量的有限增加，也会使算法的性能急剧下降。
其次，如果有测试数据表明优化非常必要而且重要，尤其是在数据量不断增加的情况下，那么应该集中精力改善O(N)复杂性，而不是把精力花在节省一个多余加法这样的微观优化上。
总而言之，要尽可能优先使用线性（或者更好的）算法。尽可能合理地避免使用比线性算法差的多项式算法。竭尽全力避免使用指数算法。
参考文献
[Bentley00]§6,§8, Appendix 4 ● [Cormen01] ● [Kernighan99]§7 ● [Knuth97a] ● [Knuth97b] ● [Knuth98] ● [McConnell93]§5.1-4, §10.6 ● [Murray93]§9.11 ● [Sedgewick98] ● [Stroustrup00]§17.1.2