diff アルゴリズムは、ツリー ノードを同じレベルで比較する効率的なアルゴリズムであり、ツリーをレイヤーごとに検索して横断する必要がなくなります。それでは、diff アルゴリズムについてどれくらい知っていますか?次の記事では、vue2 の差分アルゴリズムについて詳しく説明していますので、お役に立てれば幸いです。
私は長い間 Vue 2 のソース コードを見てきました。フローの使用から TypeScript の使用に至るまで、ソース コードを開いて毎回見ていきます。毎回、beforeMount の段階である、VNode (Visual Dom Node、vdom を直接呼び出すこともできる) の生成方法についての data 初期化 部分だけを見ていました。コンポーネントを更新するときに VNode (diff) を比較する方法 () は慎重に研究されたことがありません。両端の差分アルゴリズム が使用されていることだけがわかります。この両端の開始と終了については、次のとおりです。見たことがなかったので、今回じっくり勉強するために記事を書いてみました。内容が間違っている場合は、ご指摘いただけると幸いです。ありがとうございます~
diff とは何ですか?
私の理解では、diff とは次のことを指します。 differences、つまり 古いコンテンツと新しいコンテンツの差分を計算する ; Vue の差分アルゴリズムは、 シンプルで効率的な # 方法を通じて古いコンテンツと新しいコンテンツを迅速に比較します。 ## メソッド VNode ノード配列 の違いは、最小限の dom 操作で ページ コンテンツ を更新することです。 [関連する推奨事項: vuejs ビデオ チュートリアル 、Web フロントエンド開発 ]ここには 2 つの必要な前提条件があります:
#比較は VNode 配列です
-
古い VNode 配列と新しい VNode 配列の 2 つのセットが同時に存在します
-
したがって、これは通常のみ発生します
data 更新時 ページ コンテンツを更新する必要がある場合、
renderWatcher.run()
を実行します。 なぜ VNode なのか?
上で述べたように、diff で比較されるのは実際の dom ノードではなく VNode です。なぜ VNode が使用されるのか? ほとんどの人は比較するのだと思います。それは明らかです。簡単に説明しましょう。~Vue で VNode を使用する理由は大まかに 2 つあります:
VNode はフレームワーク デザイナーとして設計されています。 JavaScript オブジェクト自体は実際の DOM ノードよりも単純なプロパティを備えており、操作中に DOM クエリを実行する必要がないため、計算中のパフォーマンス消費を大幅に最適化できます
- #VNode から実際の DOM へのリンク レンダリング プロセスは、さまざまなプラットフォーム (Web、WeChat アプレット) に応じて異なる方法で処理され、各プラットフォームに適応した実際の DOM 要素を生成できます
- diff 中にこのプロセスでは、古いノード データと新しいノード データが走査されますが、それに比べて、VNode を使用するとパフォーマンスが大幅に向上します。
プロセスのソート
Web ページでは、実際の dom ノードは
tree の形式で存在し、ルート ノードはすべて
、仮想ノードが実際の dom ノードと確実に一致するようにするために、VNode はツリー構造も使用します。
コンポーネントの更新時にすべての VNode ノードを比較する必要がある場合、古いノードと新しいノードの両方のセットを 徹底的に走査して比較する必要があり、これによりパフォーマンスに多大なオーバーヘッドが発生します。 ; したがって、Vue のデフォルトでは、同じレベルのノードの比較、つまり、
古い VNode ツリーと新しい VNode ツリーのレベルが異なる場合、追加のレベルのコンテンツが直接作成されます。または破棄された
の場合、差分操作のみが同じレベルで実行されます。 一般的に、diff 操作は v-for ループまたは v-if/v-else、
component
などで発生します。 ノード オブジェクトを動的に生成します (静的ノードは通常変更されず、比較は非常に高速です)。このプロセスは dom を更新するため、ソース コードではこのプロセスに対応するメソッド名は ## となります。 #updateChildren 、src/core/vdom/patch.ts にあります。以下に示すように: ここでは、Vue コンポーネント インスタンスの作成および更新プロセスのレビューを示します:
最初にすべての
beforeCreate
から created
ステージに進み、主にデータとステータス、およびいくつかの基本的なイベントとメソッドを処理します
-
その後、 $mount(vm .$options.el) メソッドは、Vnode
と dom の作成およびマウント段階、つまり beforeMount- と
mounted の間に入ります。 (コンポーネントが更新された場合はここと同様)
プロトタイプの $mount は platforms/web/runtime-with-compiler.ts に書き換えられ、元の実装は # にあります。 # #platforms/web/runtime/index.ts; 元の実装メソッドでは、実際に mountComponent メソッドを呼び出して render; を実行します。 ## 以下の runtime-with-compiler は、テンプレート文字列コンパイル モジュールを追加します。これは、解析後に options で template を実行します。コンパイルされ、関数 内の options.render
- mountComponent
にバインドされた関数に変換され、レンダリング メソッド updateComponent = が定義されます。 () => (vm._update(vm._render())、before 構成で watcher インスタンスをインスタンス化します (つまり renderWatcher)、 watch 観察オブジェクトを定義したばかりの updateComponent メソッドとして定義して、最初のコンポーネントのレンダリングを実行し、依存関係コレクション をトリガーします。ここで、before 構成のみbeforeMount/beforeUpdate フック関数をトリガーするメソッドを設定します。これが、beforeMount ステージと beforeUpdate ステージで実際の dom ノードを取得できない理由です。それは、古い dom ノードの
_update- メソッドが
mountComponent と同じファイルで定義されており、そのコアは を読み取ることです。コンポーネント インスタンスの $el (古い dom ノード) および _vnode (古い VNode) は、_render()# によって生成された vnode と比較されます。 ## 関数。patch 操作
patch 関数はまず - を比較して、古いノードがあるかどうかを確認します
。そうでない場合は、新しいものである必要があります。コンポーネントを作成して直接レンダリングします。古いノードがある場合は、patchVnode、を使用して古いノードと新しいノードを比較します。古いノードと新しいノードの場合は、新しいノードには一貫性があり、両方に children 子ノードがあります。次に、コア ロジック diff - updateChildren 子ノード比較 update を入力します。このメソッドも同様です。私たちがよく diff アルゴリズムと呼ぶもの
序文の内容
古いものと新しいものを比較しているため、 VNode 配列では、まず 比較 判定方法:
sameNode (a, b)
、ノードの追加方法 addVnodes、ノードの削除方法 もちろん、removeVnodes が VNode に一貫性があると sameNode が判断した後でも、patchVnode は単一の新しい VNode と古い VNode の内容を詳細に比較して、内部データを更新する必要があります。 sameNode(a, b)
このメソッドの目的は 1 つあります。古いノードと新しいノードが同じかどうかを比較する。
このメソッドでは、最初に比較するのは、a と b の key が同じかどうかです。これが、Vue が
v-for、v-if、Dynamic を記録する理由です。 v-else
などのノードは、ノードの一意性を識別するために key を設定する必要があります。key が存在し、同じである場合は、内部の変更が変更されたかどうかを比較するだけで済みます。通常の状況では、これにより多くの DOM 操作が削減されますが、これが設定されていない場合は、対応するノード要素が直接破棄され、再構築されます。
非同期コンポーネント: ラベルは同じ、両方ともコメント ノードではなく、両方ともデータを持ち、同じ型ですテキスト入力ボックスの
非同期コンポーネント: 古いノードのプレースホルダーと新しいノードのエラー プロンプトは両方とも
unknown-
関数の全体的なプロセスは次のとおりです。次のように
addVnodes
名前が示すように、新しい VNode ノードを追加します。 この関数は 6 つのパラメータを受け取ります:
parentElm
現在のノード配列の親要素、
refElm
指定された位置の要素、vnodes 新しい仮想ノード配列、startIdx 新しいノード配列の挿入された要素の開始位置、endIdx 新しいノード配列の挿入された要素の終了インデックス、 insertedVnodeQueue ノード キューを挿入する必要がある仮想ノード。 startIdx から
endIdx
位置 まで vnodes 配列を走査し、その後 # を呼び出します。 ##createElm vnodes[idx] に対応する要素を作成し、refElm の前に順番に挿入します。 vnodes[idx] には Component コンポーネントが存在する可能性があり、対応するコンポーネントを作成するために
createComponent
も呼び出されます。実例。 <blockquote><p>全体 <code>VNode と dom は両方とも ツリー構造 であるため、同じレベルで 比較した後、より深い VNode を処理する必要があります。現在のレベルと dom 処理 。
removeVnodes
addVnodes とは対照的に、このメソッドは VNode ノードを削除するために使用されます。
このメソッドは削除のみであるため、次の 3 つのパラメータのみが必要です: vnodes 古い仮想ノード配列、startIdx 開始インデックス、endIdx インデックスの終了。
内部関数は、startIdx から endIdx 位置 まで vnodes 配列を走査します ( の場合)。 vnodes[idx ] 未定義でない場合は、tag 属性に従って処理されます:
が存在し、それが存在することを示します。要素またはコンポーネントは、- vnodes[idx]
の内容を再帰的に処理し、remove フックと破棄フックをトリガーする必要があります は、プレーン テキスト ノード であることを示しており、dom-
からノードを直接削除できます。
実際の完全な比較と dom update によるノード比較の方法。
このメソッドでは、主に
nine のメイン パラメータ判定が含まれており、さまざまな処理ロジックに対応しています:
古い VNode と新しい VNode は一致しています, これは、変更がないことを意味します。 直接終了
新しい VNode に実際の dom バインディングがあり、更新する必要があるノード セットが配列の場合、現在の VNode をコピーします。 VNode はコレクションの指定された位置に移動します。
- 古いノードが
非同期コンポーネントであり、ロードが完了していない場合は、
を直接終了します。それ以外の場合は、渡します。 ハイドレート- この関数は、新しい VNode をレンダリング用の実際の dom に変換します。どちらの場合も、
は関数を終了します。
と key- が等しいか、
isOnce が指定されている場合にノードが更新されない場合、古いノードのコンポーネント インスタンスが直接更新されます。 reused および exit the function
属性があり、# で構成されている場合##prepatch フック関数、実行 - prepatch(oldVnode, vnode)
ノードに比較フェーズに入るように通知します。通常、このステップではパフォーマンスの最適化を構成します #新しい VNode に data 属性があり、ノードの子を再帰的に変更する場合 コンポーネント インスタンスの vnode がまだラベル付きで利用可能な場合、update
フック関数が で構成されますcbs- コールバック関数オブジェクトと
data で構成された updateHook 関数:
古いノードと新しいノードの両方がある場合は、- children
子ノード、updateChildren メソッドを入力します。子ノードを比較するには
#古いノードに子ノードがない場合は、VNode に対応する新しい子ノードを直接作成します - 新しいノードに子ノードがない場合は、古い VNode 子ノードを削除します
text Text
-
- If新しい VNode には
- text
テキストがあります (これはテキスト ノードです)。古いノードと新しいノードのテキスト コンテンツを比較して一貫性があるかどうかを確認します。そうでない場合は、テキスト コンテンツの更新を続行します。
最後に、新しいノードの
data に設定された - postpatch
フック関数を呼び出して、更新が完了したことをノードに通知します
#簡単に言えば、 patchVnode- は、
同じノード更新フェーズで新しいコンテンツと古いコンテンツを比較することです。変更があれば、対応するコンテンツが更新されます。子がある場合は、対応するコンテンツが更新されます。ノードを追加し、各子ノード の比較と更新を「再帰的に」実行します。 そして 子ノード配列の比較と更新は diff
の核となるロジックであり、面接でよく聞かれる質問の 1 つでもあります。
次に、
updateChildren メソッドの分析に入りましょう~##updateChildren
diff core 分析
まず考えてみましょう。
新しい配列に基づいて 2 つのオブジェクト配列の要素の違いを比較します。
メソッドは何ですか?
暴力的な手段を通じて 2 つの配列
を直接走査して、配列内の各要素の順序と差分を見つけることができます。これが 単純な diff アルゴリズム です。 つまり、
は、新しいノード配列を走査し、各サイクルで古いノード配列を再度走査して 2 つのノードが一貫しているかどうかを比較し、比較することによって新しいノードが追加されるか、削除されるか、移動されるかを決定します。結果
、プロセス全体で m*n 回の比較が必要なため、デフォルトの時間計算量はオンです。 この比較方法は、多数のノード更新中に非常にパフォーマンスを消費するため、Vue 2 はそれを最適化し、両端比較アルゴリズム (両端差分#) に変更しました。 ##。
両端差分アルゴリズム
名前が示すように、両端は 両端から開始して中央まで横断します。比較用のアルゴリズム。
double-ended diff には 5 つの比較状況 があります:
- 古いヘッダーと新しいヘッダーは等しい
- 古い尾と新しい尾は等しい
#古い頭は新しい尾と等しい-
#古い尾は新しい頭と等しい
-
4 つは互いに等しくありません
-
それらのうち、最初の 4 つは
理想的な状況
、5番目は最も複雑な比較状況です。 等しいかどうかを判断します。つまり、
sameVnode(a, b) は true
1. 新しいノード状態と古いノード状態をプリセットする
上記の 5 つの状況を同時に実証するために、次の新しいノード配列と古いノード配列をプリセットします。 :
初期ノード順序の古いノード配列として
oldChildren (1 から 7 までの合計 7 つのノードを含む) - #障害後の新しいノード配列として
newChildren、ノードも 7 つありますが、古いノードと比較すると、 vnode 3- が 1 つ減り、
vnode 8比較する前に、まず次のことを行う必要があります2 つのノード セットの両端インデックスを定義します :
let oldStartIdx = 0
let oldEndIdx = oldCh.length - 1
let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]
let newStartIdx = 0
let newEndIdx = newCh.length - 1
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]
ログイン後にコピー
コピーされたソース コード (oldCh
)図の oldChildren は、newCh は newChildren 次に、トラバーサル比較の stop 条件を定義します。操作
:
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx)
ログイン後にコピー
ここで停止 条件は 古いノード配列または新しいノード配列のどちらかの走査が終了するとすぐに、走査 が直ちに停止します。
この時のノードの状態は以下の通りです:
2. 比較する前にvnodeが存在することを確認してください 
新旧を保証するため、ノード配列は比較時に無効な比較を行わず、古いノード配列 の先頭部分と末尾部分が連続しており、値が であるデータ
をまず除外します。 ＃＃＃未定義＃＃＃。 if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx]
} else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]ログイン後にコピー
3. 古いヘッドは新しいヘッドと同等です
この時点では、古いノードと新しいノードの 2 つの
開始インデックスに相当します。指すノードは 基本的に一貫性がある である場合、この時点で
patchVnode
が呼び出され、2 つの vnode と 2 つの開始インデックスの詳細な比較と dom 更新が実行されます。 に移動されます。つまり: if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(
oldStartVnode,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}ログイン後にコピー
##4 に示すとおりです。古い末尾は次と等しくなります。新しいテール
はヘッドノードの等価性と似ています。この状況は、
古いノード配列と新しいノード配列の最後のノードが基本的に同じであることを意味します##。このとき、
patchVnode
は、2 つの末尾ノードの合計を比較するためにも呼び出されます。dom を更新し、 2 つの端のインデックスを前方に移動します。 if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(
oldEndVnode,
newEndVnode,
insertedVnodeQueue,
newCh,
newEndIdx
)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}ログイン後にコピー
このときのノードとインデックスの変更は図
これが意味するのは、
古いノード配列の現在の開始インデックスが指す vnode は、新しいノード配列の現在の終了インデックスが指す vnode と基本的に同じであるということです
. 
patchVnode
を呼び出して、2 つのノードで同じことを実行します。
ただし、上の 2 つとの違いは、この場合、 ノードが移動されるため、
patchVnode で終了し、その後 になることです。 古いヘッド ノード を
nodeOps.insertBefore
を介して現在の古いテール ノード の後の に再挿入します。 その後、 古いノードの開始インデックスが後方に移動し、新しいノードの終了インデックスが 前方に移動します。
があるためです。 vnode ノード. は、vnode に対応する実際の dom ノードを指すため、古いノード配列をここに移動することは、実際には
実際の dom ノード シーケンス を横に移動することになり、これが であることに注意してください。現在の末尾ノード (インデックスが変更されるとき) その後、これが古いノード配列の終わりであるとは限りません。
即：
if (sameVnode(oldStartVnode, newEndVnode)) {
patchVnode(
oldStartVnode,
newEndVnode,
insertedVnodeQueue,
newCh,
newEndIdx
)
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
}ログイン後にコピー
此时状态如下：
6. 旧尾等于新头
这里与上面的 旧头等于新尾 类似，一样要涉及到节点对比和移动，只是调整的索引不同。此时 旧节点的 末尾索引 前移、新节点的 起始索引 后移，当然了，这里的 dom 移动对应的 vnode 操作是 将旧节点数组的末尾索引对应的 vnode 插入到旧节点数组 起始索引对应的 vnode 之前。
if (sameVnode(oldEndVnode, newStartVnode)) {
patchVnode(
oldEndVnode,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
)
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}ログイン後にコピー
此时状态如下：
7. 四者均不相等
在以上情况都处理之后，就来到了四个节点互相都不相等的情况，这种情况也是 最复杂的情况。
当经过了上面几种处理之后，此时的 索引与对应的 vnode 状态如下：
可以看到四个索引对应的 vnode 分别是：vnode 3、vnode 5、 vnode 4、vnode 8，这几个肯定是不一样的。
此时也就意味着 双端对比结束。
后面的节点对比则是 将旧节点数组剩余的 vnode （oldStartIdx 到 oldEndIdx 之间的节点）进行一次遍历，生成由 vnode.key 作为键，idx 索引作为值的对象 oldKeyToIdx，然后 遍历新节点数组的剩余 vnode（newStartIdx 到 newEndIdx 之间的节点），根据新的节点的 key 在 oldKeyToIdx 进行查找。此时的每个新节点的查找结果只有两种情况：
注：这里 只有找到了旧节点并且新旧节点一样才会将旧节点数组中 idxInOld 中的元素置为 undefined。
最后，会将 新节点数组的 起始索引 向后移动。
if (isUndef(oldKeyToIdx)) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
}
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) {
// New element
createElm(
newStartVnode,
insertedVnodeQueue,
parentElm,
oldStartVnode.elm,
false,
newCh,
newStartIdx
)
} else {
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(
vnodeToMove,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
)
oldCh[idxInOld] = undefined
canMove &&
nodeOps.insertBefore(
parentElm,
vnodeToMove.elm,
oldStartVnode.elm
)
} else {
// same key but different element. treat as new element
createElm(
newStartVnode,
insertedVnodeQueue,
parentElm,
oldStartVnode.elm,
false,
newCh,
newStartIdx
)
}
}
newStartVnode = newCh[++newStartIdx]
}ログイン後にコピー
大致逻辑如下图：
剩余未比较元素处理
经过上面的处理之后，根据判断条件也不难看出，遍历结束之后 新旧节点数组都刚好没有剩余元素 是很难出现的，当且仅当遍历过程中每次新头尾节点总能和旧头尾节点中总能有两个新旧节点相同时才会发生，只要有一个节点发生改变或者顺序发生大幅调整，最后 都会有一个节点数组起始索引和末尾索引无法闭合。
那么此时就需要对剩余元素进行处理：
- 旧节点数组遍历结束、新节点数组仍有剩余，则遍历新节点数组剩余数据，分别创建节点并插入到旧末尾索引对应节点之前
- 新节点数组遍历结束、旧节点数组仍有剩余，则遍历旧节点数组剩余数据，分别从节点数组和 dom 树中移除
即：
小结
Vue 2 的 diff 算法相对于简单 diff 算法来说，通过 双端对比与生成索引 map 两种方式 减少了简单算法中的多次循环操作，新旧数组均只需要进行一次遍历即可将所有节点进行对比。
両端の比較では 4 つの比較と移動がそれぞれ実行され、パフォーマンスは最適な解決策ではないため、Vue 3 では Longest Increasing Subsequence メソッドを導入して、両端の比較を置き換えました。 . ですが、残りは引き続き空間拡張を使用して、インデックス マップに変換することで時間の複雑さを軽減し、それによってコンピューティング パフォーマンスをさらに向上させます。
もちろん、vnode に対応する elm の実際の dom ノードはこの記事の図には示されていません。両者のモバイルの関係は誤解を招く可能性があります。「Vue.js」と合わせて読むことをお勧めします。設計と実装」。
全体的なプロセスは次のとおりです:
(学習ビデオ共有: vuejs 入門チュートリアル , プログラミングの基本ビデオ )
以上がVue2 diffアルゴリズムがすぐわかる（画像と文章で詳しく解説）の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
