ホームページ > 記事 > ウェブフロントエンド > Vue2 の Diff アルゴリズムの詳細な分析

Vue2 の Diff アルゴリズムの詳細な分析

青灯夜游転載: 2023-02-28 19:40:501797ブラウズ

diff アルゴリズムは、ツリーノードを同じレベルで比較する効率的なアルゴリズムであり、ツリーをレイヤーごとに検索して横断する必要がなくなります。では、diff アルゴリズムについてどれくらい知っていますか?次の記事では、vue2 の差分アルゴリズムについて詳しく説明していますので、お役に立てれば幸いです。

以前、ライブインタビューを見ていてDiffアルゴリズムについてよく質問したのと、著者自身もVue2をよく使っているので、Vue2のDiffアルゴリズムについて勉強するつもりです。実はずっと勉強したいと思っていて、Diffアルゴリズムは割と奥が深い気がして後回しにしていたのですが、最近面接の準備をしていたので、勉強しておこうと思いました。遅かれ早かれ学習してください。この機会に Diff アルゴリズムを理解してみてはいかがでしょうか。著者は 1 日かけて学習しました。少し調べてみましたが、Diff アルゴリズムの本質を十分に理解していない可能性があります。ご容赦ください。

? これは実際には著者の研究メモとしてカウントされており、著者のレベルは限られています。改訂された記事は著者の個人的な意見を表すものにすぎません。間違いがある場合は、コメントで指摘してください。同時に、この記事は非常に長いので、辛抱強く読んでください。これを読んだ後、Diff アルゴリズムについてより深く理解できるようになると著者は信じています。この記事は、現在 Diff アルゴリズムを説明しているインターネット上のほとんどの記事よりも優れていると思います。なぜなら、この記事は、答えから直接始めるのではなく、問題から始めて、答えを読むのと同じように、問題から始めてすべての人に考え方を教えるからです。この記事では、Diff アルゴリズムの微妙さを誰もが感じられるように段階的に説明しますが、同時に、誰もが Diff アルゴリズムをより直感的に体験できるようにするための小さな実験も実施しました。

Diff アルゴリズムを使用する理由

仮想 DOM

Vue2 の最下層は仮想 DOM を使用して表現するためです。ページの構造的な仮想 DOM は実際にはオブジェクトです。生成方法を知りたい場合の一般的なプロセスは次のとおりです:

