Vue diff算法 - 快速diff
简单介绍快速diff算法
该算法最早应用于ivi和inferno这两个框架，其在实测中的性能稍优于vue2所采用的双端diff算法，因此vue3借鉴并对它进行了扩展。
相同的前置元素和后置元素
不同于前边的diff算法，快速diff算法包含一个预处理的步骤，这其实是借鉴了纯文本diff的思路，在纯文本diff算法中，存在对两段文本进行预处理的过程。例如，在对两段文本进行diff之前，可以对两者进行全等比较，如果两段文本全等，就不需要进入核心的diff算法步骤了。除此之外预处理过程还会处理两段文本相同的前缀和后缀。例子如下
const before = "123 456 789"
const after = "123 654 789"
通过肉眼很容易发现，真正需要diff的部分是before: "456"和after:"654"。这其实是一种简单化的问题的一种方式，我们可以利用它轻松的处理文本的插入/删除，例如
const before = "123 "
const after = "123 456"
在经过预处理后，得到真正需要diff的部分before:""和after:"456"，before为空，说明after这部分为新插入的内容。反之，如果after为空，before这部分为需要删除的内容。
const oldNode = {
type: 'div',
children: [
{type: 'p', key: '1'},
{type: 'p', key: '2'},
{type: 'p', key: '3'}
]
}
const newNode = {
type: 'div',
children: [
{type: 'p', key: '1'},
{type: 'p', key: '4'},
{type: 'p', key: '2'},
{type: 'p', key: '3'}
]
}
经过预处理后会发现一个这样的关系，此时直接将这个节点插入到p - key：2节点之前即可完成diff算法。需要注意的是预处理时遇到key相同的节点也是需要对新旧进行patchNode操作的，以防节点内容发生变化。如下：
/**
*
* @param {新节点} newNode
* @param {旧节点} oldNode
* @param {父节点} container
*/
const patchChildren = (newNode, oldNode, container) => {
const newChildren = newNode.children;
const oldChildren = oldNode.children;
let startIndex = 0
let oldStartNode = oldChildren[startIndex]
let newStartNode = newChildren[startIndex]
let newEndIndex = newChildren.length - 1
let newEndNode = newChildren[newEndIndex]
let oldEndIndex = oldChildren.length - 1
let oldEndNode = oldChildren[oldEndIndex]
while(startIndex <= oldEndIndex && startIndex <= newEndIndex) {
if (newStartNode.key !== oldStartNode.key) break;
patchNode(newStartNode, oldStartNode, container)
startIndex++
newStartNode = newChildren[startIndex]
oldStartNode = oldChildren[startIndex]
}
while(startIndex <= oldEndIndex && startIndex <= newEndIndex) {
if (newEndNode.key !== oldEndNode.key) break;
patchNode(newEndNode, oldEndNode, container)
newEndNode = newChildren[--newEndIndex]
oldEndNode = oldChildren[--oldEndIndex]
}
if (startIndex > oldEndIndex && startIndex <= newEndIndex) {
// newStartIndex到newEndIndex之间的dom节点是需要新插入的
// 可以将他们依次插到oldStartNode对应的dom元素之前
while(startIndex <= newEndIndex) {
patchNode(newChildren[startIndex], null, container, oldStartNode.el)
startIndex++
}
} else if (startIndex <= oldEndIndex && startIndex > newEndIndex) {
// oldStartIndex到oldEndIndex之间的dom节点是需要删除掉的
while(startIndex <= oldEndIndex) {
unmount(oldChildren[startIndex])
startIndex++
}
} else if (startIndex <= newEndIndex && startIndex <= oldEndIndex) {
// 预处理阶段结束，开始真正的diff核心算法
}
};
判断是否需要进行DOM移动操作
以上示例比较理想化，在下边例子中肉眼可以见增加了一个key:7的节点同时少了一个key:6的节点，此时就无法通过预处理过程来完成更新。
const oldNode = {
type: 'div',
children: [
{type: 'p', key: '1'},
{type: 'p', key: '2'},
{type: 'p', key: '3'}，
{type: 'p', key: '4'},
{type: 'p', key: '6'},
{type: 'p', key: '5'},
]
}
const newNode = {
type: 'div',
children: [
{type: 'p', key: '1'},
{type: 'p', key: '3'},
{type: 'p', key: '4'}，
{type: 'p', key: '2'},
{type: 'p', key: '7'},
{type: 'p', key: '5'},
]
}
首先将两个列表进行预处理，结果就是下图的样子了
vue3给出的解决方案是引入一个source数组，其长度为newEndIndex - startIndex + 1，记录了newChildren[startIndex -> newEndIndex]所有节点在oldChildren中所对应的下标，若newChildren[xxx]为新元素则将newChildren[xxx]的值记录为-1。示例图如下所示：
生成source数组的方法首先可以想到遍历newChildren每一轮循环中都需要去遍历oldChildren，得到对应的下标，此种方法的复杂度是O(n²)。因此我们可以先建立一个索引表，节点的key做key，其在newChildren中对应的下标做value。有了这个索引表，再去遍历oldChildren，只需要O(n)的复杂度就能构造出数组source数组了。对应的代码如下：
const patchChildren = (newNode, oldNode, container) => {
......
if (startIndex > oldEndIndex && startIndex <= newEndIndex) {
......
} else if (startIndex <= oldEndIndex && startIndex > newEndIndex) {
......
} else if (startIndex <= newEndIndex && startIndex <= oldEndIndex) {
// 预处理阶段结束，开始真正的diff核心算法
const source = new Array(newEndIndex - startIndex + 1).fill(-1)
const keyMap = {}
for(let index = startIndex; index <= newEndIndex; index++) {
keyMap[newChildren[index].key] = index
}
for(let index = startIndex; index <= oldEndIndex; index++) {
const key = oldChildren[index].key
if (keyMap.hasOwnproperty(key)) {
// 满足这个条件，就说明旧的node节点可以复用，可以先将新旧节点进行patch
patchNode(newChildren[keyMap[key]], oldChildren[index], container)
// patchNode结束后已经将节点内容更新，但节点位置还没有进行移动，先填充source数组
source[keyMap[key] - startIndex] = index
} else {
// 当前node节点不可复用的话可以直接将其对应的dom元素卸载掉
unmount(oldChildren[index])
}
}
}
};
此时source数组已经形成，那么到底如何去判断节点的移动呢？vue3又增加了三个变量，分别是pos，moved，patched。pos代表已遍历的节点中在newChildren最大的索引值，moved代表是否有需要移动的节点，patched代表已处理完的新节点数量。改进后的代码如下：
const patchChildren = (newNode, oldNode, container) => {
......
if (startIndex > oldEndIndex && startIndex <= newEndIndex) {
......
} else if (startIndex <= oldEndIndex && startIndex > newEndIndex) {
......
} else if (startIndex <= newEndIndex && startIndex <= oldEndIndex) {
// 预处理阶段结束，开始真正的diff核心算法
const count = newEndIndex - startIndex + 1 // 需要处理的新节点总数
const source = new Array(count).fill(-1)
const keyMap = {}
for(let index = startIndex; index <= newEndIndex; index++) {
keyMap[newChildren[index].key] = index
}
let moved = false, pos = 0, patched = 0
for(let index = startIndex; index <= oldEndIndex; index++) {
if (patched < count) {
const key = oldChildren[index].key
if (keyMap.hasOwnproperty(key)) {
// 满足这个条件，就说明旧的node节点可以复用，可以先将新旧节点进行patch
patchNode(newChildren[keyMap[key]], oldChildren[index], container)
// patchNode结束后已经将节点内容更新，但节点位置还没有进行移动，先填充source数组
source[keyMap[key] - startIndex] = index
// 每处理完一个新节点patched自增一次
patched++
if (keyMap[key] < pos) {
moved = true
} else {
pos = keyMap[key]
}
} else {
// 当前node节点不可复用的话可以直接将其对应的dom元素卸载掉
unmount(oldChildren[index])
}
} else {
// patched数量够了，可以直接将目前的节点卸载掉了。
unmount(oldChildren[index])
}
}
}
};
如何进行DOM移动操作 目前我们实现了两个前置目标，1. 用moved变量标记当前列表是否需要dom移动操作。2. source数组也已经形成。接下来需要计算出source中最长递增子序列并返回它们的下标，用于DOM移动的操作。一顿操作完成后得到的列表用变量seq接收，上述例子中source数组为[2, 3, 1, -1]，因此seq为[0, 1]。然后引入i和s两个变量，从大到小遍历i，如果i !== seq[s]将i对应的node移动到上一个处理过的node(即newChildren[startIndex + i + 1])之前，i--；若i === seq[s],则代表该节点不需要移动，s--,i--；示例图如下：
除此之外还需要考虑到特殊情况source[x] = -1说明此的节点为新节点，没有DOM可以复用，此时应该将其插入到上一个处理过的node(即newChildren[startIndex + i + 1])之前，对应的代码如下：
const patchChildren = (newNode, oldNode, container) => {
......
if (startIndex > oldEndIndex && startIndex <= newEndIndex) {
......
} else if (startIndex <= oldEndIndex && startIndex > newEndIndex) {
......
} else if (startIndex <= newEndIndex && startIndex <= oldEndIndex) {
// 预处理阶段结束，开始真正的diff核心算法
const count = newEndIndex - startIndex + 1 // 需要处理的新节点总数
const source = new Array(count).fill(-1)
const keyMap = {}
for(let index = startIndex; index <= newEndIndex; index++) {
keyMap[newChildren[index].key] = index
}
let moved = false, pos = 0, patched = 0
for(let index = startIndex; index <= oldEndIndex; index++) {
......
}
if (moved) {
const seq = lis(source)
let s = seq.length - 1
let i = count - 1
while(i >= 0) {
if (source[i] === -1) {
const anchor = newChildren[startIndex + i + 1]
patchNode(newChildren[startIndex + i], null, contianer, anchor? anchor.el : null)
} else {
if (i !== seq[s]) {
const anchor = newChildren[startIndex + i + 1]
insert(newChildren[startIndex + i].el, contianer, anchor? anchor.el : null)
} else {
s--
}
}
i--
}
}
}
};
总结
快速diff算法在实测中性能最优，它借鉴了文本diff中预处理的思路，先处理新旧子节点中相同的前置和后置节点。然后根据节点索引与key的关系构建出最长递增子序列，而最长子序列所指的节点即为不需要移动的节点。
附：计算最长子序列下标算法示例
const lis = (list) => {
const res = [[0]]
let max = 0
for (let i = 1; i < list.length; i++) {
let maxIndex = -1
for(let j = i - 1; j >= 0; j--) {
if ((maxIndex < 0 || res[j].length > res[maxIndex].length) && list[res[j][res[j].length - 1]] < list[i]) maxIndex = j
}
res.push([...(res[maxIndex] || []), i])
if (res[max].length < res[i].length) max = i
}
return res[max]
}
转载自:https://juejin.cn/post/7267512263879016504