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; //返回最长递增子序列的长度

上节函数中，dp[i] 存储的是长度为 i+1 的递增子序列中末尾的元素值。若存在多个长度为 i+1 的递增子序列，我们选择末尾值最小的那个进行存储，因为末尾值越小，越有可能在其后面追加其他元素。通过二分搜索，我们保证了 dp[] 数组在遍历的过程中，始终保持递增的状态。

以上就是文章全部内容了，如果喜欢这篇文章的话，还希望三连支持一下，感谢！