最初にテンプレート文字列 (.vue##) を解析します。 # file
次に、レンダー関数を生成します。
最後に、レンダー関数を呼び出して仮想 DOM を生成します [関連する推奨事項:
vuejs ビデオチュートリアル、Web フロントエンド開発]

最小限の更新

実際、フレームワークは仮想のみを使用します。パフォーマンスのための DOM (js は DOM を生成して表示するため) ページは多くのパフォーマンスを消費します。更新されるたびにページ全体が再生成されると、エクスペリエンスは確実に良くありません。そのため、2 つの変更点を見つける必要があります。ページを開き、変更された箇所を js で更新するだけです

(おそらく追加、削除、更新のいずれか) 必要なのは 1 回のクリックだけであり、最小限の更新です。では、最小限の更新量を達成するにはどうすればよいでしょうか?次に、Diff アルゴリズムを使用する必要がありますが、Diff アルゴリズムは正確に何を比較するのでしょうか?おそらくこれが、Diff アルゴリズムを初めて学習するときに誤解しやすいところです。実際には、古い仮想 DOM と新しい仮想 DOM を比較します。つまり、Diff アルゴリズムは、違いを見つけ、次の違いを見つけることです。 2つの仮想DOMを分割し、その差分をページ上に反映させることで最小の更新量を実現し、変更箇所のみを更新すればパフォーマンスは確実に向上します。

ページ更新プロセス

実は、これを説明するのはさらに難しいのですが、著者が大まかに紹介します。Vue を学習したことがある人なら、その特徴の 1 つが次のとおりであることを知っています。このフレームワークの特徴はデータレスポンスです。レスポンシブスタイルとは何ですか。つまり、データが更新されるとページも更新されます。では、ページはどのようにして更新の必要性を認識するのでしょうか?実際、これはこのフレームワークの賢い部分で、一般的なプロセスは次のとおりです:

Object.defineProperty の get を入力すると、依存関係がここで収集されます。では、依存関係を収集するのは誰でしょうか?それは各コンポーネントです。各コンポーネントはウォッチャーであり、このコンポーネント内のすべての変数 (つまり、依存関係) を記録します。もちろん、各依存関係 (Dep) も収集しますコンポーネントのウォッチャー;
Object.defineProperty の set がトリガーされます。この関数では、データは全員に通知されますウォッチャーがページを更新すると、各ページが更新メソッドを呼び出しますこのメソッドは patch;
最終的に変更量を見つけたら、ページを更新できます。

実際には、更新しながら更新します。誰でも理解しやすいように、これら 2 つのパートは分離されています

Diff アルゴリズムの簡単な紹介

インタビューで Diff アルゴリズムとは何かと尋ねられると、誰もが間違いなく、头头のようないくつかの単語を言うでしょう。、tail tail、tail head、head Tail、深さ優先走査 (dfs)、同じ層の比較 これらの言葉に似ていますが、1 つまたは 2 つ言えます。文章、それは単なる味です。実際、筆者も CSDN で公開されている Diff アルゴリズムに関する記事を読んだのですが、これは非常に読まれている記事ですが、よく理解できなかったと感じています。おそらく、自分自身が理解していなかったのか、理解していても説明していなかったのではないでしょうか。そうすれば、著者は自分の洞察をあなたと共有しましょう。

Diff アルゴリズムの前提

誰もが明確に理解できるように、関数呼び出しプロセスを次に示します:

patch
patchVnode
updateChildren

Diff アルゴリズム前提条件 これは非常に重要です。前提とは何なのかと疑問に思われるかもしれません。先ほどの比較だけではないでしょうか？それは正しいですが、間違っています。なぜなら、Diff アルゴリズムは、前述の head、tail、tail、head、tail に達するからです。このステップの前提条件は、2 回比較されたノードは 同じ##です。 # 、ここでの類似性は誰もが考えているような完全に同じではありませんが、特定の条件を満たしていれば同じです。説明を簡単にするために、この記事では key と のみを含む 1 つのタグのみを考慮します。タグ名 (タグ) の場合、先ほど言った キーは同じでタグも同じ ということですが、作者の発言がある程度正しいことを証明するために、ソースコードは次のようになります。ここにも掲載されています:

// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts
// 36行
function sameVnode(a, b) {
  return (
    a.key === b.key &&
    a.asyncFactory === b.asyncFactory &&
    ((a.tag === b.tag &&
      a.isComment === b.isComment &&
      isDef(a.data) === isDef(b.data) &&
      sameInputType(a, b)) ||
      (isTrue(a.isAsyncPlaceholder) && isUndef(b.asyncFactory.error)))
  )
}

混乱を恐れる場合は、以下を省略しても構いません。全体的な理解には影響しません。以下は、あらゆる状況を考慮して追加された単なる判断です: したがって、2 つの仮想 DOM が同じでない場合は比較を続ける必要はなく、同じである場合は比較する必要はありません。ここでの類似性は実際にはまったく同じです。つまり、DOM のアドレスです。 2 つの仮想 DOM は同じなので、ソースコードも貼り付けます:

function patchVnode(......) {
  if (oldVnode === vnode) {
    return
  }
  ......
}

ここまでは皆さん混乱しているかもしれませんが、ここで要約しましょう:

パッチで比較される内容 関数は、新旧の仮想 DOM が key が同じでタグが同じであるかどうかを示します。 異なる場合は直接置き換えてください。同じ場合は ## を使用してください。 #patchVnode

である場合にのみ Diff アルゴリズムが考慮されるということです。同じ

。一貫性がない場合は、元の DOM を削除して、新しい DOM に置き換えます。

patchVnode関数

この関数の中身が実際のDiffアルゴリズムとなるので、ソースコードをもとに紹介していきます。

ソースコードのコアコードは、

patch.ts
の 638 行目から 655 行目です。
実際、現在導入されている patchVnode はソースコードに直接導入されていますが、なぜこのように分類されているのかわからないかもしれません。そのため、作成者はその理由を理解していただくためにここにいます。まず結論ですが、

は

属性と children 属性は同時に存在できません。これには、全員がテンプレートのソースコード部分を解析する必要があります

text

と children## があるかどうかです。 # この場合、次の 9 つの状況が存在します。

Situation古いノードのテキスト古いノードの子新しいノードのテキスト新しいノードの子1❎❎❎❎2❎✅❎❎ ✅#❎4❎❎❎✅5❎ ❎ ❎✅ #❎8❎✅✅❎9✅ ❎✅❎

##3

❎ ##❎

##✅

✅ 6 ✅ ❎

✅ 7 ❎ ❎

按照上面的表格，因为如果新节点有文本节点，其实老节点不管是什么都会被替换掉，那么就可以按照 新节点 text 是否存在来分类，其实 Vue 源码也是这么来分类的：

if (isUndef(vnode.text)) {
  // 新虚拟 DOM 有子节点
} else if (oldVnode.text !== vnode.text) {
  // 如果新虚拟 DOM 是文本节点，直接用 textContent 替换掉
  nodeOps.setTextContent(elm, vnode.text)
}

那么如果有子节点的话，那应该怎么分类呢？我们可以按照每种情况需要做什么来进行分类，比如说：

第一种情况，我们啥都不用做，因此也可以不用考虑
第二种情况，我们应该把原来 DOM 的 textContent 设置为 ''
第三种情况，我们也应该把原来 DOM 的 textContent 设置为 ''
第四种情况，我们应该加入新的子节点
第五种情况，这个情况比较复杂，需要对比新老子节点的不同
第六种情况，我们应该把原来的 textContent 设置为 '' 后再加入新的子节点

那么通过以上六种情况 (新虚拟 DOM 不含有 text，也就是不是文本节点的情况)，我们可以很容易地进行归类：

分类 1️⃣： 第二种情况 和 第三种情况。进行的是操作是：把原来 DOM 的 textContent 设置为 ''
分类 2️⃣： 第四种情况 和 第六种情况。进行的是操作是：如果老虚拟 DOM 有 text，就置空，然后加入新的子节点
分类 3️⃣：第五种情况。进行的是操作是：需要进行精细比较，即对比新老子节点的不同

其实源码也是这么来进行分类的，而且之前说的 同层比较 也就得出来了，因为每次比较都是比较的同一个父节点每一个子元素 (这里的子元素包括文本节点和子节点) 是否相同，而 深度优先遍历(dfs) 是因为每次比较中，如果该节点有子节点 (这里的子节点指的是有 children 属性，而不包括文本节点) 的话需要进行递归遍历，知道最后到文本节点结束。

⭕️ 这里需要搞清楚子节点和子元素的区别和联系

然后我们来看看源码是怎么写吧，只看新虚拟 DOM 不含有 text，也就是不是文本节点的情况：

if (isUndef(vnode.text)) {
  if (isDef(oldCh) && isDef(ch)) {
    if (oldCh !== ch)
      // 递归处理，精细比较
      // 对应分类 3️⃣
      updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
  } else if (isDef(ch)) {
    if (__DEV__) {
      checkDuplicateKeys(ch) // 可以忽略不看
    }
    // 对应分类 2️⃣
    if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, &#39;&#39;)
    addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
  } else if (isDef(oldCh)) {
  	// 对应分类 1️⃣
    removeVnodes(oldCh, 0, oldCh.length - 1)
  } else if (isDef(oldVnode.text)) {
  	// 对应分类 1️⃣
    nodeOps.setTextContent(elm, &#39;&#39;)
  }
}

❓我们可以看到源码把分类 1️⃣ 拆开来了，这是因为如果老虚拟 DOM 有子节，那么可能绑定了一些函数，需要进行解绑等一系列操作，作者也没自信看，大致瞄了一眼，但是如果我们要求不高，如果只是想自己手动实现 Diff 算法，那么没有拆开的必要。

作者觉得这么讲可能比网上其他介绍 Diff 算法的要好，其他的可能直接给你说源码是怎么写的，可能没有说明白为啥这么写，但是通过之前这么分析讲解后可能你对为什么这么写会有更深的理解和帮助吧。

updateChildren 函数

同层比较

因为当都含有子节点，即都包含 children 属性后，需要精细比较不同，不能像之前那些情况一样进行简单处理就可以了那么这个函数中就会介绍大家经常说的 头头、尾尾、尾头、头尾 比较了，其实这不是 Vue 提出来的，是很早就提出来的算法，就一直沿用至今，大家可以参考【snabbdom 库】

? 在这之前我们要定义四个指针 newStartIdx、newEndIdx、oldStartIdx 和 oldEndIdx，分别指向 新头节点、新尾节点、旧头节点 与 旧尾节点

循环条件如下：

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  ......
}

其实这个比较也就是按人类的习惯来进行比较的，比较顺序如下：

1️⃣ 新头节点与旧头节点：++newStartIdx 和 ++oldStartIdx
2️⃣ 新尾节点与旧尾节点：--newEndIdx 和 --oldEndIdx
3️⃣ 新尾节点与旧头节点：需要将 旧头节点 移动到 旧尾节点之前，为什么要这么做，讲起来比较复杂，记住就好，然后 --newEndIdx 和 ++oldStartIdx
4️⃣ 新头节点与旧尾节点：需要将 旧尾节点 移动到 旧头节点之前，为什么要这么做，讲起来比较复杂，记住就好，然后 ++newStartIdx 和 --oldEndIdx
5️⃣ 如果都没有匹配的话，就把 新头节点 在旧节点列表 (也就是 children 属性的值) 中进行查找，查找方式按照如下：
- 如果有 key 就把 key 在 oldKeyToIdx 进行匹配，oldKeyToIdx 根据旧节点列表中元素的 key 生成对应的下标
- 如果没有，就按顺序遍历旧节点列表找到该节点所在的下标
- 如果在旧节点列表是否找到也分为两种情况：
  - 找到了，那么只要将 新头节点 添加到 旧头节点 之前即可
  - 没找到，那么需要创建新的元素然后添加到 旧头节点 之前
  - 然后把这个节点设置为 undefined

根据循环条件我们可以得到两种剩余情况，如下：

6️⃣ 如果 oldStartIdx > oldEndIdx 说明老节点先遍历完成，那么新节点比老节点多，就要把 newStartIdx 与 newEndIdx 之间的元素添加
7️⃣ 如果 newStartIdx > newEndIdx 说明新节点先遍历完成，那么老节点比新节点多，就要把 oldStartIdx 与 oldEndIdx 之间的元素删除

其实我们上面还没有考虑如果节点为 undefined 的情况，因为在上面也提到过，如果四种都不匹配后会将该节点置为 undefined，也只有旧节点列表中才有，因此要在开头考虑这两种情况：

8️⃣ 当 oldStartVnode 为 undefined：++oldStartIdx
9️⃣ 当 oldEndVnode 为 undefined：--oldEndIdx

那么我们来看源码怎么写的吧，其中用到的函数可以查看源码附录：

// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts
// 439 行至 556 行
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (isUndef(oldStartVnode)) {
  	// 情况 8️⃣
    oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
  } else if (isUndef(oldEndVnode)) {
  	// 情况 9️⃣
    oldEndVnode = oldCh[--oldEndIdx]
  } else if (sameVnode(oldStartVnode, newStartVnode)) {
  	// 情况 1️⃣
    patchVnode(...)
    oldStartVnode = oldCh[++oldStartIdx]
    newStartVnode = newCh[++newStartIdx]
  } else if (sameVnode(oldEndVnode, newEndVnode)) {
  	// 情况 2️⃣
    patchVnode(...)
    oldEndVnode = oldCh[--oldEndIdx]
    newEndVnode = newCh[--newEndIdx]
  } else if (sameVnode(oldStartVnode, newEndVnode)) {
    // Vnode moved right
    // 情况 3️⃣
    patchVnode(...)
    canMove &&
      nodeOps.insertBefore(
        parentElm,
        oldStartVnode.elm,
        nodeOps.nextSibling(oldEndVnode.elm)
      )
    oldStartVnode = oldCh[++oldStartIdx]
    newEndVnode = newCh[--newEndIdx]
  } else if (sameVnode(oldEndVnode, newStartVnode)) {
    // Vnode moved left
    // 情况 4️⃣
    patchVnode(...)
    canMove &&
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
    oldEndVnode = oldCh[--oldEndIdx]
    newStartVnode = newCh[++newStartIdx]
  } else {
  	// 情况 5️⃣
    if (isUndef(oldKeyToIdx)) // 创建 key -> index 的 Map
      oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) 
    // 找到 新头节点 的下标
    idxInOld = isDef(newStartVnode.key)
      ? oldKeyToIdx[newStartVnode.key]
      : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
    if (isUndef(idxInOld)) {
      // New element
      // 如果没找到
      createElm(...)
    } else {
      // 如果找到了
      vnodeToMove = oldCh[idxInOld]
      if (sameVnode(vnodeToMove, newStartVnode)) {
        patchVnode(...)
        oldCh[idxInOld] = undefined
        canMove &&
          nodeOps.insertBefore(
            parentElm,
            vnodeToMove.elm,
            oldStartVnode.elm
          )
      } else {
        // same key but different element. treat as new element
        createElm(...)
      }
    }
    newStartVnode = newCh[++newStartIdx]
  }
}
if (oldStartIdx > oldEndIdx) {
  // 情况 6️⃣
  refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
  addVnodes(...)
} else if (newStartIdx > newEndIdx) {
  // 情况 7️⃣
  removeVnodes(...)
}

