DIFFアルゴリズムがわからない場合は、私に連絡してください（画像付き）

序文

インタビュアー: 「仮想 DOM と Diff アルゴリズムをご存知ですか? 説明してください。」

私：「えーと、...ガチョウ、それ」、終わりです😰、私のIQは突然低下し、言葉をうまく整理できず、うまく答えられないか、まったく答えられません。

そこで今回は、今後このような状況に遭遇したときに、明確な理解が得られ、落ち着いて安心できるように、関連する知識のポイントをまとめます。

仮想DOM

仮想DOMとは

一言で言えば、仮想DOMは実際のDOMを記述するために使用されるJavaScriptオブジェクトです。これだけでは十分ではないかもしれませんので、例を見てみましょう。実際のDOMと仮想DOMをそれぞれ記述するコードを使用する

実際のDOM:

 < ul  クラス= "リスト" >    
 < li > < / li >    
 < li > b </ li >    
 < li > c </ li >    
 </ ul >  

対応する仮想DOM:

 vnode = h ( 'ul.list', [  
  h('li','a')、  
  h('li','b')、  
  h('li','c')、  
 ])  
コンソール.log(vnode)

コンソールに出力される Vnode:

h 関数によって生成された仮想 DOM の JS オブジェクト (Vnode) のソース コード:

エクスポートインターフェースVNodeData {  
    小道具?: 小道具 
    属性?: 属性 
    クラス?: クラス 
    スタイル: VNodeStyle  
    データセット?: データセット 
    オン？: オン 
    ヒーロー？：ヒーロー 
    添付データ?: 添付データ 
    フック?: フック 
    キー?: キー
     ns?: 文字列 // SVGの場合
    fn?: () = > VNode // サンク用 
    args?: any[] // サンクの場合 
    [key: string]: any // その他のサードパーティモジュールの場合 
 }  
エクスポートタイプキー=文字列| 数値 
定数インターフェースVNode = {  
    sel: 文字列 | undefined, // セレクター 
    データ: VNodeData | undefined, // VNodeData は VNodeData 上で定義されています 
    children: 配列< VNode | string > | undefined, // 子ノード、テキストと相互排他的 
    text: string | undefined, // ラベルの中央のテキストコンテンツ
    elm: Node | undefined, // 変換された実際のDOM  
    key: キー | undefined // 文字列または数値
  }

補充:

上記の h 関数はおなじみかもしれませんが、しばらくは思い出せないかもしれません。問題ありません。思い出すお手伝いをします。開発、レンダリング関数のレンダリングにおける一般的な実際のシナリオ:

 //ケース1 Vueプロジェクトのmain.jsでVueインスタンスを作成する 
新しいVue({  
  ルーター、  
  店、  
  レンダリング: h = > h(App)  
 }).$mount("#app");  
 //ケース2: render を使用してリストにレンダリングする 
