如何实现不变性

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'可以将图形变成一个"新图形",当它在幕后它应该只对数据结构进行一个小的调整.不确定这看起来如何或如何工作.我第一次尝试解释就是这样......

它从一个包装器对象开始,就像在JS对象之上的ImmutableJS的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在第二个示例中放置占位符).所以我想知道你是如何具体地将这些东西变成一成不变的.我对图表所做的每一项更改都要"返回一个新对象",但在引擎盖下有最佳的结构共享.

谢谢您的帮助.

Answer 1

这个例子trie不是一般的不变性解决方案,它只是一种在树中表示数组然后对持久树应用通用解决方案的方法.

以下是持久图的一般解决方案

1. 胖节点.
   每个节点都存储其更改的历史记录和这些更改的时间戳.在特定时间点查找图表时,我们提供了当时获取版本的时间戳.它的空间效率很高(只存储了新值),但是在这种情况下访问时间受到限制,因为Mulplicative slowdown每个节点的修改数组(任意长度)都有额外的搜索().

2. 路径复制
   在这种情况下,我们创建一个保留所有子节点的新节点,我们为其中的每个节点创建一个新节点.在这种情况下,我们必须存储一个根数组.它的访问时间与原始图形相同,只需要额外的时间就可以查询根数组(Additive slowdown).这就是trie示例中使用的内容.它的空间效率低,因为每次更改都会创建一组带有新根的新节点,表示从新根节点到新节点的路径.

3. Modification Box(Sleator,Tarjan等)
   这个结合了Fat节点和Path复制.每个节点只能存储一个修改.如果我们尝试更新已修改的节点,那么我们使用路径复制并尝试创建一个具有重复路径的重复节点.有趣的是,在创建新路径时,我们必须处理修改框.在新路径中,只有那些已经修改过的节点是重复的,否则只会更新修改框.

注意:路径复制和修改框是树的应用程序(或可能是DAG),而不是通用图.因为这两者都涉及从mdoified节点到root的级联创建新节点.通用图没有根.因此,我们唯一可用的方法是通用图的胖节点.

参考文献:
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 /讲课笔记/ persistent.pdf

胖节点

以下结构的Node和Graph应该足够了

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已经修改过