是时候重新学习数据结构了

撰写于 2019-01-12 修改于 2019-01-12 标签 原创

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

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

纯粹的理论知识是不足的

举个简单的例子,假设需要在一个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处理器为例:

  1. 一段cache line的大小是64 byte。
  2. ArrayList实际上是对象指针数组。
  3. 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读取下一个成员的开销。那么我们可以得出结论:

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

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

立一个flag

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

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

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

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

Site by Zhang,Xin using Hexo & Random

Hide