可持久化数据结构
2019-01-07 本文已影响0人
ITgecko
概念
-
可持久化数据结构(Persistent data structure)是一种在发生改变时，会保存之前的版本的数据结构。这是一种不可变的(immutable
)数据结构，对数据进行操作时，不会在原数据上进行更新改变，而是会生成另一个新的发生改变了的新数据。主要不要和数据持久化(Persistent storage
)混淆，那是一种存储概念。 - 所有数据版本(versions)都可以访问，但只有最新的版本才能修改的话，称为部分持久化数据结构(partially)。所有版本都能访问、都能修改，称为全持久化数据结构(fully)。非持久化的数据结构称为ephemeral(短暂的？)。
- 结合
immutable.js来看一个示例，map1进行操作后会新生成一个对象map2。这里immutable.js提供的Map就是可持久化数据结构，无论你如何进行操作(这些操作函数自然都是纯函数)，原数据是不会发生改变的，而是会产生新的数据。
const { Map } = require("immutable");
const map1 = Map({ a: 1, b: 2, c: 3 });
const map2 = map1.set('b', 50);
map1.get('b') + " vs. " + map2.get('b'); // 2 vs. 50
- 注意虽然map2和map1是两个不同的对象，但map2并不是从map1进行深克隆就得到的，这样如果对象结构很复杂并且有多次操作的话会有很大的性能耗损。所以不同数据version，在这里也就是不同的js对象，会进行Structural Sharing（结构共享）。就比如上面的map1和map2，他们的a、c属性的值相同，所以这部分数据节点他们会共同占用。(后面会有具体的图片示例，可以清晰地了解结构共享)。
可持久化数据结构示例
- 单向链表(singly linked list
)应该是最简单的可持久化数据结构，每个节点拥有一个next指向下一个节点。我们来看下示例，我们首先有两个链表：xs和ys。
xs = [0, 1, 2]
ys = [3, 4, 5]
- 以图片来看应该是这样：
- 接着进行一个合并操作，xs在前、ys在后合并生成第三链表zs [0, 1, 2, 3, 4, 5]。以可持久化数据结构的做法来做的话，步骤如下：1. 复制xs得到zs 2. 然后zs的末端节点指向ys，这样就让zs和ys链表共享了ys的三个节点。
-
过程图示如下：
image.png
- 这种共享节点的做法只适用于单向列表，如果是双向链表，这样做就改变了ys头部节点的pre指向，违反了数据不可变原则。
-
接着来看另一种数据类型二叉树。首先有一个二叉树xs，结构如下：
image.png
-
接着在xs的f节点，添加一个left子节点e，同时生成一个新树ys。过程图示如下：
image
- 原来的树xs会保存下来，然后新树ys和老树xs会共享很多公用节点。