列: [  
    {  
        タイトル: 「作戦」  
        キー: "アクション"、  
        幅: 150,  
        レンダリング: (h, パラメータ) = > {  
            h('div', [ を返す 
                h('ボタン', {  
                    小道具: {  
                        サイズ: 「小」  
                    },  
                    スタイル: {  
                        右余白: '5px'、  
                        マージン下: '5px',  
                    },  
                    の上： {  
                        クリック: () = > {  
                            行のUUIDを編集します。  
                        }  
                    }  
                }、 '編集'）  
            ]);  
        }  
    }  
 ]

仮想 DOM を使用する理由は何ですか?

• MVVMフレームワークはビューと状態の同期の問題を解決します
• テンプレートエンジンはビュー操作を簡素化できますが、ステータスを追跡する方法はありません。
• 仮想DOMは状態の変化を追跡します
• github の virtual-dom の動機の説明を参照してください (https://github.com/Matt-Esch/virtual-dom)
  • 仮想DOMはプログラムの状態を維持し、最後の状態を追跡することができます
  • 2つの状態の違いを比較して実際のDOMを更新する
• クロスプラットフォーム使用
  • ブラウザ プラットフォームの DOM レンダリング
  • サーバーサイドレンダリングSSR（Nuxt.js/Next.js）、フロントエンドはvue指向、後者はreact指向
  • ネイティブアプリケーション (Weex/React Native)
  • ミニアプリ（mpvue/uni-app）など
• 実際の DOM には多くの属性があり、DOM ノードの作成には非常にコストがかかります。
• 仮想 DOM は通常の JavaScript オブジェクトであり、記述するプロパティを多く必要とせず、作成にかかるオーバーヘッドもほとんどありません。
• 複雑なビュー状況でのレンダリング パフォーマンスを向上します (DOM の操作はパフォーマンスを大量に消費するため、DOM の操作範囲を狭めるとパフォーマンスが向上します)

真剣に考えてみる質問です。仮想 DOM を使用すると、実際の DOM を直接レンダリングするよりも確実に高速になりますか? 答えはもちろん「いいえ」です。私の話を聞いてください。

例: ノードがDOMA->DOMBに変更された場合

上記の状況では、例 1 では DOMB を作成し、DOMA を置き換えます。例 2 では、仮想 DOM+DIFF アルゴリズムを作成して比較し、DOMB と DOMA が同じノードではないことがわかったので、最終的に DOMB を作成し、DOMA を置き換えます。例 1 の方が高速であることは明らかであり、同じ結果を得るために、例 2 でも仮想 DOM+DIFF アルゴリズムを作成して比較します。したがって、仮想 DOM を使用すると、実際の DOM を直接操作するよりも高速になるはずだと言うのは誤りであり、厳密ではありません。

たとえば、DOM ツリー内の子ノードのコンテンツが変更された場合:

複数の子ノードを持つ親ノードなど、複雑なノードがある場合、子ノードのコンテンツのみが変更された場合は、例 1 のように DOM ツリーを再レンダリングする必要はありません。このとき、仮想 DOM + Diff アルゴリズムは適切に反映されます。例 2 の仮想 DOM + Diff アルゴリズムを使用して、変更された子ノードを見つけ、そのコンテンツを更新できます。

概要: 仮想 DOM + Diff アルゴリズムにより、DOM ツリーが変更される場所を正確に見つけることができるため、複雑なビュー状況でのレンダリング パフォーマンスが向上し、DOM 操作 (再配置と再描画) が削減されます。

仮想DOMライブラリ

• スナブドム (https://github.com/snabbdom/snabbdom)
  • Vue.js2.xで使用される仮想DOMは、修正されたSnabbdomです。
  • 約 200 SLOC (コード 1 行)
  • モジュールによる拡張可能
  • ソースコードはTypeScriptを使用して開発されています
  • 最も高速な仮想DOMの1つ
• 仮想DOM

差分アルゴリズム

上記の記事を読んだ後、誰もが Diff アルゴリズムについて予備的な理解を得たと思います。はい、Diff アルゴリズムは実際には 2 つの違いを見つけるためのものです。

diff アルゴリズムについて最初に理解すべきことは、Diff のオブジェクトは仮想 DOM であり、実際の DOM の更新は Diff アルゴリズムの結果であるということです。

次に、snabbdom ソースコードのコア部分を抜粋して、Diff を皆さんに公開します。しばらくお待ちください。Web ページを閉じないでください。

スナブドムの核心

• init() はモジュールをセットアップします。patch() 関数を作成します
• h() 関数を使用して、実際のDOMを記述するJavaScriptオブジェクト（Vnode）を作成します。
• patch() は古いVnodeと新しいVnodeを比較します
• 変更されたコンテンツを実際のDOMツリーに更新する

初期化関数

モジュールは init 関数で設定され、次に patch() 関数が作成されます。まずはシナリオ ケースを使用して直感的に理解してみましょう。

 'snabbdom/build/package/init.js' から {init} をインポートします。  
 'snabbdom/build/package/h.js' から {h} をインポートします。  
 // 1. モジュールをインポートする 
 「snabbdom/build/package/modules/style」から {styleModule} をインポートします。  
 「snabbdom/build/package/modules/eventListeners」から {eventListenersModule} をインポートします。  
 // 2. 登録モジュール 
定数パッチ= init ([  
  スタイルモジュール、  
  イベントリスナーモジュール 
 ])  
 // 3. h() 関数の2番目のパラメータを使用して、モジュールで使用されるデータ（オブジェクト）を渡します。  
 vnode = h ('div', [  
  h('h1', {style: {backgroundColor: 'red'}}, 'こんにちは世界'),  
  h('p', {on: {click: eventHandler}}, 'こんにちは P')  
 ])  
関数イベントハンドラ() {  
  警告('痛いです、触らないで')  
 }  
 const app =ドキュメント.querySelector('#app')  
パッチ(アプリ、vnode)

init がインポートされたモジュールを使用する場合、これらのモジュールが提供する API を使用して、h 関数で仮想 DOM (Vnode) オブジェクトを作成できます。上記では、スタイル モジュールとイベント モジュールを使用して、作成された仮想 DOM にスタイル属性とイベント属性を付与し、最後に 2 つの仮想 DOM を patch 関数 (最初にアプリを仮想 DOM に変換) で比較してビューを更新します。

init のソースコードを簡単に見てみましょう。

 // src/package/init.ts  
 /* 最初のパラメータは各モジュール 
   2 番目のパラメータは DOMAPI で、DOM を他のプラットフォームの API に変換できます。  
つまり、クロスプラットフォームでの使用をサポートします。渡されない場合、デフォルトはhtmlDOMApiです。以下を参照してください。  
   initは高階関数であり、関数は別の関数を返し、モジュールをキャッシュでき、domApiは2つのパラメータを持ちます。  
今後は、oldValue と newValue (vnode) を渡すだけです*/  
エクスポート関数 init (モジュール: 配列<部分<モジュール>> 、 domApi?: DOMAPI) {
 ...  
関数 patch (oldVnode: VNode | Element, vnode: VNode): VNode {} を返します。  
 }

h関数

一部の場所では、createElement という名前も使用されていますが、これらは同じもので、どちらも仮想 DOM を作成します。上記の記事では、h 関数について皆さんが予備的に理解し、使用シナリオを関連付けていると思いますので、シナリオの例を紹介せず、ソースコードの部分に直接進みます。

 // h関数 
エクスポート関数 h (sel: 文字列): VNode  
エクスポート関数 h (sel: 文字列、データ: VNodeData | null): VNode  
エクスポート関数 h (sel: 文字列、子: VNodeChildren): VNode  
エクスポート関数 h (sel: 文字列、データ: VNodeData | null、子: VNodeChildren): VNode  
エクスポート関数 h (sel: any, b?: any, c?: any): VNode {  
  var データ: VNodeData = {}  
  var 子: 任意 
  varテキスト: 任意 
  var i: 数値 
    ...  
  return vnode(sel, data, children, text, undefined) //最後にvnode関数を返します 
 };

 // vnode関数 
エクスポート関数vnode (sel: 文字列 | 未定義、  
  データ: 任意 | 未定義、  
  子: 配列< VNode | 文字列> | 未定義、  
  テキスト: 文字列 | 未定義、  
  elm:Element|Text|undefined):VNode {  
  const key = data === undefined ? undefined : data.key
  return { sel, data, children, text, elm, key } //最後にVnodeオブジェクトを生成する 
 }

要約: h関数は最初にvnode関数を生成し、次にvnode関数はVnodeオブジェクト（仮想DOMオブジェクト）を生成します。

補充:

h 関数のソース コードには関数オーバーロードの概念が含まれており、簡単に説明します。

• パラメータの数や型が異なる関数 ()
• JavaScriptにはオーバーロードの概念はありません
• TypeScriptにはオーバーロードがありますが、オーバーロードの実装は依然としてコードを通じてパラメータを調整することです。

オーバーロードの概念は、戻り値ではなく、パラメータに関連しています。

• 例 1 (関数のオーバーロード - パラメータの数)

関数 add(a:数値,b:数値){  
コンソールログ(a+b)  
 }  
関数 add(a:数値,b:数値,c:数値){  
コンソールログ(a+b+c)  
 }  
追加(1,2)  
追加(1,2,3)

• 例 2 (関数のオーバーロード - パラメータの型)

関数 add(a:数値,b:数値){  
コンソールログ(a+b)  
 }  
関数 add(a:数値,b:文字列){  
コンソールログ(a+b)  
 }  
追加(1,2)  
追加(1,'2')  
パッチ機能（コア）

これまでの伏線を読んでいると、これを見ると気が散ってしまうかもしれません。目を覚ましてください、ここが核心です、高台に向かいましょう、兄弟。

• パッチ(古いVノード、新しいVノード)
• 新しいノードの変更されたコンテンツを実際のDOMにレンダリングし、最後に新しいノードを次の処理のための古いノードとして返します（コア）
• 新しい VNode と古い VNode を比較して、同じノードであるかどうかを確認します (ノードのキーと sel は同じです)
• 同じノードでない場合は、以前のコンテンツを削除して再レンダリングします。
• 同じノードの場合は、新しい VNode にテキストがあるかどうかを判断します。テキストがあり、古い Vnode のテキストと異なる場合は、テキストの内容を直接更新します (patchVnode)
• 新しい VNode に子ノードがある場合は、子ノードが変更されたかどうかを判断します (updateChildren、実装が最も面倒で難しい)

ソースコード:

関数 patch(oldVnode: VNode | Element, vnode: VNode): VNode { を返します。  
    let i: 数値、elm: ノード、親: ノード 
    const 挿入VnodeQueue: VNodeQueue = []  
    // cbs.pre はすべてのモジュールのプレフック関数セットです 
    ( i = 0 ; i <   cbs.pre.length ; ++i) cbs.pre[i]()  
    // isVnode関数はoldVnodeが仮想DOMオブジェクトであるかどうかを判定します 
    if (!isVnode(oldVnode)) {  
        // そうでない場合は、要素を仮想DOMオブジェクトに変換します 
古いVnode =空のノードAt (古いVnode)  
    }  
    // sameVnode 関数は、2 つの仮想 DOM が同じかどうかを判断するために使用されます。ソース コードについては補足 1 を参照してください。  
    同じVnode(古いVnode、vnode)の場合 
        // 同じ場合は、patchVnode を実行して 2 つのノードを比較します。patchVnode の詳細については後で説明します (core)  
        パッチVnode(古いVnode、vnode、挿入されたVnodeQueue)  
    } それ以外 {  
 elm = oldVnode .elm! // ! は ts での記述方法です。コード oldVnode.elm には値が必要です。  
        // parentNodeは親要素を取得します
親= api.parentNode (elm) をノードとして 
        // createElm は DOM 要素を作成し、それを vnode (新しい仮想 DOM) に挿入するために使用されます 
        createElm(vnode、挿入されたVnodeQueue)  
        親が null の場合 
            //DOM要素を親要素に挿入し、古いDOMを削除します 
            api.insertBefore(parent, vnode.elm!, api.nextSibling(elm)) // 新しく作成された要素を古いDOMの後ろに配置します 
            削除Vnodes(親、[古いVnode]、0、0)  
        }  
    }  
    ( i = 0 ; i <  挿入されたVnodeQueue.長さ;++i) {  
        挿入されたVnodeQueue[i].data!.hook!.insert!(挿入されたVnodeQueue[i])  
    }  
    ( i = 0 ; i <   cbs.post.length ; ++i) cbs.post[i]()  
    vnodeを返す 
 }

補足1: sameVnode関数

function sameVnode(vnode1: VNode, vnode2: VNode): boolean {keyセレクタとselセレクタを使用して、同じノードであるかどうかを判断します 
    vnode1.key === vnode2.key && vnode1.sel === vnode2.selを返します。  
 }

パッチVノード

• 最初のステージでは、プレパッチ機能と更新機能がトリガーされます (両方ともプレパッチ機能をトリガーし、更新機能は 2 つがまったく同じでない場合にのみトリガーされます)
• 2番目の段階では、新しいvnodeと古いvnodeの違いが実際に比較されます。
• 第3段階では、ポストパッチ機能がトリガーされ、ノードが更新されます。

ソースコード:

関数 patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {  
    constフック= vnode.data?.hook  
    フック?.prepatch?.(oldVnode, vnode)  
    const elm = vnode .elm = oldVnode .elm!  
    const oldCh = oldVnode.childrenを VNode[] として 
    const ch = vnode.childrenを VNode[] として 
    if ( oldVnode === vnode ) 戻り値 
    (vnode.data !== 未定義)の場合{ 
         （ i = 0とすると、i <   cbs.update.length ; ++i) cbs.update[i](oldVnode, vnode)  
        vnode.data.hook?.update?.(oldVnode, vnode)  
    }  
    if (isUndef(vnode.text)) { // 新しいノードのテキスト属性は未定義です 
        if (isDef(oldCh) && isDef(ch)) { // 新しいノードと古いノードの両方に子ノードがある場合 
            if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue) //そして子ノードが異なる場合は、後で説明する updateChildren 関数を実行します (core)  
        } else if (isDef(ch)) { // 新しいノードだけが子ノードを持つ 
            // 古いノードにテキスト属性がある場合、実際のDOMのテキスト属性に''が割り当てられます 
            if (isDef(oldVnode.text)) api.setTextContent(elm, '')  
            // そして、新しいノードのすべての子ノードを実際のDOMに挿入します 
            addVnodes(elm, null, ch, 0, ch.length - 1, 挿入されたVnodeQueue)  
        } else if (isDef(oldCh)) { // 実際のDOMのすべての子ノードをクリアする 
            Vnodesを削除します(elm, oldCh, 0, oldCh.length - 1)  
        } else if (isDef(oldVnode.text)) { // 実際のDOMのテキスト属性に''を割り当てます 
            api.setTextContent(elm, '')  
        } 
 
    } else if (oldVnode.text !== vnode.text) { //古いノードのテキストが新しいノードのテキストと異なる場合 
        if (isDef(oldCh)) { // 古いノードに子ノードがある場合は、すべての子ノードを削除します 
            Vnodesを削除します(elm, oldCh, 0, oldCh.length - 1)  
        }  
        api.setTextContent(elm, vnode.text!) // 新しいノードのテキストを実際のDOMに割り当てます 
    }  
    hook?.postpatch?.(oldVnode, vnode) // ビューを更新 
 }

