Vue の両端差分アルゴリズムの詳細については、こちらをご覧ください。-Vue.js-php.cn

diff アルゴリズムは、レンダラの最も複雑な部分です。この記事では、Vue の両端の差分アルゴリズムについて説明します。お役に立てば幸いです。

Vue の両端差分アルゴリズムの詳細については、こちらをご覧ください。

Vue と React はどちらも vdom に基づくフロントエンドフレームワークです。コンポーネントのレンダリングは vdom を返し、レンダラーは追加、削除、変更 API を通じて vdom を dom に同期します。。 (学習ビデオ共有: vuejs ビデオチュートリアル )

もう一度レンダリングすると、新しい vdom が生成されます。レンダラーは 2 つの vdom ツリーを比較し、異なる部分を追加、削除、および変更します。 . API が dom に更新されました。

2 つの vdom ツリーを比較して相違点を見つけるアルゴリズムは、diff アルゴリズムと呼ばれます。

diff アルゴリズムはレンダラーの最も複雑な部分であり、インタビューでもよく聞かれる質問です。今日は、Vue の差分アルゴリズムを通じて差分アルゴリズムを調べます。

diff アルゴリズム

各ノードは別のツリー内のすべてのノードと通信する必要があるため、2 つのツリーの差分計算の複雑さは O(n^3) であることがわかります。変更されたノードが見つかった場合、挿入、削除、変更の複雑さも n になります。これはすべてのノードに当てはまり、n 倍されるため、複雑さは O(n * n * n) になります。

Vue の両端差分アルゴリズムの詳細については、こちらをご覧ください。

このような複雑さはフロントエンドフレームワークでは受け入れられません。つまり、1 回のレンダリングで 1000 個のノード (1000 * 1000 * 1000、合計 10 億秒) を処理する必要があります。 -レート。

したがって、フロントエンドフレームワークの差分は、次の 2 つの処理原則に同意します。 同じレイヤーのみを比較し、タイプが変更されると、子ノードは比較されなくなります。

DOM ノードをレベルを越えて移動するケースは比較的少ないため、一般的には、同じレベルでの DOM の追加、削除、変更です。

この方法では、一度走査して型を比較するだけで済みます。複雑さは O(n) です。さらに、型が変更された場合、子ノードは比較されなくなるため、走査の手間が省けます。多数のノードの。さらに、関連する dom ノードが vdom に記録されるため、dom の追加、削除、変更 (O(1)) を実行する必要がなく、全体的な diff アルゴリズムの複雑さは O(n) です。

Vue の両端差分アルゴリズムの詳細については、こちらをご覧ください。

一度に 1000 個のノードがレンダリングされ、最大 1000 回比較されますが、この複雑さは許容範囲内です。

しかし、このようなアルゴリズムはそれほど複雑ではありませんが、依然として問題があります。

たとえば、ノードのグループが 5 つあるとすると、タイプは ABCDE で、次のレンダリングは EABCD になります。このとき、1 つずつ比較して、タイプが異なることを確認し、 5 つのノードが再レンダリングされます。

また、異なるタイプの原則に従って、子ノードは比較されなくなり、これらのノードに子ノードがある場合は、それらのノードも再レンダリングされます。

dom の操作は比較的遅いため、diff のアルゴリズムの複雑さは低いものの、再レンダリングのパフォーマンスは高くありません。

したがって、diff アルゴリズムでは、それ自身の時間計算量を考慮することに加えて、dom 操作の数という要素も考慮する必要があります。

上記の例では、ABCDE が EABCD になりますが、当然ながら E を移動するだけで、新しい要素を作成する必要はありません。

しかし、同じノードが移動したことを比較して確認するにはどうすればよいでしょうか?

タイプを決定しますか?同じタイプのノードが多数存在し、それらを区別できない可能性があります。

各ノードに一意の識別子を付けることが最善です。