如果问为什么这么比较，回答就是经过很多人很多年的讨论得出的，其实只要记住过程就行了，如果想要更深了解 Diff 算法，可以去 B 站看【尚硅谷】Vue源码解析之虚拟DOM和diff算法

v-for 中为什么要加 key

这个问题面试很常见，但是可能大部分人也就只会背八股，没有完全理解，那么经过以上的介绍，我们可以得到自己的理解：

首先，如果不加 key 的话，那么就不会去 Map 里匹配 (O(1))，而是循环遍历整个列表 (O(n))，肯定加 key 要快一点，性能更高
其次，如果不加 key 那么在插入或删除的时候就会出现，原本不是同一个节点的元素被认为是相同节点，上面也有说过是 sameVnode 函数判断的，因此可能会有额外 DOM 操作

为什么说可能有额外 DOM 操作呢？这个和插入的地方有关，之后会讨论，同理删除也一样

证明 key 的性能

我们分为三个实验：没有 key、key 为 index、key 唯一，仅证明加了 key 可以进行最小化更新操作。

实验代码

有小伙伴评论说可以把代码贴上这样更好，那么作者就把代码附上 ?：

<!DOCTYPE html>
<html>

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
  <script src="https://cdn.jsdelivr.net/npm/vue@2/dist/vue.js"></script>
  <style>
    .box {
      display: flex;
      flex-direction: row;
    }
    .item {
      flex: 1;
    }
  </style>