少しわかりにくいかもしれないので、別のマインドマップを示します。

話題外: diff アルゴリズムの紹介

従来のdiffアルゴリズム

• 仮想DOMにおける差分アルゴリズム
• 従来のアルゴリズムは、2つのツリーの各ノード間の差を見つけます
• n1 (dom1のノード数) * n2 (dom2のノード数) を実行して比較し、違いを見つけて更新します。

snabbdom の diff アルゴリズムの最適化

• Snbbdom は、DOM の特性に基づいて従来の diff アルゴリズムを最適化します。
• DOM操作ではノード間のクロスレベル操作はほとんど行われない
• 同じレベルのノードのみを比較する

次に、Diff アルゴリズムの核心かつ難しい点でもある、子ノードの類似点と相違点を比較する updateChildren 関数の仕組みを紹介します。

updateChildren (コア内のコア: 子ノードの差を判定)

• この関数を 3 つの部分に分けます。パート 1: 変数の宣言、パート 2: 同じレベルのノードの比較、パート 3: ループの最後で作業を終了する (下の図を参照)。

• 同じレベルのノードの比較の 5 つのケース:

1. oldStartVnode/newStartVnode（古い開始ノード/新しい開始ノード）は同じです
2. oldEndVnode/newEndVnode（古いエンドノード/新しいエンドノード）は同じです
3. oldStartVnode/newEndVnode（古い開始ノード/新しい終了ノード）は同じです
4. oldEndVnode/newStartVnode（古い終了ノード/新しい開始ノード）は同じです
5. 特別なケース: 1、2、3、4 が条件を満たさない場合、実行されます。oldVnodes で newStartVnode と同じノードを探し、oldStartVnode に移動します。見つからない場合は、oldStartVnode にノードを作成します。

