Vue diff算法

本文主要是介绍Vue diff算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

vue diff算法主要体现在renderer.ts中的patchChildren这段代码逻辑。差异算法排序分为无key时的diff算法排序逻辑和有key时的diff算法排序逻辑。无key时的逻辑主要有三步，首先，通过for循环patch重新渲染元素进行替换，其次是删除旧的元素，再次是新增元素。
代码如下：

const patchUnkeyedChildren = ( c1: VNode[], c2: VNodeArrayChildren, container: RendererElement, anchor: RendererNode | null, parentComponent: ComponentInternalInstance | null, parentSuspense: SuspenseBoundary | null, isSVG: boolean, slotScopeIds: string[], optimized: boolean ) => {c1 = c1 || EMPTY_ARR c2 = c2 || EMPTY_ARR const oldLength = c1.length const newLength = c2.length const commonLength = Math.min(oldLength, newLength) for (let i = 0; i < commonLength; i++) { const nextChild = (c2[i] = optimized ? cloneIfMounted(c2[i] as VNode) : normalizeVNode(c2[i])) patch( c1[i], nextChild, container, null , parentComponent, parentSuspense, isSVG, slotScopeIds, optimized ) } if (oldLength > newLength) { unmountChildren( c1, parentComponent, parentSuspense, true , false , commonLength ) } else { mountChildren( c2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized, commonLength ) } }

当节点有key时，排序逻辑如下：
1. 前序算法: 前面的元素与后面的元素比较，若不同，则跳出循环。
2. 尾序算法: 尾部与尾部比较，若不同，跳出循环。
3. 若新节点多出来，则将其挂载（即新增）。
4. 若旧节点多出来，则将其卸载（即删除）。
5. 在有key的情况下，乱序(涉及最长递增子序列算法)，此过程包括构建新节点的映射关系等步骤。

代码示例：

let j 
let patched = 0 
const toBePatched = e2 - s2 + 1 
let moved = false 
let maxNewIndexSoFar = 0
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0

最长递增子序列（Longest Increasing Subsequence）

需要一个数组来存储新序列新的索引到旧的索列旧的索引的映射关系。即，newIndexToOldIndexMap变量，它的初始化方式如下：

const toBePatched = e2 - s2 + 1; // e2和s2分别是新旧节点数组的结束和开始索引
let newIndexToOldIndexMap = new Array(toBePatched).fill(0); //初始化映射表

然后在遍历过程中，如果新的VNode与旧的VNode相同，我们将更新这个映射表，如下所示：

newIndexToOldIndexMap[i - s2] = oldIndex + 1;

接下来，我们需要用到一个辅助函数，用来获取最长递增子序列。我们使用动态规划（DP）和二分搜索（Binary Search）来实现这个功能。

对于最长递增子序列的问题，通常我们会用到动态规划（DP）或二分搜索（Binary Search）的方法。下面的代码是一个常规的DP解决方案：

假设 sequence 是输入的数组，length 是数组的长度，我们维护一个 dp 数组来表示以 i 结尾的最长递增子序列的长度：

  let dp = Array(sequence.length).fill(1);for (let i = 1; i < sequence.length; i++) {for (let j = 0; j < i; j++) {if (sequence[i] > sequence[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}}return Math.max(...dp);

然而，这个算法的时间复杂度是 O(n^2)，若数组的长度很大，可能会非常耗时。为了提高效率，我们可以使用二分搜索的方式，下面是其代码实现以及相应的注释：

let dp = [], len = sequence.length;
for(let i = 0; i < len; i++) {let low = 0, high = dp.length, mid;while(low < high) { //进行二分查找mid = (low + high) >>> 1;if(dp[mid] < sequence[i]) low = mid + 1;  //若当前值大于中间值，则在后半段查找else high = mid;    //否则在前半段查找}dp[low] = sequence[i]; //更新对应位置的值if(low === dp.length)  //若low等于当前dp数组的长度，说明该值可以拓展当前的递增序列dp.push(sequence[i]);
}
return dp.length; //返回最长递增子序列的长度