我正试图掌握 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 占位符)。所以我想知道您将如何具体地使这些东西不可变。我对图形所做的每一次更改都希望“返回一个新对象”，但在引擎盖下存在最佳结构共享。
感谢您的帮助。
最佳答案
trie 示例不是不变性的通用解决方案，它只是一种在树中表示数组然后应用持久树的通用解决方案的方法。
以下是持久图的通用解决方案
- 胖节点。
每个节点都存储其更改的历史记录和这些更改的时间戳。在特定时间点查找图形时，我们提供时间戳以获取当时的版本。它节省空间(仅存储新值)，但在这种情况下，由于对每个节点的修改数组(任意长度)进行额外搜索(乘法减速)，访问时间会受到影响。 路径复制
在这种情况下，我们创建一个保留所有子节点的新节点，我们为根路径中的每个节点创建一个新节点。在这种情况下，我们必须存储一个根数组。它的访问时间与原始图相同，只是它花费的额外时间是由于对根数组的搜索(Additive slowdown)。这就是trie示例中使用的内容。它的空间效率很低，因为每次更改都会创建一组具有新根的新节点，表示从新根到新节点的路径。修改框(Sleator、Tarjan 等人)
这个结合了胖节点和路径复制。每个节点只能存储一个修改。如果我们尝试更新一个已经修改的节点，那么我们使用路径复制并尝试创建一个具有重复路径的重复节点。有趣的是，在创建新路径时，我们必须处理修改框。在新路径中，只有那些已经被修改的节点被复制，否则只有修改框被更新。
注意:路径复制和修改框适用于树(或可能是 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和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 的整个路径将被复制。
路径复制案例一
路径复制案例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
}
...
]
retrofit 箱案例1
节点h没有被修改
retrofit 箱案例2
对于这种情况，我们假设 h 已经被修改
关于javascript - 如何实现不变性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50993252/