• 実行プロセスはループです。各ループでは、上記の 5 つの状況のいずれかが実行されると、ループは終了します。
• ループの最後で作業を終了します: oldStartIdx>oldEndIdx || newStartIdx>newEndIdx まで (古いノードまたは新しいノードが走査されたことを示します)

より直感的に理解するために、同じレベルのノードを比較する 5 つのケースの実装の詳細を見てみましょう。

新しい開始ノードと古い開始ノード（ケース1）

• ケース 1 が満たされた場合: (新旧ノードの開始ノードから開始し、oldCh[oldStartIdx] と newCh[newStartIdx] は、sameVnode (キーと sel が同じ) を実行して、同じノードであるかどうかを判断します)
• 次に、patchVnodeを実行して2つの違いを見つけ、グラフを更新します。違いがない場合は何もせずにサイクルを終了します。
• 古いスタートIdx++/新しいスタートIdx++

新しいエンドノードと古いエンドノード（ケース2）

• ケース 1 が一致しない場合は、ケース 2 を判断します。一致する場合: (古いノードと新しいノードの終了ノードから比較を開始し、oldCh[oldEndIdx] と newCh[newEndIdx] を比較し、sameVnode (key と sel が同じ) を実行して、同じノードであるかどうかを判断します)
• patchVnodeを実行して2つの違いを見つけ、ビューを更新します。違いがない場合は何もせずにループを終了します。
• 古い終了 ID --/新しい終了 ID --