したがって、ノードのグループをレンダリングするときに、フロントエンドフレームワークは開発者にキーを指定するように要求し、そのキーを使用して一部のノードが移動されたばかりかどうかを判断し、ノードを直接再利用できるようにします。

このように、diff アルゴリズムがノードのグループの比較を処理する場合、キーに基づいてアルゴリズムを再度最適化する必要があります。

キーに基づいた 2 つのノードグループの差分アルゴリズムを マルチノード diff アルゴリズム と呼びます。これは、vdom 全体の差分アルゴリズムの一部です。

次に、マルチノード diff アルゴリズムを学習しましょう:

単純な diff

ノードのセット ABCD がレンダリングされ、DCAB がレンダリングされると仮定します。これはどうやって対処すればいいのでしょうか？

マルチノード差分アルゴリズムの目的は、ノードを可能な限り再利用し、ノードの移動によって作成を置き換えることです。

したがって、新しい vnode 配列の各ノードについて、古い vnode 配列に対応するキーがあるかどうかを確認する必要があります。ある場合は、それを新しい位置に移動します。ない場合は、新しいものを作成します。

以上です:

const oldChildren = n1.children
const newChildren = n2.children

let lastIndex = 0
// 遍历新的 children
for (let i = 0; i < newChildren.length; i++) {
    const newVNode = newChildren[i]
    let j = 0
    let find = false
    // 遍历旧的 children
    for (j; j < oldChildren.length; j++) {
      const oldVNode = oldChildren[j]
      // 如果找到了具有相同 key 值的两个节点，则调用 patch 函数更新
      if (newVNode.key === oldVNode.key) {
        find = true
        patch(oldVNode, newVNode, container)
        
        处理移动...
        
        break //跳出循环，处理下一个节点
      }
   }
   // 没有找到就是新增了
   if (!find) {
      const prevVNode = newChildren[i - 1]
      let anchor = null
      if (prevVNode) {
        anchor = prevVNode.el.nextSibling
      } else {
        anchor = container.firstChild
      }
      patch(null, newVNode, container, anchor)
   }
}

ログイン後にコピー

ここでのパッチ機能は、ノードのプロパティを更新し、イベントリスナーをリセットすることです。対応する古いノードがない場合は、そのノードが挿入され、その後のノードをアンカーアンカーとして渡す必要があります。

新しい vnode を走査して処理します:

まず、古い vnode 配列から対応するノードを見つけます。見つかった場合は、再利用できることを意味します。次に、それを移動するだけです。

見つからない場合は、それを挿入すると、アンカーポイントは前のノードの次の兄弟になります。

Vue の両端差分アルゴリズムの詳細については、こちらをご覧ください。

那如果找到了可复用的节点之后，那移动到哪里呢？

其实新的 vnode 数组中记录的顺序就是目标的顺序。所以把对应的节点按照新 vnode 数组的顺序来移动就好了。

const prevVNode = newChildren[i - 1]
if (prevVNode) {
    const anchor = prevVNode.el.nextSibling
    insert(newVNode.el, container, anchor)
}

ログイン後にコピー

要插入到 i 的位置，那就要取 i-1 位置的节点的 nextSibling 做为锚点来插入当前节点。

Vue の両端差分アルゴリズムの詳細については、こちらをご覧ください。

但是并不是所有的节点都需要移动，比如处理到第二个新的 vnode，发现它在旧的 vnode 数组中的下标为 4，说明本来就是在后面了，那就不需要移动了。反之，如果是 vnode 查找到的对应的旧的 vnode 在当前 index 之前才需要移动。

也就是这样：

let j = 0
let find = false
// 遍历旧的 children
for (j; j < oldChildren.length; j++) {
    const oldVNode = oldChildren[j]
    // 如果找到了具有相同 key 值的两个节点，则调用 patch 函数更新之
    if (newVNode.key === oldVNode.key) {
        find = true
        patch(oldVNode, newVNode, container)

        if (j < lastIndex) { // 旧的 vnode 数组的下标在上一个 index 之前，需要移动
          const prevVNode = newChildren[i - 1]
          if (prevVNode) {
            const anchor = prevVNode.el.nextSibling
            insert(newVNode.el, container, anchor)
          }
        } else {// 不需要移动
          // 更新 lastIndex
          lastIndex = j
        }
        break
    }
}

