17611538698
webmaster@21cto.com

谈谈数据结构

资讯 0 2321 2017-06-02 12:01:35
data-stru.png


沃斯说过,程序 = 算法 + 数据结构。

我认为,等式的右边,数据结构的权重要大于算法。数据结构定义好,基本上,你所用的算法也就确定了,算法的时间复杂度也八九不离十。
 
上周,我在 team 内部分享了一个关于数据结构的主题,在这里,也和诸位分享。

现代的编程语言,内置的数据结构越来越多,从 primitive 的类型:integer, float, boolean, string,一路到 complex 结构,如:array,list,map,set 等。这些结构即插即用,非常顺手,可是有时我们也需要了解其内部的实现(内部的数据结构),从而更好地打造高性能的应用。有些「聪明」的语言,如 clojure,会根据使用场景动态地切换内部的结构,比如说 map,当 key 的数量超过某个阈值,便会自动换成更高效的结构来应对需求。

今天,我们就来扒一扒,编程语言中的常见数据类型,其内在究竟是怎么一回事。
array / tuple array 或者 tuple,是大家最熟知的容器型的数据类型,其内部可以承载其他数据结构。他们的特点是容器里的元素被分配在连续的内存中,可以按照 index 随机访问,时间复杂度是 O(1)。array 一般要求内部是同构的数据结构,而 tuple 则允许异构。

对函数式编程语言,或者提供 immutable data structure 的语言,高效地处理 array 是个挑战。如果代码中修改了 array 中的某个元素,拷贝并重新生成整个 array 的代价太大。
 
我们需要一种合适的数据,能够在结构上共享大部分不受影响的数据。这种数据结构,便是大部分函数式编程语言使用的 persistent data structure。persistent data structure 用 DAG(一般是一个 Trie)来描述数据,当 DAG 某部分发生改变,只需要重新生成和改变相关的路径上的节点即可,非常高效。对于 array,我们可以使用 Bit Array Mapped Trie / Index Vector Trie:


001.jpg


通过把 index 的二进制切分并进行 trie 的遍历,对应的叶子节点就是要找的节点。如果我们要修改这个节点的内容,在原有结构保持不变的情况下,我们只需要生成一个新的 node,并生成这条路径上一直到根节点的相关中间节点即可。需要额外拷贝的内容仅仅和 trie 的深度有关。

002.jpg

List
大多数编程语言,提及 list,其内部一般是个带尾指针的双向链表。因而,在头部或者尾部添加新的节点非常高效,是 O(1) 的操作,然而查找,插入,删除则需要遍历链表,是 O(n) 的操作。由于是链表,获取链表的长度一般而言也需要遍历,是个 O(n) 的操作,有些编程语言会为其优化,在链表的头部维护链表的长度,这样获取长度的效率则为 O(1)。请注意弄清楚你用的语言,这个操作的效率如何。对于 erlang,
length
函数是 O(n) 的复杂度,因而对大列表的
length
操作不要滥用。

003.jpg


 
Map
 
map,在很多语言里,被称为 associate array (PHP),dict(Python)等。他是一个 key/value pair 的容器。理论上可以容纳任意数量的 key/value pair。在 map 中,key 是唯一的,key 和 value 一般都可以是任意数据结构。当 key 只能是 string 时,有些语言会使用标准的 trie,或者 patricia trie 来处理。

早期的 map 用 hash array + collision avoidance 实现,典型的 collision avoidance 有 chaining 和 probing。一个 key 经过某个哈希函数后,对应 hash array 中的一个位置,如果这个位置已经有数据,要么,把数据 用 linklist chain 起来,这是 chaining;要么,在 array 中随后的某个固定位置找到(probe)一个空闲的 slot,写入,这是 probling。

chaining 的问题是如果 key 的数量大大超过 hash array 的长度,冲突会很严重,从而大大拉低性能。最坏情况下,时间复杂度是 O(n/k);probing 的问题是 hash table 必须和 key 空间一样大,如果 hash 函数选得不好,容易造成大面积的冲突。对于支持动态增减 key 的 map 来说,常常需要扩大 hash table,然后 rehash,内存和计算的代价都不小。python 的 dict 便是使用 hash array + collision avoidance 实现的。
C++ 及很多其他语言使用红黑树来支持 map。hash array 和红黑树的比较:
 
如今大部分 FP 语言,其 map 都使用了类似上文提到的 persistent data structure:HAMT (Hash Array Mapped Trie,作者:Phil Bagwell):

004.jpg


它将 key 通过哈希函数处理后,成为一个数字,然后从这个 hash value 的低位起,一路向下搜索,直到找到叶子节点,如果叶子节点上的数据和 key 匹配,则查找到;否则,没找到。HAMT 使用 32bit / 64bit 的 hash value(上述仅仅是示意),所以 hash collision 的几率很小,如果冲突发生,叶子节点会转换为 index node,然后用不同的 hash 方法计算原有的叶子节点和新的节点,并将其挂载到 index node 下。
 
Tree
 
Tree 的种类很多,这里讲讲常用的 AVL, Trie 和近期比较热门的 Merkle tree。
 
AVL 是一种比较简单的 tree,左右两棵子树层级不超过 1。如果新加入的节点打破了这个平衡,则需要翻转(可能多次)使其达到新的平衡。
 
Trie 是一种前缀树,可以用来做路由查询。erlang 的 pattern matching 机制,就是将使用 pattern matching 的代码转化成类似 Trie 的代码结构。
 
Merkle tree 脱胎于加密算法,可以验证 tree 的任何部分的正确性,被广泛用于文件系统(ZFS),文件分块下载(BT),block chain 等。

在 Merkle tree 里,每个数据单元生成一个 hash,相邻的 hash 凑在一起再生成 hash,这样两两结合,一直到根(如果数据单元的总数是奇数,那么最后一个的 hash 和自己结合)。

举个文件同步校验的例子。假设本地磁盘和网盘有 128 个文件(2^7),各自生成一个 Merkle tree,我们只需要从根节点一路比较下来,O(logN) 的效率,就可以找到有差异的文件。

评论