查找相同前后綴
- 如上圖所示，新舊 children 擁有相同的前綴節(jié)點(diǎn)和后綴節(jié)點(diǎn)
- 對(duì)于前綴節(jié)點(diǎn)，我們可以建立一個(gè)索引，指向新舊 children 中的第一個(gè)節(jié)點(diǎn)，并逐步向后遍歷，直到遇到兩個(gè)擁有不同 key 值的節(jié)點(diǎn)為止
// 更新相同的前綴節(jié)點(diǎn)
// j 為指向新舊 children 中第一個(gè)節(jié)點(diǎn)的索引
let j = 0
let prevVNode = prevChildren[j]
let nextVNode = nextChildren[j]
// while 循環(huán)向后遍歷，直到遇到擁有不同 key 值的節(jié)點(diǎn)為止
while (prevVNode.key === nextVNode.key) {
// 調(diào)用 patch 函數(shù)更新
patch(prevVNode, nextVNode, container)
j++
prevVNode = prevChildren[j]
nextVNode = nextChildren[j]
}
- 對(duì)于相同的后綴節(jié)點(diǎn)，由于新舊 children 中節(jié)點(diǎn)的數(shù)量可能不同，所以我們需要兩個(gè)索引分別指向新舊 children 的最后一個(gè)節(jié)點(diǎn)，并逐步向前遍歷，直到遇到兩個(gè)擁有不同 key 值的節(jié)點(diǎn)為止
// 更新相同的后綴節(jié)點(diǎn)
// 指向舊 children 最后一個(gè)節(jié)點(diǎn)的索引
let prevEnd = prevChildren.length - 1
// 指向新 children 最后一個(gè)節(jié)點(diǎn)的索引
let nextEnd = nextChildren.length - 1
prevVNode = prevChildren[prevEnd]
nextVNode = nextChildren[nextEnd]
// while 循環(huán)向前遍歷，直到遇到擁有不同 key 值的節(jié)點(diǎn)為止
while (prevVNode.key === nextVNode.key) {
// 調(diào)用 patch 函數(shù)更新
patch(prevVNode, nextVNode, container)
prevEnd--
nextEnd--
prevVNode = prevChildren[prevEnd]
nextVNode = nextChildren[nextEnd]
}
通過(guò)前后綴位置信息新增節(jié)點(diǎn)
// 前綴節(jié)點(diǎn)終止位置
j: 1
// 后綴節(jié)點(diǎn)終止位置
prevEnd: 0
nextEnd: 1
- 發(fā)現(xiàn) j > prevEnd 并且 j <= nextEnd，這說(shuō)明當(dāng)新舊 children 中相同的前綴和后綴被更新之后，舊 children 中的節(jié)點(diǎn)已經(jīng)被更新完畢了，而新 children 中仍然有剩余節(jié)點(diǎn)，通過(guò)上圖可以發(fā)現(xiàn)，新 children 中的 li-d 節(jié)點(diǎn)，就是這個(gè)剩余的節(jié)點(diǎn)。實(shí)際上新 children 中位于 j 到 nextEnd 之間的所有節(jié)點(diǎn)都應(yīng)該是新插入的節(jié)點(diǎn)：
// 滿足條件，則說(shuō)明從 j -> nextEnd 之間的節(jié)點(diǎn)應(yīng)作為新節(jié)點(diǎn)插入
if (j > prevEnd && j <= nextEnd) {
// 所有新節(jié)點(diǎn)應(yīng)該插入到位于 nextPos 位置的節(jié)點(diǎn)的前面
const nextPos = nextEnd + 1
const refNode =
nextPos < nextChildren.length ? nextChildren[nextPos].el : null
// 采用 while 循環(huán)，調(diào)用 mount 函數(shù)掛載節(jié)點(diǎn)
while (j <= nextEnd) {
mount(nextChildren[j++], container, false, refNode)
}
}
通過(guò)前后綴位置信息刪除節(jié)點(diǎn)
- 在這個(gè)案例中，當(dāng)“去掉”相同的前綴和后綴之后，三個(gè)索引的值為：
j: 1
prevEnd: 1
nextEnd: 0
- 這時(shí)條件 j > nextEnd 并且 j <= prevEnd 成立，通過(guò)上圖可以很容的發(fā)現(xiàn)，舊 children 中的 li-b 節(jié)點(diǎn)應(yīng)該被移除，實(shí)際上更加通用的規(guī)則應(yīng)該是：在舊 children 中有位于索引 j 到 prevEnd 之間的節(jié)點(diǎn)，都應(yīng)該被移除
if (j > prevEnd && j <= nextEnd) {
// j -> nextEnd 之間的節(jié)點(diǎn)應(yīng)該被添加
const nextPos = nextEnd + 1
const refNode =
nextPos < nextChildren.length ? nextChildren[nextPos].el : null
while (j <= nextEnd) {
mount(nextChildren[j++], container, false, refNode)
}
} else if (j > nextEnd) {
// j -> prevEnd 之間的節(jié)點(diǎn)應(yīng)該被移除
while (j <= prevEnd) {
container.removeChild(prevChildren[j++].el)
}
}
- 假設(shè)在第一個(gè) while 循環(huán)結(jié)束之后，索引 j 的值已經(jīng)大于 prevEnd 或 nextEnd，那么還有必須執(zhí)行第二個(gè) while 循環(huán)嗎？答案是沒(méi)有必要，這是因?yàn)橐坏┧饕?j 大于 prevEnd 則說(shuō)明舊 children 中的所有節(jié)點(diǎn)都已經(jīng)參與了 patch，類(lèi)似的，如果索引 j 大于 nextEnd 則說(shuō)明新 children 中的所有節(jié)點(diǎn)都已經(jīng)參與了 patch，這時(shí)當(dāng)然沒(méi)有必要再執(zhí)行后續(xù)的操作了。
while (prevVNode.key === nextVNode.key) {
patch(prevVNode, nextVNode, container)
j++
if (j > prevEnd || j > nextEnd) {
break;
}
prevVNode = prevChildren[j]
nextVNode = nextChildren[j]
}
// 更新相同的后綴節(jié)點(diǎn)
prevVNode = prevChildren[prevEnd]
nextVNode = nextChildren[nextEnd]
while (prevVNode.key === nextVNode.key) {
patch(prevVNode, nextVNode, container)
prevEnd--
nextEnd--
if (j > prevEnd || j > nextEnd) {
break outer
}
prevVNode = prevChildren[prevEnd]
nextVNode = nextChildren[nextEnd]
}
if(!(j > prevEnd && j>prevEnd)){
// 滿足條件，則說(shuō)明從 j -> nextEnd 之間的節(jié)點(diǎn)應(yīng)作為新節(jié)點(diǎn)插入
if (j > prevEnd && j <= nextEnd) {
// j -> nextEnd 之間的節(jié)點(diǎn)應(yīng)該被添加
// 省略...
} else if (j > nextEnd) {
// j -> prevEnd 之間的節(jié)點(diǎn)應(yīng)該被移除
// 省略...
}
}
中間部份 diff
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-639871.html
- 首先，我們需要構(gòu)造一個(gè)數(shù)組 source，該數(shù)組的長(zhǎng)度等于新 children 在經(jīng)過(guò)預(yù)處理之后剩余未處理節(jié)點(diǎn)的數(shù)量，初始化該數(shù)組中每個(gè)元素的初始值為 -1
- 實(shí)際上 source 數(shù)組將用來(lái)存儲(chǔ)新 children 中的節(jié)點(diǎn)在舊 children 中的位置，后面將會(huì)使用它計(jì)算出一個(gè)最長(zhǎng)遞增子序列，并用于 DOM 移動(dòng)
- 再建立一個(gè) Index Map 中的鍵是節(jié)點(diǎn)的 key，值是節(jié)點(diǎn)在新 children 中的位置索引，用空間來(lái)?yè)Q取時(shí)間上的優(yōu)化
if (j > prevEnd && j <= nextEnd) {
// 省略...
} else if (j > nextEnd) {
// 省略...
} else {
// 構(gòu)造 source 數(shù)組
const nextLeft = nextEnd - j + 1 // 新 children 中剩余未處理節(jié)點(diǎn)的數(shù)量
const source = []
for (let i = 0; i < nextLeft; i++) {
source.push(-1)
}
const prevStart = j
const nextStart = j
let moved = false
let pos = 0
// 構(gòu)建索引表
const keyIndex = {}
for(let i = nextStart; i <= nextEnd; i++) {
keyIndex[nextChildren[i].key] = i
}
// 遍歷舊 children 的剩余未處理節(jié)點(diǎn)
for(let i = prevStart; i <= prevEnd; i++) {
prevVNode = prevChildren[i]
// 通過(guò)索引表快速找到新 children 中具有相同 key 的節(jié)點(diǎn)的位置
const k = keyIndex[prevVNode.key]
if (typeof k !== 'undefined') {
nextVNode = nextChildren[k]
// patch 更新
patch(prevVNode, nextVNode, container)
// 更新 source 數(shù)組
source[k - nextStart] = i
// 判斷是否需要移動(dòng)
if (k < pos) {
moved = true
} else {
pos = k
}
} else {
// 沒(méi)找到
}
}
}
判斷節(jié)點(diǎn)是否需要移動(dòng)
- 在上一步代碼中，遍歷舊 children 的剩余未處理節(jié)點(diǎn)，通過(guò)索引表快速找到新 children 中具有相同 key 的節(jié)點(diǎn)的位置
- 如果新舊節(jié)點(diǎn)位置沒(méi)有變化，那么位置信息應(yīng)該是相同的，否則，新節(jié)點(diǎn)索引表信息為[1,2,3,4]，如果映射成舊節(jié)點(diǎn)為[1,2,4,3]，說(shuō)明舊節(jié)點(diǎn)的最后一個(gè)位置和前面的位置互換了，說(shuō)明節(jié)點(diǎn)移動(dòng)了
const prevStart = j
const nextStart = j
let moved = false
let pos = 0
// 構(gòu)建索引表
const keyIndex = {}
for(let i = nextStart; i <= nextEnd; i++) {
keyIndex[nextChildren[i].key] = i
}
// 遍歷舊 children 的剩余未處理節(jié)點(diǎn)
for(let i = prevStart; i <= prevEnd; i++) {
prevVNode = prevChildren[i]
// 通過(guò)索引表快速找到新 children 中具有相同 key 的節(jié)點(diǎn)的位置
const k = keyIndex[prevVNode.key]
if (typeof k !== 'undefined') {
nextVNode = nextChildren[k]
// patch 更新
patch(prevVNode, nextVNode, container)
// 更新 source 數(shù)組
source[k - nextStart] = i
// 判斷是否需要移動(dòng)
if (k < pos) {
moved = true
} else {
pos = k
}
} else {
// 沒(méi)找到
}
}
刪除節(jié)點(diǎn)
刪除未查找到的節(jié)點(diǎn)
- 拿舊 children 中的節(jié)點(diǎn)嘗試去新 children 中尋找具有相同 key 值的節(jié)點(diǎn)，但并非總是能夠找得到，當(dāng) k === ‘undefined’ 時(shí)，說(shuō)明該節(jié)點(diǎn)在新 children 中已經(jīng)不存在了，這時(shí)我們應(yīng)該將其移除
// 遍歷舊 children 的剩余未處理節(jié)點(diǎn)
for(let i = prevStart; i <= prevEnd; i++) {
prevVNode = prevChildren[i]
// 通過(guò)索引表快速找到新 children 中具有相同 key 的節(jié)點(diǎn)的位置
const k = keyIndex[prevVNode.key]
if (typeof k !== 'undefined') {
// 省略...
} else {
// 沒(méi)找到，說(shuō)明舊節(jié)點(diǎn)在新 children 中已經(jīng)不存在了，應(yīng)該移除
container.removeChild(prevVNode.el)
}
}
刪除多余節(jié)點(diǎn)
- 舊 children 中已經(jīng)更新過(guò)的節(jié)點(diǎn)數(shù)量應(yīng)該小于新 children 中需要更新的節(jié)點(diǎn)數(shù)量，一旦更新過(guò)的節(jié)點(diǎn)數(shù)量超過(guò)了新 children 中需要更新的節(jié)點(diǎn)數(shù)量，則說(shuō)明該節(jié)點(diǎn)是多余的節(jié)點(diǎn)，我們也應(yīng)該將其移除
const nextLeft = nextEnd - j + 1 // 新 children 中剩余未處理節(jié)點(diǎn)的數(shù)量
let patched = 0
// 遍歷舊 children 的剩余未處理節(jié)點(diǎn)
for (let i = prevStart; i <= prevEnd; i++) {
prevVNode = prevChildren[i]
if (patched < nextLeft) {
// 通過(guò)索引表快速找到新 children 中具有相同 key 的節(jié)點(diǎn)的位置
const k = keyIndex[prevVNode.key]
if (typeof k !== 'undefined') {
nextVNode = nextChildren[k]
// patch 更新
patch(prevVNode, nextVNode, container)
patched++
// 更新 source 數(shù)組
source[k - nextStart] = i
// 判斷是否需要移動(dòng)
if (k < pos) {
moved = true
} else {
pos = k
}
} else {
// 沒(méi)找到，說(shuō)明舊節(jié)點(diǎn)在新 children 中已經(jīng)不存在了，應(yīng)該移除
container.removeChild(prevVNode.el)
}
} else {
// 多余的節(jié)點(diǎn)，應(yīng)該移除
container.removeChild(prevVNode.el)
}
}
移動(dòng)和新增節(jié)點(diǎn)
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-639871.html
最長(zhǎng)遞增子序列
- source 數(shù)組的值為 [2, 3, 1, -1]，很顯然最長(zhǎng)遞增子序列應(yīng)該是 [ 2, 3 ]，換算成位置信息是 [ 0, 1 ]
- 而最長(zhǎng)遞增子序列是 [ 0, 1 ] 這告訴我們：新 children 的剩余未處理節(jié)點(diǎn)中，位于位置 0 和位置 1 的節(jié)點(diǎn)的先后關(guān)系與他們?cè)谂f children 中的先后關(guān)系相同?；蛘呶覀兛梢岳斫鉃槲挥谖恢?0 和位置 1 的節(jié)點(diǎn)是不需要被移動(dòng)的節(jié)點(diǎn)
- 只有 li-b 節(jié)點(diǎn)和 li-g 節(jié)點(diǎn)是可能被移動(dòng)的節(jié)點(diǎn)，但是我們發(fā)現(xiàn)與 li-g 節(jié)點(diǎn)位置對(duì)應(yīng)的 source 數(shù)組元素的值為 -1，這說(shuō)明 li-g 節(jié)點(diǎn)應(yīng)該作為全新的節(jié)點(diǎn)被掛載，所以只有 li-b 節(jié)點(diǎn)需要被移動(dòng)
- 使用 for 循環(huán)從后向前遍歷新 children 中剩余未處理的子節(jié)點(diǎn)
- 這里的技巧在于 i 的值的范圍是 0 到 nextLeft - 1，這實(shí)際上就等價(jià)于我們對(duì)剩余節(jié)點(diǎn)進(jìn)行了重新編號(hào)。接著判斷當(dāng)前節(jié)點(diǎn)的位置索引值 i 是否與子序列中位于 j 位置的值相等，如果不相等，則說(shuō)明該節(jié)點(diǎn)需要被移動(dòng)；如果相等則說(shuō)明該節(jié)點(diǎn)不需要被移動(dòng)，并且會(huì)讓 j 指向下一個(gè)位置
- 節(jié)點(diǎn)需要被怎么移動(dòng)呢？找到 li-b 節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)(li-g)，將其插入到 li-g 節(jié)點(diǎn)的前面即可
if (moved || source.indexOf(-1)!==-1) {
// 根據(jù) source 數(shù)組計(jì)算一個(gè)最長(zhǎng)遞增子序列：
const seq = lis(sources) // [ 0, 1 ],代表的是最長(zhǎng)遞增子序列中的各個(gè)元素在 source 數(shù)組中的位置索引
let j = seq.length - 1
// 從后向前遍歷新 children 中的剩余未處理節(jié)點(diǎn)
for (let i = nextLeft - 1; i >= 0; i--) {
if (source[i] === -1) {
// 作為全新的節(jié)點(diǎn)掛載
// 該節(jié)點(diǎn)在新 children 中的真實(shí)位置索引
const pos = i + nextStart
const nextVNode = nextChildren[pos]
// 該節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)的位置索引
const nextPos = pos + 1
// 掛載
mount(
nextVNode,
container,
false,
nextPos < nextChildren.length
? nextChildren[nextPos].el
: null
)
} else if (i !== seq[j]) {
// 說(shuō)明該節(jié)點(diǎn)需要移動(dòng)
// 該節(jié)點(diǎn)在新 children 中的真實(shí)位置索引
const pos = i + nextStart
const nextVNode = nextChildren[pos]
// 該節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)的位置索引
const nextPos = pos + 1
// 移動(dòng)
container.insertBefore(
nextVNode.el,
nextPos < nextChildren.length
? nextChildren[nextPos].el
: null
)
} else {
// 當(dāng) i === seq[j] 時(shí)，說(shuō)明該位置的節(jié)點(diǎn)不需要移動(dòng)
// 并讓 j 指向下一個(gè)位置
j--
}
}
}
}
求解最長(zhǎng)遞增子序列位置信息
[ 0, 8, 4, 12, 2, 10]
// 最長(zhǎng)遞增子序列長(zhǎng)度
[ 3, 2, 2, 1, 2, 1]
- 如上可知最長(zhǎng)子序列長(zhǎng)度為 3，從右往左遍歷查找子序列長(zhǎng)度為2位置，接著查找為1的位置，這樣就能找到所有的位置信息
// 所有的最長(zhǎng)遞增子序列
[ 0, 8, 12 ]
[ 0, 8, 10 ]
[ 0, 4, 12 ]
[ 0, 4, 10 ]
[ 0, 2, 10 ]
到了這里，關(guān)于vue diff 前后綴+最長(zhǎng)遞增子序列算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
