如何实现不变性 [英] How Immutability is Implemented
问题描述
我正在尝试了解
胖节点案例2
路径复制
如果您的示例中的图是一个以节点 a 为根的树，则路径复制将与 trie 示例
在具有根数组的简单树节点之后就足够了
Node->变量值节点父级Node []个子级图->根源:[{节点root1，日期时间戳}，{节点root2，日期时间戳}...] 由于修改了节点 h ，因此将复制从节点 h 到根节点 a 的整个路径.
路径复制案例1
路径复制案例2
修改框
假设示例中的图形为树，则只需满足以下条件
Node->变量值节点父级Node []个子级ModificationBox modBox修改框->时间戳记属性 {类型:值/父母/子女[i]等(仅一个属性)值:属性值}图->根源:[{节点root1，日期时间戳}，{节点root2，日期时间戳}...] 修改框案例1
未修改节点 h
修改框案例2
在这种情况下，假设 h 已被修改
I am trying to grasp how the trie and such in immutability is implemented, as relates to immutability in JS. I understand how there is supposed to be significant structural sharing.
My question is say you have a graph sort of structure like this:
a -- b
|
c
|
d -- h
|
e -- i -- l
|
f -- j -- m
|
g -- k -- n
So then you add an x to the system. I'll try it two different ways:
a -- b
|
c
|
d -- h -- x
|
e -- i -- l
|
f -- j -- m
|
g -- k -- n
That one is just added as a leaf node.
a -- b
|
c
|
d -- h
|
x
|
e -- i -- l
|
f -- j -- m
|
g -- k -- n
That one is added in the middle of a path.
I am wondering what the immutable data structure would be to handle these 2 situations. So essentially we have a function f : graph -> graph' that changes the graph into a "new graph", when under the hood it should only be making a small adjustment to the data structure. Not sure how this would look or how it works. My first attempt at an explanation would be something like this...
It starts of in a wrapper object which is like ImmutableJS's API layer on top of the JS objects.
--------------------------
| |
| a -- b |
| | |
| c |
| | |
| d -- h |
| | |
| e -- i -- l |
| | |
| f -- j -- m |
| | |
| g -- k -- n |
| |
--------------------------
Then you make the change and it creates a new wrapper object.
-------------------------- --------------------------
| | | |
| a -- b | | |
| | | | |
| c | | |
| | | | |
| d -- h --------------------------------- x |
| | | | |
| e -- i -- l | | |
| | | | |
| f -- j -- m | | |
| | | | |
| g -- k -- n | | |
| | | |
-------------------------- --------------------------
Then likewise for the second example:
-------------------------- --------------------------
| | | |
| a -- b | | |
| | | | |
| c | | |
| | | | |
| d -- h | | |
| | | | |
| o --------------------------------- x |
| | | | |
| e -- i -- l | | |
| | | | |
| f -- j -- m | | |
| | | | |
| g -- k -- n | | |
| | | |
-------------------------- --------------------------
The boxes are the API objects you use, and the graphs inside are the plain JS data objects.
But in these examples the original graph structure is modified (placing a link to h in the first example, and placing an o placeholder in the second one). So I'm wondering how specifically you would make these things immutable. Every change I make to the graph I would like to "return a new object", but under the hood there is optimal structural sharing.
Thank you for your help.
The example in case of trie is not a general solution for immutability, it's just a way of representing an array in a tree then applying general solutions for persistent trees.
Following are general solutions for persistent graphs
- Fat node.
Each node stores history of it's changes and timestamp of those changes. When looking for a graph at specific point in time, we provide the timestamp to get version at that time. It's space efficient (only new value is stored) however access time suffers in this case due to an additional search (Mulplicative slowdown) on the modification array (of arbitrary length) for each node. Path copying
In this case we create a new node keeping all the children, we create a new node for each node in it's path to root. In this case we have to store an array of roots. It's access time is same as original graph, only extra time that it takes is due to search on the root array (Additive slowdown). This is what's being used in thetrieexample. It's space inefficient as every change creates a set of new nodes with new root, representing path to new node from new root.Modification Box(Sleator, Tarjan et al)
This one combines both Fat node and Path copying. Every node can store only one modification. If we try to update an already modified node then we use path copying and try to create a duplicate node with duplicate path to it. Interestingly while creating new path we'll have to take care of modification boxes. In the new path only those nodes are duplicated which have been already modified, else only there modification boxes are updated.
Note: Path copy and Modification box are application to trees (or may be DAGs) and not not generic graphs. As both of these involve cascading creation of new nodes from mdoified node to root. A generic graph doesn't have a root. So only method available to us is Fat Node for generic graphs.
Ref:
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
Fat Node
Following structure of Node and Graph should suffice
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],
}
Fat Node Case 1
Fat Node Case 2
Path Copy
If graph in your example is a tree with node a as root, then path copy will work same as described in trie example
Following simple tree nodes with root array will suffice
Node ->
var value
Node parent
Node[] children
Graph ->
roots: [
{
Node root1,
Date timestamp
},
{
Node root2,
Date timestamp
}
...
]
Since node h is being modified, entire path from node h to root node a would be duplicated.
Path copy Case 1
Path Copy Case 2
Modification Box
Assuming the graph in example is tree, following would suffice
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
}
...
]
Modification Box Case 1
Node h is not modified
Modification Box Case 2
For this case lets assume that h has already been modified
这篇关于如何实现不变性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