ログイン後にコピー

查找新的 vnode 在旧的 vnode 数组中的下标，如果找到了的话，说明对应的 dom 就是可以复用的，先 patch 一下，然后移动。

移动的话判断下下标是否在 lastIndex 之后，如果本来就在后面，那就不用移动，更新下 lastIndex 就行。

如果下标在 lastIndex 之前，说明需要移动，移动到的位置前面分析过了，就是就是新 vnode 数组 i-1 的后面。

这样，我们就完成了 dom 节点的复用和移动。

新的 vnode 数组全部处理完后，旧的 vnode 数组可能还剩下一些不再需要的，那就删除它们：

// 遍历旧的节点
for (let i = 0; i < oldChildren.length; i++) {
    const oldVNode = oldChildren[i]
    // 拿着旧 VNode 去新 children 中寻找相同的节点
    const has = newChildren.find(
      vnode => vnode.key === oldVNode.key
    )
    if (!has) {
      // 如果没有找到相同的节点，则移除
      unmount(oldVNode)
    }
}

ログイン後にコピー

这样，我们就完成了两组 vnode 的 diff 和对应 dom 的增删改。

小结一下：

diff 算法的目的是根据 key 复用 dom 节点，通过移动节点而不是创建新节点来减少 dom 操作。

对于每个新的 vnode，在旧的 vnode 中根据 key 查找一下，如果没查找到，那就新增 dom 节点，如果查找到了，那就可以复用。

复用的话要不要移动要判断下下标，如果下标在 lastIndex 之后，就不需要移动，因为本来就在后面，反之就需要移动。

最后，把旧的 vnode 中在新 vnode 中没有的节点从 dom 树中删除。

这就是一个完整的 diff 算法的实现。

Vue の両端差分アルゴリズムの詳細については、こちらをご覧ください。

这个 diff 算法我们是从一端逐个处理的，叫做简单 diff 算法。

简单 diff 算法其实性能不是最好的，比如旧的 vnode 数组是 ABCD，新的 vnode 数组是 DABC，按照简单 diff 算法，A、B、C 都需要移动。

那怎么优化这个算法呢？

从一个方向顺序处理会有这个问题，那从两个方向同时对比呢？

这就是双端 diff 算法：

双端 diff

简单 diff 算法能够实现 dom 节点的复用，但有的时候会做一些没必要的移动。双端 diff 算法解决了这个问题，它是从两端进行对比。

我们需要 4 个指针，分别指向新旧两个 vnode 数组的头尾：

Vue の両端差分アルゴリズムの詳細については、こちらをご覧ください。

头和尾的指针向中间移动，直到 oldStartIdx <= oldEndIdx 并且 newStartIdx <= newEndIdx，说明就处理完了全部的节点。

每次对比下两个头指针指向的节点、两个尾指针指向的节点，头和尾指向的节点，是不是 key是一样的，也就是可复用的。

如果是可复用的话就直接用，调用 patch 更新一下，如果是头尾这种，还要移动下位置。