</head>

<body>
  <div id="app">
    <div>
      <div>
        <h3>没有 key</h3>
        <p v-for="(item, index) in list">{{ item }}</p>
      </div>
      <div>
        <h3>key 为 index</h3>
        <p v-for="(item, index) in list" :key="index">{{ item }}</p>
      </div>
      <div>
        <h3>key 唯一</h3>
        <p v-for="(item, index) in list" :key="item">{{ item }}</p>
      </div>
    </div>
    <button @click="click1">push(4)</button>
    <button @click="click2">splice(1, 0, 666)</button>
    <button @click="click3">unshift(999)</button>
    <br /><br />
    <button @click="click4">pop()</button>
    <button @click="click5">splice(1, 1)</button>
    <button @click="click6">shift()</button>
  </div>
  <script>
    var app = new Vue({
      el: &#39;#app&#39;,
      data: {
        show: false,
        list: [1, 2, 3],
      },
      methods: {
        click1() {
          this.list.push(4);
        },
        click2() {
          this.list.splice(1, 0, 666);
        },
        click3() {
          this.list.unshift(999);
        },
        click4() {
          this.list.pop();
        },
        click5() {
          this.list.splice(1, 1);
        },
        click6() {
          this.list.shift();
        }
      },
    })
  </script>
</body>

