一开始自学数据结构与算法的时候，我的选择了两本教材：《数据结构与算法分析》和《算法设计与分析基础》。一本偏重数据结构，一本偏重算法。两本书都很好。在实际工作中，尽管直接应用到相关知识的场景很少，但是在很多时候可以明确感觉到用到了其中的思想。

教材里对算法复杂度的考量全部都是基于理论上的，所以这些知识在实际应用的时候，也会发现有些不足。

纯粹的理论知识是不足的

举个简单的例子，假设需要在一个List中查找指定对象A。那么写成伪代码就是：

for item in List:
	if A == item:
		return item.index

假设List的实现可以是数组ArrayList或者链表LinkedList。根据数据结构相关理论，两者在当前场景下的时间复杂度均为O(n)。但是能够就此得出结论认为两者的效率是一致的吗？

理论已经无法更近一步证明这个问题。

计算机体系知识也很重要

如果我们再从计算机体系的角度去思考一下：CPU在运算时，会将数据以cache line的结构加载至L1～L3高速缓存处。那么对于ArrayList，总会有一段连续的数组数据同时存在于L1缓存处。以64bit X86处理器为例：

一段cache line的大小是64 byte。
ArrayList实际上是对象指针数组。
64bit JVM中一个对象指针的大小是8 byte。

所以说，L1缓存中至少同时存在连续的8个List成员。而对于LinkedList，因为其中的List成员使用指针来相互指向，实际上松散的存储于内存中。随着各种GC动作，LinkedList的成员在内存中很难保证能够连续的顺序分布在内存中。因此，当CPU读取到一个List成员时，下一个成员未必就在L1缓存中，甚至都有可能在内存中。

根据《性能之巅》提供的参考数据，CPU读取L1缓存数据需要耗费3个CPU周期，读取L2缓存数据需要消耗9个CPU周期，读取L3缓存数据需要消耗43个CPU周期，读取内存RAM需要消耗360个CPU周期。假设，CPU在读取完cache line数据后，发生cache miss的开销为Nmax。这也就是ArrayList读取下一段数组数据的开销，也是LinkedList读取下一个成员的开销。那么我们可以得出结论：

ArrayList的成员读取平均开销na = (7 * 3 + Nmax)/8
LinkedList的成员读取平均开销nl = Nmax
Nmax远大于3

然后再回到最初的理论时间复杂度来看：尽管ArrayList的和LinkedList处于同一量级，但是实际上由于括号里的n只有后者的几分之一，所以前者的实际耗费的时间也比后者小很多。

立一个flag

上面这个小栗子是我瞎编的。

但是也可以反映出一个情况：同样是“开销”，但是“开销”和“开销”是不一样的。如果嘴上只挂着开销两个字，那么所有的性能讨论就都成了玄学。而将玄学变为科学的最佳方法是用数据说话。因此，接下来一段时间里，我将利用一些性能测试工具，对常见的数据结构进行测试分析，结合计算机体系知识重新学习一下数据结构。当然也会测测上面瞎编的这个小栗子，看会不会打脸。

暂定的数据结构选材范围就是OpenJDK的Collection、Eclipse Collection、Scala Collection。

是的，我改主意了，一味的傻等精通Java再学习Scala的话，可能永远都没那个机会。先从小demo开始，慢慢熟悉语法。至于函数式编程思想的学习，可以留在不远的未来。