古い開始ノード/新しい終了ノード (ケース 3)

• ケース 1 とケース 2 のどちらも満たされない場合は、ケース 3 が試行されます: (古いノードの開始ノードが新しいノードの終了ノードと比較され、oldCh[oldStartIdx] が newCh[newEndIdx] と比較され、sameVnode (キーと sel が同じ) が実行されて、同じノードであるかどうかが判断されます)
• patchVnodeを実行して2つの違いを見つけ、ビューを更新し、違いがない場合は何もせずにサイクルを終了します。
• oldCh[oldStartIdx]に対応する実DOMがoldCh[oldEndIdx]に対応する実DOMにシフトされた後
• 古い開始Idx++/新しい終了Idx--;

古い終了ノード/新しい開始ノード (ケース 4)

• ケース 1、2、3 のいずれにも該当しない場合は、ケース 4 が試行されます: (古いノードの終了ノードを新しいノードの開始ノードと比較し、oldCh[oldEndIdx] を newCh[newStartIdx] と比較し、sameVnode (キーと sel が同じ) を実行して、同じノードであるかどうかを判断します)
• patchVnodeを実行して2つの違いを見つけ、ビューを更新し、違いがない場合は何もせずにサイクルを終了します。
• oldCh[oldEndIdx]に対応する実際のDOMは、oldCh[oldStartIdx]に対応する実際のDOMの先頭にシフトされます。
• 古い終了Idx--/新しい開始Idx++;

