不可变性是如何实现的

Question

我试图理解如何在 JS 中实现不可变数据结构，例如使用 trie 等。我了解到，这里应该存在重要的结构共享。

我的问题是，假设你有一个类似于下面的图结构：

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'，它将图形更改为“新图形”，但在底层它只应该对数据结构进行小的调整。不确定它会是什么样子或者怎么工作。我的第一个尝试是这样的解释...

它始于一个包装对象，就像 ImmutableJS 在 JS 对象之上的 API 层。

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

然后你进行更改，它会创建一个新的包装对象。

 --------------------------           --------------------------
|                          |         |                          |
|    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数据对象。

但在这些示例中，原始图形结构被修改（在第一个示例中放置到h的链接，在第二个示例中放置一个o占位符）。所以我想知道具体如何使这些东西不可变。我对图形进行的每个更改都希望“返回一个新对象”，但在幕后有最佳的结构共享。

感谢您的帮助。

- Lance

---

https://hypirion.com/musings/understanding-persistent-vector-pt-1 - Lance

Answer 1

Trie的示例并不是针对不可变性的通用解决方案，它只是一种将数组表示为树的方式，然后应用于持久性树的通用解决方案。

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

1. 胖节点。
   每个节点存储其更改历史记录和更改的时间戳。当在特定时间点查找图时，我们提供时间戳以获取该时间点的版本。它在空间上效率高（仅存储新值），但由于每个节点的修改数组（任意长度）上进行额外的搜索（乘法减速），因此访问时间会受到影响。

2. 路径复制
   在这种情况下，我们创建一个新节点并保留所有子节点，对其到根的每个节点创建一个新节点。 在这种情况下，我们必须存储一组根节点的数组。它的访问时间与原始图相同，唯一需要额外的时间是由于对根数组的搜索（加法减速）。这就是trie示例中使用的方法。它的空间效率低，因为每次更改都会创建一组具有新根的新节点，表示从新根到新节点的路径。

3. 修改盒（Sleator，Tarjan等）
   这个方法同时结合了胖节点和路径复制。每个节点只能存储一个修改。如果我们尝试更新已经修改的节点，那么我们使用路径复制，尝试创建一个具有重复路径的重复节点。有趣的是，在创建新路径时，我们将不得不处理修改框。在新路径中，只有那些已被修改的节点才会被复制，否则只有它们的修改盒会被更新。

注意：路径复制和修改盒适用于树（或可能是DAG），而不是通用图形。由于这两者都涉及从修改节点到根的级联新节点创建，因此通用图形没有根。因此，我们只能使用胖节点来处理通用图形。

参考资料：
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已经被修改

- 11thdimension