关键词
工程、选择、权衡
到这里，我们已经学习了大部分常见的数据结构和算法。但是，在我看来，数据结构和算法是非常基础的东西，在实际的工程开发中，我们需要更多地权衡数据结构和算法的使用。下面有六条总结经验：
六条经验.jpg
1.时间、空间复杂度不能和性能划等号
我们在学习数据结构和算法的时候，非常着重地了解了其时间复杂度和空间复杂度的分析。但是这种复杂度分析并不能直接等同于性能。原因如下
复杂度不是执行时间和内存消耗的精确值
还记得复杂度分析的定义吗？复杂度反映了程序随数据规模变化而变化的趋势，在计算复杂度的过程中，我们省略了 低阶、常数、系数 等因素。实际上，这些因素在工程中都是非常重要的指标
代码的执行 时间有时不和时间复杂度成正比
在数据量较小的时候，你看不出 O(n2) 复杂度和 O(nlogn) 复杂度的程序的性能差别，甚至可能前者更快。
2.抛开数据规模谈数据结构和算法都是“耍流氓”
在数据规模很小的时候，普通算法和高级算法的差距非常小。如果这段代码并不是用于构建核心程序，你考虑的主要因素可能是：代码是否够简单、容易维护、容易实现。很多情况下，我们使用最简单的数据结构和最暴力的算法即可。
比如，对于百字以内的字符串匹配，直接使用暴力匹配即可，使用 BM、KMP 这种算法大材小用，还容易产生 bug。
3.结合数据特征和访问方式选择数据结构
在实际开发中，如果我们可以实现对面临的数据有所研究，我们就可以更好地选择合适的数据结构。如何将一个背景复杂、开放的问题，通过细致的观察、调研、假设，理清要处理数据的特征与访问方式，这才是解决问题的重点。清楚了这些，我们才可以构建更加贴合实际的模型，从而找到更加高效的算法。
例如，Trie树 适合进行前缀匹配，但是如果要处理的数据没有多少前缀重合，且字符集很大，这就不适合用 Trie树了。
例如，某些数据具有一定的特征，如果我们想要对这些数据设计一个高效的散列表，就要根据数据特征设计散列函数。
例如，图的存储方式有很多。稀疏图适合用邻接表法存储，稠密图适合用邻接矩阵存储。
4.区别对待 IO 密集、内存密集、计算密集
IO 密集
对 IO 密集型程序，访问磁盘是性能的瓶颈，我们要做到减少对磁盘对访问次数。
例如，递归寻找一个用户的最终推荐人，如果他是被层层推荐而来，我们就需要多次访问数据库。我们可以直接在用户后面构建一个“最终推荐人”的字段，如此一来，只需要访问一次数据库即可。
例如，MySQL 使用 B+树 作为索引，也是为了减少对磁盘的访问次数。
CPU 密集型
CPU 的功能主要时用于计算，CPU 密集型的程序会涉及大量计算（例如人工智能计算），对于这样的程序使用高效的计算方式（位运算）和简化后的计算方式（如在 A* 算法中，使用曼哈顿距离代替欧几里得距离）。
内存密集型
对于内存密集型程序，需要执行的计算操作都比较简单，而性能的瓶颈主要来自于对内存读写次数的减少。（这一点和 IO密集 有点像）
例如，字符串匹配中，字符的比较操作非常简单，如果可以减小字符之间的比较次数，将会提高性能。所以 BM、KMP 算法会比暴力匹配算法更加高效。
5.善用轮子
相信我，你自己写的程序远远没有知名开源软件的轮子好用。
6.不要过度优化
在使用更加优化的算法的时候，要看你的优化是否值得。如果你耗费了大量时间，只是将一个程序提升了 5% 的性能，那你要思考这种优化是否过度了。
当然，这不是说你可以随意选择数据结构和算法，而是我们要准确估计性能收益和耗费的精力的付出的比例。
以上就是全部内容，后会有期
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论