新しい開始ノード/古いノード配列内のノードの検索 (ケース 5)

• 古いノードから検索します。newCh[newStartIdx]と同一のノードが見つかった場合（対応ノード[1]と呼びます）、patchVnodeを実行して2つのノードの差分を探し、ビューを更新します。差分がない場合は何もせずにループを終了します。
• 対応するノード[1]に対応する実DOMは、oldCh[oldStartIdx]に対応する実DOMの先頭に移動される。

• 同じノードが見つからない場合は、newCh[newStartIdx]ノードに対応する実際のDOMを作成し、oldCh[oldStartIdx]に対応する実際のDOMの前に挿入します。
• 新しい開始Idx++

次に、ループを終了する最後の作業を紹介します (oldStartIdx>oldEndIdx || newStartIdx>newEndIdx):

• 新しいノードのすべての子ノードが最初に走査され（newStartIdx>newEndIdx）、ループが終了します。
• 同じノードに対応しない子ノードが削除されると、新しいノードのすべての子ノードのトラバーサルは終了します。

• 古いノードのすべての子ノードが最初に走査され（oldStartIdx>oldEndIdx）、ループが終了します。
• 古いノードのすべての子ノードのトラバーサルは、追加の子ノードが古いノードの終了ノードの前に挿入されたときに終了します。(ソースコード: newCh[newEndIdx + 1].elm) これは、対応する古い終了ノードの実際の DOM です。newEndIdx+1 は、同じノードに一致するときに -1 が必要なため、終了ノードとして追加し直す必要があるためです。