</html>

增加实验

实验如下所示，我们首先更改原文字，然后点击按钮**「观察节点发生变化的个数」**：

在队尾增加

Vue2 の Diff アルゴリズムの詳細な分析

在队内增加

Vue2 の Diff アルゴリズムの詳細な分析

在队首增加

Vue2 の Diff アルゴリズムの詳細な分析

删除实验

在队尾删除

Vue2 の Diff アルゴリズムの詳細な分析

在队内删除

Vue2 の Diff アルゴリズムの詳細な分析

在队首删除

Vue2 の Diff アルゴリズムの詳細な分析

实验结论

增加实验

表格为每次实验中，每种情况的最小更新量，假设列表原来的长度为 n

实验	没有 key	key 为 index	key 唯一
在队尾增加	1	1	1
在队中增加	n - i + 1	n - i + 1	1
在队首增加	n + 1	n + 1	1

删除实验

表格为每次实验中，每种情况的最小更新量，假设列表原来的长度为 n

实验	没有 key	key 为 index	key 唯一
在队尾删除	1	1	1
在队中删除	n - i	n - i	1
在队首删除	n	n	1

通过以上实验和表格可以得到加上 key 的性能和最小量更新的个数是最小的，虽然在 在队尾增加 和 在队尾删除 的最小更新量相同，但是之前也说了，如果没有 key 是要循环整个列表查找的，时间复杂度是 O(n)，而加了 key 的查找时间复杂度为 O(1)，因此总体来说加了 key 的性能要更好。

