第1章 算法真的很重要
第2章 算法的数学原理
第3章 模式和领域
第1章 算法真的很重要
算法真的很重要！在哪些情况下使用哪种算法会给你编写的软件的性能带来巨大的差异。如果你不信的话，那么请看看Gary是怎么通过一些小小的分析，选择了一个正确的算法，扭转了整个败局[1]。
Gary曾经在一个有着很多天才软件开发者的公司工作。和大多数有着很多天才的组织一样，这里有着层出不穷的伟大想法，这些天才们将这些伟大想法实现并且集成到了软件产品中。例如Graham，他从公司创立之初就加入了这个公司。Graham曾经思考过一个问题：如何知道一个程序是否存在内存泄漏，这是当时C和C++程序都存在的一个问题。如果一个存在内存泄漏的程序运行足够长时间，那么这个程序会由于内存耗尽而崩溃。任何一个存在此类问题的程序都不支持自动内存管理和垃圾回收。
Graham决定编写一个库，以包装操作系统的内存分配以及回收函数，例如malloc、free，还有他自己的函数。Graham的函数将每次内存的分配以及回收都记录在一个特定的数据结构中，这样在程序结束之后，程序员能够查询到这些记录。这些包装函数记录这些信息，并且调用操作系统函数来进行内存管理。Graham只花了几个小时就实现了这个库而且能够正常被调用执行。但是现在有一个问题：调用了Graham的库的程序运行得如此缓慢，以至于没有人会去使用它。这是真的名副其实地缓慢。你可以先启动程序，然后离开去喝一杯咖啡，或许喝一壶咖啡也可以，然后回来，你会看到程序还在缓慢地运行着。这种速度当然不能够接受。
为了解决这个问题，Graham很快就了解了操作系统以及内部工作原理。他是一个极其优秀的程序员，能在一个小时内写出其他程序员需要一天才能写出的代码。他已经在大学学习了算法、数据结构以及其他标准课程，所以这点事情肯定难不倒他。那么为什么使用了这些包装的函数，程序会执行得如此缓慢呢？看来，这就是一个典型的知道如何使程序运行，却不知道如何使程序运行得快的案例。但是像很多具有创新精神的人一样，Graham已经在思考他的下一个程序，而不是回到他的那个内存泄漏程序中继续寻找问题。于是，他希望Gary检查一下这个库，看看能不能修复运行缓慢的问题。Gary是一个编译以及软件工程方面的能手，他擅长精炼代码，使得它们可供发布。
在开始深入代码之前，Gary希望先和Graham谈谈这个程序。这样的话，他能够更好地理解Graham如何构造他的解决方案以及为什么他选择了这样的实现方式。
注意：在继续读下去之前，想想如果是你，你会问Graham一些什么。然后在接下来的部分，看看你是否能够得到和Gary相同的信息。
理解问题
解决问题最好从大局观开始：理解问题，找出潜在原因，然后深入挖掘细节。如果你觉得你知道原因，然后决定解决这个问题，那么你可能会出错，或者你也许不会发现其他更好的答案。Gary首先希望Graham能够描述这个问题以及他的解决方案。
Graham说他的目的是希望能够知道一个程序是否存在内存泄漏。他想知道这个问题答案的最好方法是记录所有被程序分配的内存，不管这些内存是否在程序终止之前被释放掉了，同时也记录用户的程序在哪儿请求内存分配。他的解决方案是构建一个包含三个函数的小型库。
malloc
一个包装了系统内存分配函数的函数。
free
一个包装了系统内存回收函数的函数。
exit
一个包装了系统退出函数的函数。
那就写一个使用了这个库的程序来进行测试吧，在程序中调用库中自定义函数而不是系统函数。自定义的malloc和free将会记录每一次内存分配和释放。当程序测试结束的时候，如果记录中，每一个内存分配接下来都有相对应的内存释放，那么就证明没有内存泄漏。如果存在内存泄漏，那么Graham的函数将会记录相关信息以供程序员参考。当调用自定义的exit函数的时候，在程序实际退出之前，将会显示内存的分配释放记录。Graham将他的解决方案用图表示出来，如图1-1。
图 1-1 Graham的解决方案描述貌似已经很清楚了。除非Graham在他包装了系统函数的代码中犯了一些相当严重的错误，否则还真的很难想象在包装的代码中存在性能问题。如果存在的话，那么所有程序的缓慢程度都应该与调用的次数成比例。于是Gary询问Graham测试过的程序是否存在性能差异。Graham解释说，通过性能剖析发现，那些小的程序通常能够在一个勉强可以接受的运行时间内，不管这些程序是否有内存泄漏。但是，那些需要进行大量处理工作和有内存泄漏的程序运行起来慢得不像话。
[1]本文涉及的人员以及组织名均被改变以保护隐私，避免不必要的法律纠纷。