Vue3 中的 diff 实现与优化

关键词
-  最小递增子序列
- 贪心
- 二分查找

先谈一道题

最长递增子序列 （lc.300)

• 解法一、dp
• 解法二、贪心+二分 贪心思想：[1,2] 比 [1,4] 好，[1,2]更有潜力，因为我们想让他递增得慢点 【思路】： 建一个tail数组 存放最长递增子序列 如果（1） 当前tail[tail.length-1] < nums[i] ,nums[i]push 到最后 否则（2） 查找tail数组中比nums[i]大的第一个数，nums[i]替换掉这个数 (前面说到的让他递增慢点)

function lcs(arr) {
  let length = arr.length;
  if (length <= 1) {
    return length;
  }
  let tails = [arr[0]];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > tails[tails.length - 1]) {
      tails.push(arr[i]);
    } else {
      //二分
      let left = 0,
        right = tails.length;
      while (left < right) {
        let mid = (left + (right - left)) >> 1;
        if (arr[i] < tails[mid]) {
          right = mid;
        } else {
          left = mid + 1;
        }
      }
      tails[left] = arr[i];
    }
  }
  return tails.length;
}

注意：这种方式被替换后组成的新数组不一定是解法一中正确结果的数组，但长度是一样的，不影响我们对此题求解。因为最后一步破坏了子序列的性质了。

vue3 中 diff 的核心算法

1.思考 ： vue 中使用diff的目的？ 「为了减少 DOM 操作的性能开销，我们要尽可能的复用 DOM 元素。所以我们需要判断出是否有节点需要移动，应该如何移动以及找出那些需要被添加或删除的节点。」 2.思考： diff发生在什么时候 「旧 vnode 有 children，新 vnode 有 children，更新的时候」

//packages/runtime-core/src/renderer.ts
function getSequence(arr) {
  let p = arr.slice();
  const result = [0];
  let u; //left
  let v; //right
  let c; //mid
  for (let i = 0; i < arr.length; i++) {
    let arrI = arr[i];
    if (arrI != 0) {
      let j = result[result.length - 1];
      if (arrI > arr[j]) {
        p[i] = j;
        result.push(i);
        continue;
      }
    } else {
      u = 0;
      v = result.length - 1;
      while (u < v) {
        c = ((u + v) / 2) | 0;
        if (arr[result[c]] < arrI) {
          u = c + 1;
        } else {
          v = c;
        }
      }
      // 比较 => 替换
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]; // 正确的结果
        } 
        result[u] = i;// 有可能替换会导致结果不正确，需要一个新数组 p 记录正确的结果
      }
      u=result.length
      v= result[u-1]
      // 倒叙回溯 用 p 覆盖 result 进而找到最终正确的索引
      while(u-->0)
      {
        result[u] =v;
        v = p[v]
      }
    }
  }
  return result;
}

getSequence 找到那些有序不需要更改的元素下标 注意：理解这个p:[]:1、是保存前驱节点 通过p回溯找到正确的最长子序列的索引 例子

 [2,3,1,5,6,8,7,9,4]
2
2 3 
1 3 (二分替换掉2)
1 3 5
1 3 5 6
1 3 5 6 8
1 3 5 6 7（二分替换掉8）
1 3 5 6 7 9 
1 3 4 6 7 9（二分替换掉5）
--------------------------
正确结果：  2 3 5 6 7 9

这里引入 p：【】（下面的preIndexArr）
往result push或者替换的时候，往p添项，该项为当前项对应的前一项的索引

result：[1,3,4,6,7,9]
preIndexArr：[undefined,0,undefined,1,3,4,4,6,1]

比如 9： 在`原来数组`idx是7. 在result中，9前一项是7，7在`原来数组`的idx是6 .
通过
回溯构建出正确的result数组

vue3中diff的全过程