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