概念
-
可持久化數(shù)據(jù)結(jié)構(gòu)(Persistent data structure)是一種在發(fā)生改變時(shí)，會(huì)保存之前的版本的數(shù)據(jù)結(jié)構(gòu)。這是一種不可變的(immutable
)數(shù)據(jù)結(jié)構(gòu)练湿，對(duì)數(shù)據(jù)進(jìn)行操作時(shí)番枚，不會(huì)在原數(shù)據(jù)上進(jìn)行更新改變，而是會(huì)生成另一個(gè)新的發(fā)生改變了的新數(shù)據(jù)村砂。主要不要和數(shù)據(jù)持久化(Persistent storage
)混淆烂斋，那是一種存儲(chǔ)概念。 - 所有數(shù)據(jù)版本(versions)都可以訪問础废，但只有最新的版本才能修改的話汛骂，稱為部分持久化數(shù)據(jù)結(jié)構(gòu)(partially)。所有版本都能訪問评腺、都能修改帘瞭，稱為全持久化數(shù)據(jù)結(jié)構(gòu)(fully)。非持久化的數(shù)據(jù)結(jié)構(gòu)稱為ephemeral(短暫的蒿讥？)图张。
- 結(jié)合
immutable.js來看一個(gè)示例，map1進(jìn)行操作后會(huì)新生成一個(gè)對(duì)象map2诈悍。這里immutable.js提供的Map就是可持久化數(shù)據(jù)結(jié)構(gòu)祸轮，無論你如何進(jìn)行操作(這些操作函數(shù)自然都是純函數(shù))，原數(shù)據(jù)是不會(huì)發(fā)生改變的侥钳，而是會(huì)產(chǎn)生新的數(shù)據(jù)适袜。
const { Map } = require("immutable");
const map1 = Map({ a: 1, b: 2, c: 3 });
const map2 = map1.set('b', 50);
map1.get('b') + " vs. " + map2.get('b'); // 2 vs. 50
- 注意雖然map2和map1是兩個(gè)不同的對(duì)象，但map2并不是從map1進(jìn)行深克隆就得到的舷夺，這樣如果對(duì)象結(jié)構(gòu)很復(fù)雜并且有多次操作的話會(huì)有很大的性能耗損苦酱。所以不同數(shù)據(jù)version售貌，在這里也就是不同的js對(duì)象，會(huì)進(jìn)行Structural Sharing（結(jié)構(gòu)共享）疫萤。就比如上面的map1和map2颂跨，他們的a、c屬性的值相同扯饶，所以這部分?jǐn)?shù)據(jù)節(jié)點(diǎn)他們會(huì)共同占用恒削。(后面會(huì)有具體的圖片示例，可以清晰地了解結(jié)構(gòu)共享)尾序。
可持久化數(shù)據(jù)結(jié)構(gòu)示例
- 單向鏈表(singly linked list
)應(yīng)該是最簡(jiǎn)單的可持久化數(shù)據(jù)結(jié)構(gòu)钓丰，每個(gè)節(jié)點(diǎn)擁有一個(gè)next指向下一個(gè)節(jié)點(diǎn)。我們來看下示例每币，我們首先有兩個(gè)鏈表：xs和ys携丁。
xs = [0, 1, 2]
ys = [3, 4, 5]
- 以圖片來看應(yīng)該是這樣：
- 接著進(jìn)行一個(gè)合并操作，xs在前兰怠、ys在后合并生成第三鏈表zs [0, 1, 2, 3, 4, 5]梦鉴。以可持久化數(shù)據(jù)結(jié)構(gòu)的做法來做的話，步驟如下：1. 復(fù)制xs得到zs 2. 然后zs的末端節(jié)點(diǎn)指向ys揭保，這樣就讓zs和ys鏈表共享了ys的三個(gè)節(jié)點(diǎn)尚揣。
-
過程圖示如下：
image.png - 這種共享節(jié)點(diǎn)的做法只適用于單向列表，如果是雙向鏈表掖举，這樣做就改變了ys頭部節(jié)點(diǎn)的pre指向快骗，違反了數(shù)據(jù)不可變?cè)瓌t。
-
接著來看另一種數(shù)據(jù)類型二叉樹塔次。首先有一個(gè)二叉樹xs方篮，結(jié)構(gòu)如下：
image.png -
接著在xs的f節(jié)點(diǎn)，添加一個(gè)left子節(jié)點(diǎn)e励负，同時(shí)生成一個(gè)新樹ys藕溅。過程圖示如下：
image - 原來的樹xs會(huì)保存下來，然后新樹ys和老樹xs會(huì)共享很多公用節(jié)點(diǎn)继榆。
