從0寫一下diff算法降狠，我是一邊寫代碼对竣，一邊寫文章，整理一下思路榜配。
注：這里只討論tag屬性相同并且多個children的情況否纬，
不相同的tag直接替換，刪除蛋褥，這沒啥好寫的临燃。
用這個例子來說明
export const Hello = {
name: 'Hello',
data() {
return {
childList: ['a', 'b', 'c'],
};
},
mounted() {
setTimeout(() => {
this.childList = this.childList.reverse();
}, 1000);
},
render: function(h) {
return h('ul', {
}, this.childList.map((child) => h('li', {}, child)));
},
};
簡單diff，把原有的刪掉烙心，把更新后的插入
function updateChildren (elm, prevChildren, nextChildren) {
// 刪除舊節(jié)點
for (const child of prevChildren) {
elm.removeChild(child.elm);
}
// 把新的vnode插入
for (const child of nextChildren) {
createElm(child, elm); //vnode生成正式dom
}
}
變化前后的標簽都是li膜廊，所以只用比對vnodeData和children即可，復用原有的DOM淫茵。
先只從這個例子出發(fā)
我只用遍歷舊的vnode爪瓜，然后把舊的vnode和新的vnode patch就行
function updateChildren (elm, prevChildren, nextChildren) {
for (let i = 0; i < prevChildren.length; i++) {
patchVnode(nextChildren[i], prevChildren[i]);
}
}
這樣就省掉移除和新增dom的開銷
現在的問題是，我的例子剛好是新舊vnode數量一樣匙瘪，如果不一樣就有問題
示例改成這樣：
// 新的children vnode增加了一個d
export const Hello1 = {
name: 'Hello1',
data() {
return {
childList: ['a', 'b', 'c'],
};
},
mounted() {
setTimeout(() => {
this.childList.reverse().push('d');
}, 1000);
},
render: function(h) {
return h('ul', {
}, this.childList.map((child) => h('li', {}, child)));
},
};
// 新的的children vnode刪除了一個元素
export const Hello2 = {
name: 'Hello2',
data() {
return {
childList: ['a', 'b', 'c'],
};
},
mounted() {
setTimeout(() => {
this.childList.reverse().shift();
}, 1000);
},
render: function(h) {
return h('ul', {
}, this.childList.map((child) => h('li', {}, child)));
},
};
實現思路改成：先看看是舊的長度長铆铆，還是新的長，如果舊的長丹喻，我就遍歷新的薄货，然后把多出來的舊節(jié)點刪掉，如果新的長碍论，我就遍歷舊的谅猾，然后多出來的新vnode加上。
function updateChildren (elm, prevChildren, nextChildren) {
const oldLen = prevChildren.length;
const newLen = nextChildren.length;
const commonLen = oldLen > newLen ? newLen : oldLen;
for (let i; i < commonLen.length; i++) {
patchVnode(nextChildren[i], prevChildren[i]);
}
if (oldLen < newLen) {
createElm(child, [], elm);
}
} else {
for (const child of prevChildren.slice(oldLen - (oldLen - newLen))) {
elm.removeChild(child.elm);
}
}
}
仍然有可優(yōu)化的空間鳍悠，還是下面這幅圖
通過我們上面的diff算法税娜，實現的過程會比對 preve vnode和next vnode，標簽相同贼涩，則只用比對vnodedata和children巧涧。發(fā)現<li>標簽的子節(jié)點（文本節(jié)點a,b,c）不同，于是分別刪除文本節(jié)點a,b,c遥倦，然后重新生成新的文本節(jié)點c,b,a。但是實際上這幾個<li>只是位置不同占锯，那優(yōu)化的方案就是復用已經生成的dom袒哥，把它移動到正確的位置。
怎么移動消略？我們使用key來將新舊vnode做一次映射堡称。
首先我們找到可以復用的vnode
可以做兩次遍歷，外層遍歷next vnode艺演，內層遍歷prev vnode
for (let i = 0; i < nextChildren.length; i++) {
const nextVnode = nextChildren[i];
for (let j = 0; j < prevChildren.length; j++) {
const prevVnode = prevChildren[j];
if (nextVnode.key === prevVnode.key) {
// 說明可以復用
patchVnode(nextVnode, prevVnode);
}
}
}
如果next vnode和prev vnode只是位置移動却紧，vnodedata和children沒有任何變動桐臊，調用patchVnode之后不會有任何dom操作。
接下來只需要把這個key相同的vnode移動到正確的位置即可晓殊。我們的問題變成了怎么移動断凶。
首先需要知道兩個事情:
- 每一個prev vnode都引用了一個真實dom節(jié)點，每個next vnode這個時候都沒有真實dom節(jié)點巫俺。
- 調用patchVnode的時候會把prevVnode引用的真實Dom的引用賦值給nextVnode认烁，就像這樣
const elm = vnode.elm = oldVnode.elm;
還是拿上面的例子，外層遍歷next vnode,
遍歷第一個元素的時候介汹， 第一個vnode是li(c)却嗡，然后去prev vnode里找，在最后一個節(jié)點找到了嘹承，這里外層是第一個元素窗价，不做任何移動的操作，我們記錄一下這個vnode在prevVnode中的索引位置lastIndex叹卷，接下來在遍歷的時候舌镶，如果j<lastIndex，說明原本prevVnode在前面的元素豪娜，在nextVnode中變到了后面來了餐胀，那么我們就把prevVnode[j]放到nextVnode[i-1]的后面。
這里多說一句瘤载，dom操作的api里否灾，只有insertBefore()，沒有insertAfter()鸣奔。也就是說只有把某個dom插入到某個元素前面這個方法墨技，沒有插入到某個元素后面這個方法，所以我們只能用insertBefore()挎狸。那么思路就變成了扣汪，當j<lastIndex的時候，把prevChildren[j]插入到nextVnode[i-1]的真實dom的后面元素的前面锨匆。
當j>=lastIndex的時候崭别，說明這個順序是正確的的，不用移動恐锣，然后把lastIndex = j;
也就是說茅主，只把prevVnode中后面的元素往前移動，原本順序是正確的就不變土榴。
現在我們的diff的代碼變成了這樣
function updateChildren (elm, prevChildren, nextChildren) {
let lastIndex = 0;
for (let i = 0; i < nextChildren.length; i++) {
const nextVnode = nextChildren[i];
console.log('nextVnode: ', nextVnode);
for (let j = 0; j < prevChildren.length; j++) {
const prevVnode = prevChildren[j];
if (nextVnode.key === prevVnode.key) {
patchVnode(nextVnode, prevVnode);
if (j < lastIndex) {
elm.insertBefore(prevVnode.elm, nextChildren[i-1].elm.nextSibling);
} else {
lastIndex = j;
}
}
}
}
}
同樣的問題诀姚，如果新舊vnode的元素數量一樣，那就已經可以工作了玷禽。接下來要做的就是新增節(jié)點和刪除節(jié)點赫段。
新增節(jié)點：
整個框架中將vnode掛載到真實dom上都調用patch函數呀打，patch里調用createElm來生成真實dom。按照上面的實現糯笙，如果nextVnode中有一個節(jié)點是prevVnode中沒有的贬丛，就有問題
在prevVnode中找不到li(d)，那我們需要調用createElm掛在這個新的節(jié)點炬丸，因為這里的節(jié)點需要超入到li(b)和li(c)之間瘫寝，所以需要用insertBefore()。在每次遍歷nextVnode的時候用一個變量find=false表示是否能夠在prevVnode中找到節(jié)點稠炬，如果找到了就find=true焕阿。如果內層遍歷后find是false，那說明這是一個新的節(jié)點
function updateChildren (elm, prevChildren, nextChildren) {
let lastIndex = 0;
for (let i = 0; i < nextChildren.length; i++) {
let find = false;
const nextVnode = nextChildren[i];
for (let j = 0; j < prevChildren.length; j++) {
const prevVnode = prevChildren[j];
if (nextVnode.key === prevVnode.key) {
find = true;
patchVnode(nextVnode, prevVnode);
if (j < lastIndex) {
elm.insertBefore(prevVnode.elm, nextChildren[i-1].elm.nextSibling);
} else {
lastIndex = j;
}
}
}
if (!find) {
createElm(nextChildren[i], elm, nextChildren[i-1].elm.nextSibling);
}
}
}
我們的createElm函數需要判斷一下第四個參數首启，如果沒有就是用appendChild直接把元素放到父節(jié)點的最后暮屡，如果有第四個參數，則需要調用insertBefore來插入到正確的位置毅桃。
接下來要做的是刪除prevVnode多余節(jié)點：
在nextVnode中已經沒有l(wèi)i(d)了褒纲，我們需要在執(zhí)行完上面所講的所有流程后在遍歷一次prevVnode，然后拿到nextVnode里去找钥飞，如果找不到相同key的節(jié)點莺掠，那就說明這個節(jié)點已經被刪除了，我們直接用removeChild方法刪除Dom
function updateChildren (elm, prevChildren, nextChildren) {
let lastIndex = 0;
for (let i = 0; i < nextChildren.length; i++) {
let find = false;
const nextVnode = nextChildren[i];
for (let j = 0; j < prevChildren.length; j++) {
const prevVnode = prevChildren[j];
if (nextVnode.key === prevVnode.key) {
find = true;
patchVnode(nextVnode, prevVnode);
if (j < lastIndex) {
elm.insertBefore(prevVnode.elm, nextChildren[i-1].elm.nextSibling);
} else {
lastIndex = j;
}
}
}
if (!find) {
createElm(nextChildren[i], [], elm, nextChildren[i-1].elm.nextSibling);
}
}
for (const vnode of prevChildren) {
const has = nextChildren.find(child => child.key === vnode.key);
if (!has) {
elm.removeChild(vnode.elm);
}
}
}
完整的代碼：https://github.com/TingYinHelen/tempo/blob/main/src/platforms/web/patch.js
在react-diff分支(目前有可能代碼倉庫還沒有開源读宙，等我實現更完善的時候會開源出來彻秆，項目結構可能有變化，看tempo倉庫就行)
這里我的代碼實現的diff算法很明顯看出來時間復雜度是O(n2)结闸。那么這里在算法上依然又可以優(yōu)化的空間唇兑，這里我把nextChildren和prevChildren都設計成了數組的類型，這里可以把nextChildren桦锄、prevChildren設計成對象類型扎附，用戶傳入的key作為對象的key，把vnode作為對象的value结耀，這樣就可以只循環(huán)nextChildren留夜，然后通過prevChildren[key]的方式找到prevChidren中可復用的dom。這樣就可以把時間復雜度降到O(n)饼记。
以上就是react的diff算法的實現
下面來講一下vue2的diff算法
先說一下上面代碼的問題香伴，舉個例子，下面這個情況
如果按照react的方法具则，整個過程會移動2次：
li(c)是第一個節(jié)點，不需要移動具帮，lastIndex=2
li(b), j=1, j<lastIndex, 移動到li(c)后面 (第1次移動)
li(a), j=0, j<lastIndex, 移動到li(b)后面 (第2次移動)
但是通過肉眼來看博肋，其實只用把li(c)移動到第一個就行低斋，只需要移動1一次。
于是vue2這么來設計的
首先找到四個節(jié)點vnode：prev的第一個匪凡，next的第一個膊畴，prev的最后一個，next的最后一個病游，然后分別把這四個節(jié)點作比對：1. 把prev的第一個節(jié)點和next的第一個比對唇跨；2. 把prev的最后一個和next的最后一個比對；3.prev的第一個和next的最后一個衬衬；4. next的第一個和prev的最后一個买猖。如果找到相同key的vnode，就做移動滋尉，移動后把前面的指針往后移動玉控，后面的指針往前移動，直到前后的指針重合狮惜，如果key不相同就只patch更新vnodedata和children高诺。下面來走一下流程
- li(a)和li(b)，key不同碾篡，只patch虱而，不移動
- li(d)和li(c)，key不同开泽，只patch牡拇，不移動
- li(a)和li(c)，key不同眼姐，只patch诅迷，不移動
-
li(d)和li(d)，key相同众旗，先patch罢杉，需要移動移動，移動的方法就是把prev的li(d)移動到li(a)的前面贡歧。然后移動指針滩租，因為prev的最后一個做了移動，所以把prev的指向后面的指針往前移動一個利朵，因為next的第一個vnode已經找到了對應的dom律想，所以next的前面的指針往后移動一個。現在比對的圖變成了下面這樣：
這個時候的真實DOM
繼續(xù)比對
- li(a)和li(b)绍弟，key不同技即，只patch，不移動
-
li(c)和li(c)樟遣，相同相同而叼，先patch身笤，因為next的最后一個元素也剛好是prev的最后一個，所以不移動葵陵，prev和next都往前移動指針
這個時候真實DOM：
現在最新的比對圖：
繼續(xù)比對 - li(a)和li(b)液荸，key不同，只patch脱篙，不移動
- li(b)和li(a)娇钱，key不同，只patch绊困，不移動
-
li(a) 和li (a)文搂，key相同，patch考抄，把prev的li(a)移動到next的后面指針的元素的后面
真實的DOM變成了這樣
比對的圖變成這樣
繼續(xù)比對：
li(b)和li(b)的key相同细疚，patch，都是前指針相同所以不移動川梅，移動指針
這個時候前指針就在后指針后面了疯兼，這個比對就結束了。
function updateChildren (elm, prevChildren, nextChildren) {
let oldStartIndex = 0;
let oldEndIndex = prevChildren.length - 1;
let newStartIndex = 0;
let newEndIndex = nextChildren.length - 1;
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
const oldStartVnode = prevChildren[oldStartIndex];
const oldEndVnode = prevChildren[oldEndIndex];
const newStartVnode = nextChildren[newStartIndex];
const newEndVnode = nextChildren[newEndIndex];
if (oldStartVnode.key === newStartVnode.key) {
patchVnode(newStartVnode, oldStartVnode);
oldStartIndex++;
newStartIndex++;
} else if (oldEndVnode.key === newEndVnode.key) {
patchVnode(newEndVnode, oldEndVnode);
oldEndIndex--;
newEndIndex--;
} else if (oldStartVnode.key === newEndVnode.key) {
patchVnode(newEndVnode, oldStartVnode);
elm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
newEndIndex--;
oldStartIndex++;
} else if (oldEndVnode.key === newStartVnode.key) {
patchVnode(newStartVnode, oldEndVnode);
elm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
oldEndIndex--;
newStartIndex++;
}
}
}
這就完成了常規(guī)的比對贫途，還有不常規(guī)的吧彪，如下圖：
經過1，2丢早，3姨裸，4次比對后發(fā)現，沒有相同的key值能夠移動怨酝。
這種情況我們沒有辦法傀缩，只有用老辦法，用newStartIndex的key拿去依次到prev里的vnode农猬，直到找到相同key值的老的vnode赡艰，先patch，然后獲取真實dom移動到正確的位置(放到oldStartIndex前面)斤葱，然后在prevChildren中把移動過后的vnode設置為undefined慷垮，在下次指針移動到這里的時候直接跳過，并且next的start指針向右移動揍堕。
function updateChildren (elm, prevChildren, nextChildren) {
let oldStartIndex = 0;
let oldEndIndex = prevChildren.length - 1;
let newStartIndex = 0;
let newEndIndex = nextChildren.length - 1;
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
let oldStartVnode = prevChildren[oldStartIndex];
let oldEndVnode = prevChildren[oldEndIndex];
let newStartVnode = nextChildren[newStartIndex];
let newEndVnode = nextChildren[newEndIndex];
if (oldStartVnode === undefined) {
oldStartVnode = prevChildren[++oldStartIndex];
}
if (oldEndVnode === undefined) {
oldEndVnode = prevChildren[--oldEndIndex];
}
if (oldStartVnode.key === newStartVnode.key) {
patchVnode(newStartVnode, oldStartVnode);
oldStartIndex++;
newStartIndex++;
} else if (oldEndVnode.key === newEndVnode.key) {
patchVnode(newEndVnode, oldEndVnode);
oldEndIndex--;
newEndIndex--;
} else if (oldStartVnode.key === newEndVnode.key) {
patchVnode(newEndVnode, oldStartVnode);
elm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
newEndIndex--;
oldStartIndex++;
} else if (oldEndVnode.key === newStartVnode.key) {
patchVnode(newStartVnode, oldEndVnode);
elm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
oldEndIndex--;
newStartIndex++;
} else {
const idxInOld = prevChildren.findIndex(child => child.key === newStartVnode.key);
if (idxInOld >= 0) {
elm.insertBefore(prevChildren[idxInOld].elm, oldStartVnode.elm);
prevChildren[idxInOld] = undefined;
newStartIndex++;
}
}
}
}
接下來就是新增節(jié)點
這種排列方法料身，按照上面的方法，經過1衩茸，2芹血，3，4比對后找不到相同key，然后然后用newStartIndex到老的vnode中去找祟牲，仍然找不著隙畜，這個時候說明是一個新節(jié)點抖部，把它插入到oldStartIndex前面
const idxInOld = prevChildren.findIndex(child => child.key === newStartVnode.key);
if (idxInOld >= 0) {
elm.insertBefore(prevChildren[idxInOld].elm, oldStartVnode.elm);
prevChildren[idxInOld] = undefined;
} else {
createElm(newStartVnode, [], elm, oldStartVnode.elm);
}
newStartIndex++;
最后一步是移除多余dom
還是按照原來步驟進行比對
也就是說當newStartIndex > newEndIndex的時候就說明有dom需要刪除说贝，刪除的就是oldStartIndex 到 oldEndIndex。
if (oldEndIndex < oldStartIndex) {
for (let i = newStartIndex; i <= newEndIndex; i++) {
createElm(nextChildren[i], elm, oldStartVnode.elm);
}
} else if (newEndIndex < newStartIndex) {
for (let i = oldStartIndex; i <= oldEndIndex; i++) {
elm.removeChild(prevChildren[i].elm);
}
}
完整代碼
完整的代碼：https://github.com/TingYinHelen/tempo/blob/main/src/platforms/web/patch.js
vue2-diff分支
下面來講vue3的diff算法
vue3首先對chidren做了預處理慎颗，預處理其實就是去除相同的前綴和后綴乡恕，之比較不相同的部分
例如字符串:
abcd
abed
去除前面相同部分和后面相同部分，剩下不同的部分就是
c
e
應用到我們的children上也是同樣的俯萎，我們先實現最簡單情況
通過上圖可以看出傲宜，前面a是相同的，后面e夫啊，f是相同的函卒，去除前后相同的我們只用把中間新增的vnode insert進來就行。在預處理階段需要4個指針撇眯，分別指向prev的第一個和next的第一個报嵌，在前綴比較的時候，如果key相同熊榛，則只patch锚国，然后把這兩個指針依次向后移動。同樣需要兩個指針分別指向prev和next的最后一個vnode玄坦，如果兩個vnode key相同血筑，只patch，指針向前移動煎楣。
我們需要3個變量：j（指向前綴豺总，因為prev和next前綴比較的時候索引值相同，所以只需要一個變量）择懂，prevEnd（指向prev的后綴）喻喳，nextEnd（指向next的后綴）。
前綴a相同休蟹，j++沸枯，j=1的時候prev的元素是e，next的c這時key不同赂弓，這個循環(huán)結束绑榴。
接著循環(huán)遍歷后綴，第一次prevEnd=2,nextEnd=3相同盈魁，指針向前移動翔怎，prevEnd=1,nextEnd=2，key還是相同，指向向前移動,prevEnd=0,nextEnd=1赤套，key不同飘痛，循環(huán)結束
當prevEnd < j，說明next有元素需要新增容握，當nextEnd == j宣脉，說明next的j需要被新增
來看一下刪除
首先遍歷前綴，a的key相同剔氏，j++塑猖，j=1，b和c的key不同谈跛，前綴循環(huán)結束羊苟。后綴c的key相同，向前移動指針感憾，這個時候的圖變成這樣
如果j>nextEnd蜡励，就說明有元素需要刪除
function updateChildren (elm, prevChildren, nextChildren) {
let j = 0;
let prevEnd = prevChildren.length - 1;
let nextEnd = nextChildren.length - 1;
while (prevChildren[j].key === nextChildren[j].key) {
patchVnode(nextChildren[j], prevChildren[j]);
j++;
}
while (prevChildren[prevEnd].key === nextChildren[nextEnd].key) {
patchVnode(nextChildren[nextEnd--], prevChildren[prevEnd--]);
}
if (prevEnd < j || nextEnd === j) {
while (j <= nextEnd) {
createElm (nextChildren[j--], elm, prevChildren[prevEnd + 1].elm);
}
} else if (j > nextEnd) {
while (j <= prevEnd) {
elm.removeChild(prevChildren[j++].elm);
}
}
}
還有一種情況，如果在第一次循環(huán)的階段阻桅，j大于了nextEnd凉倚，那說明nextChildren整個都已經patch完，就可以不用在家進行后綴的遍歷鳍刷，如果j大于了prevEnd占遥，說明prevChildren整個都patch完成，也不用在繼續(xù)第二次循環(huán)输瓜；同樣瓦胎，在第二次循環(huán)的時候，有上面說的情況也不用再繼續(xù)執(zhí)行尤揣。出于性能考慮搔啊，我們應該避免沒有必要的代碼執(zhí)行。
outer: {
while (prevChildren[j].key === nextChildren[j].key) {
patchVnode(nextChildren[j], prevChildren[j]);
j++;
if (j > nextEnd || j > prevEnd) {
break outer;
}
}
while (prevChildren[prevEnd].key === nextChildren[nextEnd].key) {
patchVnode(nextChildren[nextEnd--], prevChildren[prevEnd--]);
if (j > nextEnd || j > prevEnd) {
break outer;
}
}
}
以上討論的是預處理時新增和刪除的特殊情況北戏。大多數情況并不能在預處理就結束比對负芋，所以下面來討論常規(guī)情況。
通過上面的分析嗜愈，可以知道無論什么框架旧蛾，diff算法的比對步驟是：先看有哪些vnode需要移動，然后考慮怎么移動蠕嫁，最后考慮新增和刪除的情況锨天。
看一下下面這種情況
通過預處理之后，a和e已經被比對剃毒，這個時候j<prevEnd并且j<nextEnd病袄，所以我們上面的實現不滿足搂赋，那么實現思路，
給一個source數組益缠，source的長度等于預處理之后nextChildren剩余未處理節(jié)點的長度脑奠，source元素的初始值都是-1
這個source數組的作用是用來存儲，新的children中的元素在老的chidren中的位置：
const prevStart = j;
const nextStart = j;
// 遍歷舊的children
for (let i = prevStart; i <= prevEnd; i++) {
const prevVnode = prevChildren[i];
// 遍歷新的children
for (let k = nextStart; k <= nextEnd; k++) {
const nextVnode = nextChildren[k];
// 找到擁有相同key值的vnode
if (prevVnode.key === nextVnode.key) {
// patch更新
patch(nextVnode, prevVnode);
source[k - nextStart] = i;
}
}
}
k代表的是在新的children中幅慌，遇到的節(jié)點的位置索引宋欺，用一個pos變量用來存儲當遇到key相同的vnode的時候，遇到的索引的最大值欠痴，一旦發(fā)現后面遇到的索引值比之前的要小迄靠，則說明需要移動，這時我們用一個變量move來記錄是否需要移動move=true喇辽，如果后面遇到的k比pos更大，則把k賦值給pos雨席。這里的思路和react類似菩咨。
這里之前已經說過，這里的時間復雜度是O(n2)陡厘。這里來優(yōu)化一下
我們可以為新的children節(jié)點抽米，構建一個key到位置索引索引表。
Index Map中的鍵是節(jié)點的key糙置，值是節(jié)點是在新的children中的位置索引云茸，由于數據結構帶來的優(yōu)勢，使我們可以快速的定位舊的children中的節(jié)點在新的children中的位置谤饭。
const prevStart = j;
const nextStart = j;
let pos = 0;
let move = false;
const keyIndex = {};
for (let i = nextStart; i < nextStart; i++) {
keyIndex[nextChildren[i].key] = i;
}
// 遍歷舊的children的剩余未處理節(jié)點
for (let i = prevStart; i <= prevEnd; i++) {
const prevVnode = prevChildren[i];
// 通過索引表快速找到新的children中key值相等的vnode的位置
const k = keyIndex[prevVnode.key]
if (k !== undefined) {
patch(nextChildren[k], prevVnode);
// 更新source數組
source[k - nextStart] = i;
if (pos > k) {
move = true;
} else {
pos = k;
}
} else {
// 刪除節(jié)點
}
}
現在的時間復雜度就是O(n)了标捺。接下來可以做操作Dom的操作了。
上面的邏輯中如果k是undefined揉抵，這里我們用prevChildren中的vnode在新的children中找亡容，找不著，那么就說明這是一個多余的vnode冤今，需要刪除
const prevStart = j;
const nextStart = j;
let pos = 0;
let move = false;
const keyIndex = {};
for (let i = nextStart; i < nextStart; i++) {
keyIndex[nextChildren[i].key] = i;
}
// 遍歷舊的children的剩余未處理節(jié)點
for (let i = prevStart; i <= prevEnd; i++) {
const prevVnode = prevChildren[i];
// 通過索引表快速找到新的children中key值相等的vnode的位置
const k = keyIndex[prevVnode.key]
if (k !== undefined) {
patch(nextChildren[k], prevVnode);
// 更新source數組
source[k - nextStart] = i;
if (pos > k) {
move = true;
} else {
pos = k;
}
} else {
elm.removeChild(prevChildren[i]);
}
}
接下來做移動操作
if (move) {
...
}
首先要做的是根據source計算一個最長遞增子序列闺兢。
if (move) {
const seq = lis(source) //
}
什么是最長遞增子序列：
給定一個數值序列，找到他的一個子序列戏罢，并且子序列中的值是遞增的屋谭，子序列中的元素在原序列中不一定連續(xù)。
比如給定序列：[0,8,4,12]
那么他的最長遞增子序列：[0,8,12]
當然答案可能有多種：[0,4,12]
我們調用lis函數后龟糕，求出數組source的最長遞增子序列是[0,1]桐磁。注：這里lis函數求的是source中最長遞增子序列的索引值。
[0,1]告訴我們nextChildren的未處理節(jié)點中翩蘸，位于位置0和位置1的節(jié)點所意，與他們在prevChildren中的先后順序是沒變的，在位置0 和位置1的節(jié)點是不需要移動的。
i和j分別指向新的children中剩余未處理節(jié)點的最后一個節(jié)點扶踊，和最長子序列的的最后一個泄鹏，并從后往前遍歷。
if (move) {
const seq = lis(source);
// j指向最長遞增子序列的最后一個
let j = seq.length - 1;
// 從后往前遍歷新children中的剩余未處理節(jié)點
for (let i = nextLeft - 1; i > 0; i--) {
if (i !== seq[j]) {
// 移動
} else {
j--;
}
}
}
i的值的范圍是0到nextLeft-1秧耗，等價于我們隊剩余節(jié)點重新編號备籽，接著看當前節(jié)點的索引是否與子序列中j相等。同時還需要注意source[i]是否為-1分井，是-1的節(jié)點需要新增车猬。
if (move) {
const seq = lis(source);
// j指向最長遞增子序列的最后一個
let j = seq.length - 1;
// 從后往前遍歷新children中的剩余未處理節(jié)點
for (let i = nextLeft - 1; i > 0; i--) {
if (source[i] === -1) {
// 該節(jié)點在新 children 中的真實位置索引
const pos = i + nextStart;
const nextVNode = nextChildren[pos]
const nextPos = pos + 1;
createElm(nextVNode, [], elm, nextChildren[nextPos].elm);
} else if (i !== seq[j]) {
// 該節(jié)點在新 children 中的真實位置索引
const pos = i + nextStart;
const nextVNode = nextChildren[pos];
// 該節(jié)點下一個節(jié)點的位置索引
const nextPos = pos + 1;
// 移動
elm.insertBefore(
nextVNode.el,
nextPos < nextChildren.length
? nextChildren[nextPos].elm
: null
)
} else {
j--;
}
}
}
