如何实现不变性

Question

我想了解 trie 等不可变性是如何实现的，这与 JS 中的不可变性有关。我理解应该如何进行重要的结构共享。

我的问题是你有一个像这样的图结构：

a -- b
     |
     c
     |
     d -- h
          |
     e -- i -- l
          |
     f -- j -- m
          |
     g -- k -- n

然后你向系统添加一个x。我将尝试两种不同的方式：

a -- b
     |
     c
     |
     d -- h -- x
          |
     e -- i -- l
          |
     f -- j -- m
          |
     g -- k -- n

那个刚刚添加为叶节点。

a -- b
     |
     c
     |
     d -- h
          |
          x
          |
     e -- i -- l
          |
     f -- j -- m
          |
     g -- k -- n

那个是在路径中间添加的。

我想知道处理这两种情况的不可变数据结构是什么。所以本质上我们有一个函数 f : graph -> graph' 将图形更改为 "new graph"，在引擎盖下它应该只对数据结构进行小的调整。不确定这看起来如何或如何工作。我第一次尝试解释是这样的...

它从一个包装器对象开始，它类似于 JS 对象之上的 ImmutableJS 的 API 层。

 --------------------------
|                          |
|    a -- b                |
|         |                |
|         c                |
|         |                |
|         d -- h           |
|              |           |
|         e -- i -- l      |
|              |           |
|         f -- j -- m      |
|              |           |
|         g -- k -- n      |
|                          |
 --------------------------

然后您进行更改，它会创建一个 new 包装器对象。

 --------------------------           --------------------------
|                          |         |                          |
|    a -- b                |         |                          |
|         |                |         |                          |
|         c                |         |                          |
|         |                |         |                          |
|         d -- h --------------------------------- x            |
|              |           |         |                          |
|         e -- i -- l      |         |                          |
|              |           |         |                          |
|         f -- j -- m      |         |                          |
|              |           |         |                          |
|         g -- k -- n      |         |                          |
|                          |         |                          |
 --------------------------           --------------------------

那么第二个例子同样如此：

 --------------------------           -------------------------- 
|                          |         |                          |
|    a -- b                |         |                          |
|         |                |         |                          |
|         c                |         |                          |
|         |                |         |                          |
|         d -- h           |         |                          |
|              |           |         |                          |
|              o --------------------------------- x            |
|              |           |         |                          |
|         e -- i -- l      |         |                          |
|              |           |         |                          |
|         f -- j -- m      |         |                          |
|              |           |         |                          |
|         g -- k -- n      |         |                          |
|                          |         |                          |
 --------------------------           --------------------------

方框是你使用的API对象，里面的图表是普通的JS数据对象。

但在这些示例中，原始图结构被修改（在第一个示例中将 link 放置到 h，在第二个示例中放置 o 占位符）。所以我想知道您将如何具体地使这些东西不可变。我希望 "return a new object" 对图表所做的每一次更改，但在引擎盖下有最佳的结构共享。

感谢您的帮助。

Answer 1

trie 的示例不是不变性的通用解决方案，它只是一种在树中表示数组然后应用持久树的通用解决方案的方法。

以下是持久图的通用解决方案

胖节点.
每个节点都存储其更改的历史记录和这些更改的时间戳。在特定时间点查找图形时，我们提供时间戳以获取当时的版本。它 space 高效（仅存储新值）但是在这种情况下访问时间会受到影响，因为在每个节点的修改数组（任意长度）上进行额外搜索（Mulplicative slowdown）。
路径复制
在这种情况下，我们创建一个保留所有子节点的新节点，我们为根路径中的每个节点创建一个新节点。在这种情况下，我们必须存储一个根数组。它的访问时间与原始图相同，只是由于在根数组 (Additive slowdown) 上搜索而花费的额外时间。这就是 trie 示例中使用的内容。它 space 效率低下，因为每次更改都会创建一组具有新根的新节点，表示从新根到新节点的路径。
改装箱(Sleator, Tarjan et al)
这个结合了胖节点和路径复制。每个节点只能存储一个修改。如果我们尝试更新一个已经修改的节点，那么我们使用路径复制并尝试创建一个具有重复路径的重复节点。有趣的是，在创建新路径时，我们必须处理修改框。在新路径中，只有那些已经修改的节点被复制，否则只有修改框被更新。

注意：路径复制和修改框适用于树（或可能是DAG）而不是通用图。因为这两者都涉及从 mdoified 节点到 root 的新节点的级联创建。通用图没有根。所以我们唯一可用的方法是用于通用图的 Fat Node。

参考：
1. https://en.wikipedia.org/wiki/Persistent_data_structure
2.https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2005/lecture-notes/persistent.pdf

胖节点

节点和图形的以下结构应该足够了

Node ->
    var value;
    Node parent
    Node[] children
    Modification[] modifications
Modification ->
    Node node
    Date timestamp

Graph -> (Adjancency list)
    {
        'a': [b],
        'b': [c],
        'c': [d],
        'd': [h],
        'e': [i],
        'f': [j],
        'g': [k],
        'h': [d, i],
        'i': [e, j, l],
        'j': [f, i, k, m],
        'k': [g, j, n],
        'l': [i],
        'm': [j],
        'n': [k],
    }

胖节点案例 1

胖节点案例 2

路径复制

如果您的示例中的图形是以节点 a 为根的树，则路径复制的工作方式与 trie 示例

中描述的相同

跟随带有根数组的简单树节点就足够了

Node ->
    var value
    Node parent
    Node[] children

Graph ->
    roots: [
        {
            Node root1,
            Date timestamp
        },
        {
            Node root2,
            Date timestamp
        }
        ...
    ]

由于正在修改节点 h，因此从节点 h 到根节点 a 的整个路径将被复制。

路径复制案例1

路径复制案例2

修改框

假设示例中的图形是树，以下就足够了

Node ->
    var value
    Node parent
    Node[] children
    ModificationBox modBox

ModificationBox ->
    timestamp,
    Attribute {
        type: value/parent/children[i] etc (only one attribute)
        value: value of attribute
    }


Graph ->
    roots: [
        {
            Node root1,
            Date timestamp
        },
        {
            Node root2,
            Date timestamp
        }
        ...
    ]

改装箱案例1

节点h未修改

改装箱案例2

对于这种情况，我们假设 h 已经被修改

如何实现不变性

How Immutability is Implemented

javascript

graph

immutability

trie

immutable.js