也就是这样的：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) { // 头头
    patch(oldStartVNode, newStartVNode, container)
    oldStartVNode = oldChildren[++oldStartIdx]
    newStartVNode = newChildren[++newStartIdx]
  } else if (oldEndVNode.key === newEndVNode.key) {//尾尾
    patch(oldEndVNode, newEndVNode, container)
    oldEndVNode = oldChildren[--oldEndIdx]
    newEndVNode = newChildren[--newEndIdx]
  } else if (oldStartVNode.key === newEndVNode.key) {//头尾，需要移动
    patch(oldStartVNode, newEndVNode, container)
    insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)

    oldStartVNode = oldChildren[++oldStartIdx]
    newEndVNode = newChildren[--newEndIdx]
  } else if (oldEndVNode.key === newStartVNode.key) {//尾头，需要移动
    patch(oldEndVNode, newStartVNode, container)
    insert(oldEndVNode.el, container, oldStartVNode.el)

    oldEndVNode = oldChildren[--oldEndIdx]
    newStartVNode = newChildren[++newStartIdx]
  } else {
    
    // 头尾没有找到可复用的节点
  }
}

ログイン後にコピー

头头和尾尾的对比比较简单，头尾和尾头的对比还要移动下节点。

比如旧 vnode 的头节点是新的 vnode 的尾节点，那就要把它移动到旧的 vnode 的尾节点的位置。

也就是：

insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling)

ログイン後にコピー

插入节点的锚点节点是 oldEndVNode 对应的 dom 节点的 nextSibling。

如果旧 vnode 的尾节点是新 vnode 的头结点，那就要把它移动到旧 vnode 的头结点的位置。

也就是：

insert(oldEndVNode.el, container, oldStartVNode.el)

ログイン後にコピー

插入节点的锚点节点是 oldStartVNode 对应的 dom 节点（因为要插在它之前）。

从双端进行对比，能尽可能的减少节点移动的次数。

当然，还要处理下如果双端都没有可复用节点的情况：

如果双端都没有可复用节点，那就在旧节点数组中找，找到了就把它移动过来，并且原位置置为 undefined。没找到的话就插入一个新的节点。

也就是这样：

const idxInOld = oldChildren.findIndex(
  node => node.key === newStartVNode.key
)
if (idxInOld > 0) {
  const vnodeToMove = oldChildren[idxInOld]
  patch(vnodeToMove, newStartVNode, container)
  insert(vnodeToMove.el, container, oldStartVNode.el)
  oldChildren[idxInOld] = undefined
} else {
  patch(null, newStartVNode, container, oldStartVNode.el)
}

ログイン後にコピー

因为有了一些 undefined 的节点，所以要加上空节点的处理逻辑：

if (!oldStartVNode) {
    oldStartVNode = oldChildren[++oldStartIdx]
} else if (!oldEndVNode) {
    oldEndVNode = newChildren[--oldEndIdx]
}

ログイン後にコピー

这样就完成了节点的复用和移动的逻辑。

那确实没有可复用的节点的那些节点呢？

经过前面的移动之后，剩下的节点都被移动到了中间，如果新 vnode 有剩余，那就批量的新增，如果旧 vnode 有剩余那就批量的删除。

因为前面一个循环的判断条件是 oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx，这样如果 old vnode 多了，最后 newStartIdx 会小于 newEndIdx。如果 new vnode 多了，最后 oldStartIdx 会小于 oldEndIdx。

所以判断条件是这样的：

if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
  // 添加新节点
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    patch(null, newChildren[i], container, oldStartVNode.el)
  }
} else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
  // 移除操作
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    unmount(oldChildren[i])
  }
}

ログイン後にコピー

这样就是一个完整的 diff 算法了，包括查找可复用节点和移动节点、新增和删除节点。

而且因为从两侧查找节点，会比简单 diff 算法性能更好一些。

比如 ABCD 到 DABC，简单 diff 算法需要移动 ABC 三个节点，而双端 diff 算法只需要移动 D 一个节点。

小结一下：

双端 diff 是头尾指针向中间移动的同时，对比头头、尾尾、头尾、尾头是否可以复用，如果可以的话就移动对应的 dom 节点。

如果头尾没找到可复用节点就遍历 vnode 数组来查找，然后移动对应下标的节点到头部。

最后还剩下旧的 vnode 就批量删除，剩下新的 vnode 就批量新增。

Vue の両端差分アルゴリズムの詳細については、こちらをご覧ください。