最後に、ソースコードを添付します。

関数 updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue) {  
    let oldStartIdx = 0 ; // 古いノードの開始ノードインデックス 
    let newStartIdx = 0 ; // 新しいノードの開始ノードインデックス 
    let oldEndIdx = oldCh .length - 1; // 古いノードの終了ノードのインデックス 
    let oldStartVnode = oldCh [0]; // 古いノードの開始ノード 
    let oldEndVnode = oldCh [oldEndIdx]; // 古いノードの終了ノード 
    let newEndIdx = newCh .length - 1; // 新しいノードの終了ノードのインデックス 
    let newStartVnode = newCh [0]; // 新しいノードの開始ノード 
    let newEndVnode = newCh [newEndIdx]; // 新しいノード終了ノード 
    let oldKeyToIdx; // ノード移動関連 
    let idxInOld; // ノード移動関連 
    let elmToMove; // ノード移動関連 
    前にさせてください。  
    // 同じレベルのノードを比較する 
    (古い開始Idx < = 古い終了Idx && 新しい開始Idx < = 新しい終了Idx) {  
        （古い開始Vノード== null）の場合{  
 oldStartVnode = oldCh [++oldStartIdx]; // Vnodeが左に移動された可能性があります 
        }  
        そうでない場合 ( oldEndVnode == null) {  
 oldEndVnode = oldCh [--oldEndIdx];  
        }  
        そうでない場合（ newStartVnode == null）{  
新しいStartVnode =新しいCh [++新しいStartIdx];  
        }  
        そうでない場合 ( newEndVnode == null) {  
新しいEndVnode =新しいCh [--newEndIdx];  
        }  
        else if (sameVnode(oldStartVnode, newStartVnode)) { // 判定ケース1  
            パッチVnode(古い開始Vnode、新しい開始Vnode、挿入されたVnodeQueue);  
古い開始Vノード=古いCh [++古い開始Idx];  
新しいStartVnode =新しいCh [++新しいStartIdx];  
        }  
        else if (sameVnode(oldEndVnode, newEndVnode)) { // ケース2  
            パッチVnode(古いEndVnode、新しいEndVnode、挿入されたVnodeQueue);  
 oldEndVnode = oldCh [--oldEndIdx];  
新しいEndVnode =新しいCh [--newEndIdx];  
        }  
        else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnodeが右に移動 case 3  
            パッチVnode(古い開始Vnode、新しい終了Vnode、挿入されたVnodeQueue);  
            api.insertBefore(parentElm、oldStartVnode.elm、api.nextSibling(oldEndVnode.elm));  
古い開始Vノード=古いCh [++古い開始Idx];  
新しいEndVnode =新しいCh [--newEndIdx];  
        }  
        else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnodeが左に移動 ケース4  
            パッチVnode(古い終了Vnode、新しい開始Vnode、挿入されたVnodeQueue);  
            api.insertBefore(親Elm、古い終了Vnode.elm、古い開始Vnode.elm);  
 oldEndVnode = oldCh [--oldEndIdx];  
新しいStartVnode =新しいCh [++新しいStartIdx];  
        }  
        else { // ケース5  
            if ( oldKeyToIdx === 未定義 ) {  
古いキーからIdxを作成 
            }  
 idxInOld = oldKeyToIdx [newStartVnode.key];  
            if (isUndef(idxInOld)) { // 新しい要素 // 古いノードの新しいノードの前に新しいノードを作成します 
                api.insertBefore(parentElm、createElm(newStartVnode、insertedVnodeQueue)、oldStartVnode.elm);  
            }  
            それ以外 {  
 elmToMove = oldCh [idxInOld];  
                if (elmToMove.sel !== newStartVnode.sel) { // 古いノードの新しいノードの前に新しいノードを作成します 
                    api.insertBefore(parentElm、createElm(newStartVnode、insertedVnodeQueue)、oldStartVnode.elm);  
                }  
                それ以外 {  
                                                           // 古いノード配列で同じノードを見つけ、違いを比較してビューを更新し、位置を移動します 
                    パッチVnode(elmToMove、newStartVnode、insertedVnodeQueue);  
                    oldCh[idxInOld] = 未定義;  
                    api.insertBefore(親Elm、elmToMove.elm、oldStartVnode.elm);  
                }
            }  
新しいStartVnode =新しいCh [++新しいStartIdx];  
        }  
    }  
    // ループの最後で作業を終了する 
    （古い開始ID < = 古い終了ID || 新しい開始ID < = 新しい終了ID）の場合 {  
        （古い開始ID ＞古い終了ID）の場合{  
            // newCh[newEndIdx + 1].elmは、古いノード配列の終了ノードに対応するDOM要素です 
            // newEndIdx+1 は、newEndIdx が以前に正常に一致した後に -1 を必要とするためです。  
            // newCh[newEndIdx + 1].elm、同じノードが一致したため、古いノード配列の終了ノードに対応するDOM要素（oldCh[oldEndIdx + 1].elm）と等しくなります。  
以前= newCh [newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm;  
            // 新しいノード配列に追加のノードを挿入する前に 
            Vnodes を追加します (parentElm、before、newCh、newStartIdx、newEndIdx、insertedVnodeQueue);  
        }  
        それ以外 {  
            // ここでは同じノードと一致しないノードを削除します 
            Vnodes を削除します (親 Elm、oldCh、oldStartIdx、oldEndIdx)。  
        }  
    }  
 }