写在最后

本文从源码和实验的角度介绍了 Diff 算法，相信大家对 Diff 算法有了更深的了解了，如果有问题可私信交流或者评论区交流，如果大家喜欢的话可以点赞 ➕ 收藏 ?

源码函数附录

列举一些源码中出现的简单函数

setTextContent

function setTextContent(node: Node, text: string) {
  node.textContent = text
}

isUndef

function isUndef(v: any): v is undefined | null {
  return v === undefined || v === null
}

isDef

function isDef<T>(v: T): v is NonNullable<T> {
  return v !== undefined && v !== null
}

insertBefore

function insertBefore(
  parentNode: Node,
  newNode: Node,
  referenceNode: Node
) {
  parentNode.insertBefore(newNode, referenceNode)
}

nextSibling

function nextSibling(node: Node) {
  return node.nextSibling
}

createKeyToOldIdx

function createKeyToOldIdx(children, beginIdx, endIdx) {
  let i, key
  const map = {}
  for (i = beginIdx; i <= endIdx; ++i) {
    key = children[i].key
    if (isDef(key)) map[key] = i
  }
  return map
}

（学习视频分享：vuejs入门教程、编程基础视频）

以上がVue2 の Diff アルゴリズムの詳細な分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明：

この記事はjuejin.cnで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。

前の記事：Vue を使用した小さなプログラム開発の技術原則について話しましょう次の記事：Vue を使用した小さなプログラム開発の技術原則について話しましょう

続きを見る