vue3源码分析——手写diff算法

通过上面可以发现,
如果在中间对比的时候不写key,将会再来一次for循环,那就比较费性能了!!!

中间对比,节点都存在,需要移动节点

通过上面代码的执行，最终 i = 2, e1 =4， e2 = 4， 在上面的图中,会发现新老节点中只有E的节点移动了,其他的节点都不动,那么怎么找出 [C,D,E]和[E,C,D]中的最长连续的节点呢?

遇到这个,肯定需要使用 最长递增子序列的算法啦,通过这个可以得出最长节点的连续范围.

但是最长递增子序列中需要一个数组,这个数组需要记录老节点与新节点的位置关系

\

通过上图,可以看到,先定义一个数组,长度是对比之后的长度,然后默认
赋值为0,然后遍历老节点,用老节点的i来表示数组的结果,newIndex表示数据的下标,这样就能展示出新老节点的映射关系了

接下来实现一下这部分的功能,由于这一部分的内容与整体有关,我把整个diff的逻辑都放出来,全部已经写好注释了
functiоn patchKeyChildren(n1, n2, container, parentComponent, anchor) {    // 采用双端对比法    const l2 = n2.length    const l1 = n1.length    let i = 0;    let e1 = l1 – 1;    let e2 = l2 – 1;    const isSameVNode = (vnode1, vnode2) => {      return vnode1.type === vnode2.type && vnode1.key === vnode2.key    }    // 获取左侧的位置    while (i <= e1 && i <= e2) {      if (isSameVNode(n1, n2)) {        // 对比对应的子节点        patch(n1, n2, container, parentComponent, anchor)      } else {        break;      }      i++    }    // 获取右侧是位置    while (i <= e1 && i <= e2) {      if (isSameVNode(n1[e1], n2[e2])) {        patch(n1[e1], n2[e2], container, parentComponent, anchor)      } else {        break;      }      e1–;      e2–;    }    // 新的比老的短，删除老的    if (i >= e2 && i <= e1) {      while (i <= e1) {        hostRemove(n1.el)        i++      }    }    // 新的比老的长，挂载新的    else if (i > e1 && i <= e2) {      // 往左侧添加       //    a b   i = 0 e1 = -1 e2 = 0      // d c a b  需要找到a的位置      const nextPos = e2 + 1;      const anchor = nextPos < l2 ? n2[nextPos].el : null      while (i <= e2) {        patch(null, n2, container, parentComponent, anchor)        i++      }    }    else {      // 中间对比      const s1 = i;      const s2 = i;      // a b c d   i = 2 e1 = 2 e2 = 1      // a b d      // 条件  删除c      // 判断旧节点是否在新节点里面，在的话保留，不在则删除      const newIndexToOldIndexMap = new Map()      // 增加一个优化点,如果旧节点的数量和新节点的数量已经一致，那么其余旧节点直接删除      const toBePatched = e2 – s1 + 1;      let patched = 0;      // 将老节点和新节点做映射 b c d –> c d b      const oldIndexToNewIndexMap = new Array(toBePatched).fill(0)      // 判断是否需要移动节点，不需要移动则不需要调用获取最长递增子序列      let moved = false;      let maxIndexSoFar = 0;      // 把新节点的key装入map      for (let j = s2; j <= e2; j++) {        newIndexToOldIndexMap.set(n2[j].key, j)      }      for (let i = s1; i <= e1; i++) {        // 新节点已经满足前面对比的老节点，需要删除其余的老节点        if (patched >= toBePatched) {          hostRemove(n1.el)          continue;        }        let newIndex;        if (n1.key !== null) {          newIndex = newIndexToOldIndexMap.get(n1.key)        } else {          // key 不存在，需要遍历新节点，看能不能找到这个节点          for (let j = s2; j <= e2; j++) {            if (isSameVNode(n1, n2[j])) {              newIndex = j              break;            }          }        }        if (newIndex === undefined) {          // 删除节点          hostRemove(n1.el)        } else {          // 更新映射关系          oldIndexToNewIndexMap[newIndex – s1] = i + 1          // 判断是否需要移动节点          if (newIndex > maxIndexSoFar) {            maxIndexSoFar = newIndex;          } else {            moved = true          }          // 存在的话，进行下一次的patch          patch(n1, n2[newIndex], container, parentComponent, anchor)          patched++        }      }      // 获取最长递增序列  获取的是最长递增子序列的索引下标数组      const longestIncreasingSubsequence = moved ? getLongestIncreasingSubsequence(oldIndexToNewIndexMap) : []      // 遍历，判断当前的下标是否存在于最长递增序列中，存在则不需要移动，不存在需要移动      // 使用游标j      let j = longestIncreasingSubsequence.length – 1;      for (let i = toBePatched – 1; i >= 0; i–) {        // 计算下一个节点        const curIndex = i + s2;        const anchor = curIndex + 1 < l2 ? n2[curIndex + 1].el : null;        if (oldIndexToNewIndexMap === 0) {          // 新增节点          patch(null, n2[i + s2], container, parentComponent, anchor)        }        else if (moved) {          if (j < 0 || i !== longestIncreasingSubsequence[j]) {            // 移动节点            hostInsert(n2[curIndex].el, container, anchor)          } else {            // 命中目标节点，不需要移动            j–;          }        }      }    }  }中间节点新增