キーの役割

• 差分操作が高速化されます。
• 差分操作の精度が向上します (レンダリングエラーを回避)
• インデックスをキーとして使用することは推奨されません

これらの効果のいくつかの例を見てみましょう。

差分操作はより正確になります (レンダリング エラーを回避):

例: 3つのDOM要素a、b、cのbとcの間にz要素を挿入する

キーが設定されていません

キーが設定されている場合:

差分操作の精度が向上します (レンダリングエラーを回避)

例: DOM 要素 a、b、c が 3 つあります。要素 a のプロパティを変更した後、要素 a の前に新しい要素 z を追加します。

キーが設定されていません:

キーが設定されていないため、デフォルトは未定義で、ノードは同じです。テキストコンテンツは更新されますが、以前のDOMが引き続き使用されます。したがって、実際にはa->z（aの元のチェック状態は保持され、テキストのみが変更されます）、b->a、c->b、d->cです。トラバーサルが完了すると、別のDOMを追加する必要があることがわかります。最後に、テキストdを含むDOM要素が追加されます。

キーを設定します:

キーが設定されると、a、b、c、d にはすべて対応するキー、a->a、b->b、c->c、d->d が設定されます。内容は同じなので、更新は必要ありません。トラバーサルが終了し、テキスト z を含む DOM 要素が追加されます。

インデックスをキーとして使用することは推奨されません。

インデックスをキーに設定します:

これは明らかに非効率的です。異なるノードの更新のみを検索したいのですが、インデックスをキーとして使用すると計算時間が長くなります。この問題は、キーをノード テキストと一致するように設定することで解決できます。