软件性能优化那些事( 三 ) _优化

另一个例子是二叉树，这就是链表的一个使用场景。二叉树是一种树状结构，其中平衡二叉树在插入与删除的过程中只要移动logn次就能找到自己的新位置，而且代码简单易于维护（不容易写错也是工程中一个重要的考虑点，如果写得代码过于复杂就要反思下是否使用错了数据结构）。比如：红黑树就是一个综合性能很好的平衡二叉查找树；它是一个动态的数据结构，可以在动态添加与查找过程中稳定在O(logn)量级；在Linux内核中大量使用；而且在Java中的ConcurrentHashMap在冲突大的情况下，冲突元素大于8也会升级成红黑树存储冲突元素，来平衡工程与算法效率之间的矛盾。
当然，数据结构是可以融合的，比如Java中的LinkedHashMap就是融合了数组、哈希表与链表的优秀实践。普通的哈希表因为通过哈希函数将元素链接到数组的索引号上面，实现高速的查找性能，但是丢失了元素的插入顺序，而有时候我们需要这个顺序性来实现特殊的需求，比如缓存淘汰策略；而如果使用链表，形成一个插入的队列，先插入的在队列头，后插入在队列尾部；但是这样虽然保存了插入的顺序但是丢失了查找性能；为了平衡，我们可以在哈希表的基础上，每个元素再增加一个指针用来连接前后插入的元素，形成队列，这样没插入一个元素不仅在哈希表上挂载新的索引点，还要将新元素挂接到队列的尾部，而每一步都是O（1）的开销，是可以接受的，这就是LinkedHashMap的实现原理。
算法设计技术算法设计技术是使用数据结构解决实际问题的技术，就好比化合物特性研究与化学工程的关系，一个是偏重科学特性的研究，一个是解决实际问题。为了能够让科学能够指导生产，能够造福世间，必须将科学落地，那么这个过程中最重要的一步就是对实际问题的建模，建模是对问题的模拟，越准确越能够解决好问题。那么，在算法设计层面有哪些建模方式呢？大体可以分为三个：

蛮力算法
贪心算法
分治算法
动态规划

其中，蛮力算法是对问题建模的初期阶段，是对问题的程序再现，追求的是定性，性能不一定重要，但是问题描述没问题；分治与贪心是在蛮力基础上的一次降阶，往往可以将问题优化到O(nlogn)的规模以内；而动态规划可以进一步将问题的阶降到O(n)级别。降阶是设计算法的初衷，前提是问题本身计算的各个阶段是有冗余的，有重复计算的地方，而找到这个重复的点并不容易，就拿动态规划来说吧，虽然有极致的性能但是发现递推方程并不容易，当然这一切都要经过严格的数学证明才行，这就更加难能可贵。我们这里没有考虑空间的优化，往往降阶的过程中最好保证空间的复杂度不会激增，这样才会有效。这方面我们不展开了，有很多资料可以参考，其中我推荐屈婉玲教授的算法设计分析「链接」。
写在最后【软件性能优化那些事】细心的你可能会发现，为什么没有讲多线程？多线程也是常用的优化手段啊。对，工程上多线程往往可以优化程序的运行效率，但是这里有个基础就是硬件的资源并没有被充分利用，也就是说，如果因为IO导致CPU利用率不足，当然我们就要想办法去构建可以充分利用硬件资源的方法，而多线程、多路复用这些技术都是为了提高硬件的利用“带宽”的技术，所以并不在我们讨论范围之内。这篇文章还有更加详细的另一篇姐妹篇，在这里「链接」，希望对你有所帮助。