この記事ではDiffアルゴリズムの使い方を説明します

[[420540]]

1. 基本

Diff アルゴリズムは、仮想 DOM の最小限の更新を実装します。この文は短いですが、仮想 DOM と最小限の更新という 2 つのコア要素が含まれています。

1. 仮想DOM

仮想 DOM とは、実際の DOM ツリーを js オブジェクトの形式で構築することを指し、それによって実際の DOM を操作するブラウザーのパフォーマンスの問題を解決します。

例えば、次のDOMと仮想DOMのマッピング関係

2. 最小限の更新

Diff の目的は、新しい仮想 DOM と古い仮想 DOM の間で更新された最小の部分を見つけ、その部分に対応する DOM を更新することです。

2. 全体のプロセス

Diff アルゴリズムは本当に美しいです。全体のプロセスは以下の図に示されています。

まず、新旧のノードが同じノードであるかどうかを比較します（sel（セレクタ）とkey（一意の識別子）の値が同じかどうかを比較します）。同じノードでない場合は、強制削除が行われます（注：最初に古いノードに基づいて新しいノードを挿入し、次に古いノードを削除します）。
同じノードの場合は、さらに比較する必要があります

まったく同じ、加工なし

新しいノードコンテンツはテキストなので、置き換えるだけです

新しいノードには子ノードがあるため、この時点では慎重に検討する必要があります。古いノードに子要素がない場合は、古いノードをクリアして新しいノードの子要素を挿入するだけです。古いノードに子要素がある場合は、上記の更新戦略に従って解決する必要があります (更新戦略を覚えておけば、あと数年間は自慢できます、666666)。

3. 実戦

実践のない話ばかりです。以下は diff アルゴリズムの核となる内容です。

3.1 パッチ機能

Diff アルゴリズムのエントリ関数は、主に新しいノードと古いノードが同じノードであるかどうかを判断し、それらを異なるロジックに渡して処理します。

エクスポートデフォルト 関数patch(oldVnode, newVnode) {
    // 渡された最初のパラメータがDOMノードか仮想ノードかを判断する
    oldVnode.sel === '' || oldVnode.sel === 未定義の場合{
        // 渡される最初のパラメータはDOMノードであり、仮想ノードにパッケージ化する必要があります
        oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], 未定義, oldVnode);
    } 
 
    // oldVnode と newVnode が同じノードであるかどうかを判定する
    (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel)の場合{
        //同じノードの場合は、精密な比較を実行します
        パッチVnode(古いVnode、新しいVnode);
    }
それ以外{
        // 同じノードではないので、新しいノードを強制的に挿入し、古いノードを削除します
        newVnodeElm = createElement(newVnode); を作成します。 
 
        // 新しいノードを古いノードの前に挿入します
        (古いVnode.elm.parentNode && 新しいVnodeElm) の場合 {
            古いVnode.elm.parentNode.insertBefore(新しいVnodeElm、古いVnode.elm);
        }
        // 古いノードを削除する
        oldVnode.elm.parentNode.removeChild(oldVnode.elm);
    }
 }

3.2 patchVnode関数

この機能は主に、精緻な比較を行う機能です。上記のフローチャートのロジックに従って、メッセージがどのブランチに属するかを判断し、異なる処理ロジックを採用します。 (アイデアは明確で、アルゴリズムは素晴らしいです)

エクスポートデフォルト 関数patchVnode(oldVnode, newVnode) {
    // 新しいvnodeと古いvnodeが同じオブジェクトであるかどうかを判定する
    (古いVnode === 新しいVnode)の場合{
戻る;
    }
    // vnode にテキスト属性があるかどうかを判定する
    newVnode.text !== 未定義 && (newVnode.children === 未定義 || newVnode.children.length === 0) の場合 {
        console.log( '新しい vnode にはテキスト属性があります' );
        (新しいVnode.text !== 古いVnode.text) の場合 {
            古いVnode.elm.innerText = 新しいVnode.text;
        }
    }
それ以外{
        // 新しいvnodeにはテキスト属性はありませんが、子ノードがあります
        console.log( '新しい vnode にはテキスト属性がありません' );
        // 古いものに子があるかどうかを判定する
        oldVnode.children !== 未定義 && oldVnode.children.length > 0 の場合 {
            // 古いものには子があり、新しいものにも子があります
            古いVnode.elm、新しいVnode.childrenを更新します。
        }
それ以外{
            // 古いものには子がなく、新しいものには子があります
            // 古いノードの内容をクリアする
            oldVnode.elm.innerHTML = '' ;
            // 新しい vnode の子ノードを走査し、DOM を作成し、ツリーを上に進みます
( i = 0 とします; i < newVnode.children.length; i++) {
                dom = createElement(newVnode.children[i]); を作成します。
                古いVnode.elm.appendChild(dom);
            }
        }
    }
 }

3.3 updateChildren関数

コア関数は、主に古い仮想ノードと新しい仮想ノードの両方に子要素がある状況を担当し、比較戦略に従ってそれらを順番に比較し、最終的に子要素内の変更された部分を見つけて、最小限の更新を実現します。この部分には、次のようないくつかの指針があります。

古いフロントは、更新前の仮想DOMのヘッドポインタを参照します。
古いバックは、更新前の仮想DOMの末尾ポインタを参照します。
新しいフロントは、更新された仮想DOMのヘッドポインタを参照します。
新しいものは更新された仮想DOMの末尾ポインタを参照します

上記の更新戦略に従って、古い仮想 DOM を新しい仮想 DOM に更新するプロセスは次のようになります。

「新しい後、古い後」戦略がヒットし、その後、文字後の DOM ノード (つまり、ノード 1) が古い後ノード (ノード 3) の後ろに移動し、その後、古い前ノードポインターが下に移動し、新しい後ノードポインターが上に移動します。
「新しい後ろ、古い前」戦略は依然としてヒットし、同じ操作を実行して、ノード 2 を古い後ろのノード (ノード 3) の後ろに移動し、古い前部のノードを下に移動し、新しい後ろのノードを上に移動します。
「新しいフロント、古いフロント」戦略がヒットすると、DOM ノードは変更されず、古いフロントノードと新しいフロントノードの両方が下に移動します。
ループから飛び出すと動きは終了します。

エクスポートデフォルト 関数updateChildren(parentElm, oldCh, newCh) {
    // 古いフロント
    oldStartIdx を 0 にします。
    // 新しいフロント
    newStartIdx = 0 とします。
    // 古い
    oldEndIdx = oldCh.length - 1 とします。
    // 新しい
    newEndIdx = newCh.length - 1 とします。
    // 古いフロントノード
    oldStartVnode = oldCh[0]とします。
    // 古い投稿ノード
    oldEndVnode = oldCh[oldEndIdx]とします。
    // 新しいフロントノード
    newStartVnode = newCh[0]とします。
    // 新しい投稿ノード
    newEndVnode = newCh[newEndIdx]とします。 
 
    keyMap をnullにします。 
 
    (古い開始Idx <= 古い終了Idx && 新しい開始Idx <= 新しい終了Idx) {
        // undefined でマークされたコンテンツをスキップします
        （oldStartVnode == null || oldCh[oldStartIdx] === 未定義）の場合{
            古いStartVnode = 古いCh[++古いStartIdx];
        }
そうでない場合 (oldEndVnode == null || oldCh[oldEndIdx] === 未定義) {
            oldEndVnode = oldCh[ --oldEndIdx];  
        }
そうでない場合 (newStartVnode == null || newCh[newStartIdx] === 未定義) {
            新しいStartVnode = 新しいCh[++新しいStartIdx];
        }
そうでない場合 (newEndVnode == null || newCh[newEndIdx] === 未定義) {
            新しいEndVnode = 新しいCh[ --newEndIdx];  
        }
そうでない場合 (checkSameVnode(oldStartVnode, newStartVnode)) {
            // 新しいフロントと古いフロント
            console.log( '新しいフロントと古いフロントがヒットしました' );
            パッチVnode(古い開始Vnode、新しい開始Vnode);
            古いStartVnode = 古いCh[++古いStartIdx];
            新しいStartVnode = 新しいCh[++新しいStartIdx];
        }
そうでない場合 (checkSameVnode(oldEndVnode, newEndVnode)) {
            // 新旧の女王
            console.log( '新しいヒットと古いヒット' );
            パッチVnode(古いEndVnode、新しいEndVnode);
            oldEndVnode = oldCh[ --oldEndIdx];  
            新しいEndVnode = newCh[ --newEndVnode];  
        }
そうでない場合 (checkSameVnode(oldStartVnode, newEndVnode)) {
            console.log( 'ヒット後の新しい値とヒット前の古い値' );
            パッチVnode(古い開始Vnode、新しい終了Vnode);
            // 新しい背面が古い前面に当たったとき、ノードを古いノードの背面に移動します。
            親Elm.insertBefore(oldStartVnode.elm、oldEndVnode.elm.nextSibling);
            古いStartVnode = 古いCh[++古いStartIdx];
            新しいEndVnode = 新しいCh[ --newEndIdx];  
        }
そうでない場合 (checkSameVnode(oldEndVnode, newStartVnode)) {
            // 新しい前と古い後
            console.log( 'ヒット前の新しい値とヒット後の古い値' );
            パッチVnode(古い終了Vnode、新しい開始Vnode);
            // 新しいフロントと古いバックがヒットすると、ノードを移動する必要があり、新しいフロントが指すノードは古いノードの前面に移動されます。
            親Elm.insertBefore(oldEndVnode.elm、oldStartVnode.elm);
            oldEndVnode = oldCh[ --oldEndIdx];  
            新しいStartVnode = 新しいCh[++新しいStartIdx];
        }
それ以外{
            // 4つのヒットのいずれも
            // 毎回古いオブジェクトを走査しなくても済むように、keyMap マッピング オブジェクトを作成します
            キーマップの場合
                キーマップ = {};
 ( i = oldStartIdx; i <= oldEndIdx; i++ とします) {
                    定数キー= oldCh[i] .key ;
                    if (キー!== 未定義) {
                        keyMap[キー] = i;
                    }
                }
            }
            // keyMap 内の現在の項目 (newStartIdx) のマッピング位置を検索します
            const idxInOld = keyMap [newStartVnode.key ];
            idxInOld === 未定義の場合{
                // idxInOld が未定義の場合は、まったく新しいアイテムを意味します。このとき、アイテムは DOM ノードとして作成され、古いアイテムの前に挿入されます。
                親Elm.insertBefore(createElement(newStartVnode)、oldStartVnode.elm);
            }
それ以外{
                // 未定義でない場合は、新しい項目ではないので移動する必要があります
                elmToMove は、古い Ch[idxInOld] を移動します。
                elmToMove に新しい StartVnode を追加します。
                // この項目を未定義に設定し、この項目が処理されたことを示します
                oldCh[idxInOld] = 未定義;
                // 動く
                親Elm.insertBefore(elmToMove.elm、oldStartVnode.elm);
            }
            // ポインタを下に移動し、新しいヘッドのみを移動します
            新しいStartVnode = 新しいCh[++新しいStartIdx];
        }
    } 
 
    // ループが終了したら、未処理の項目を処理する
    (新しい開始ID <= 新しい終了ID) の場合 {
        console.log( 'new にはまだ処理されていないノードが残っています。項目を追加し、残りのすべてのノードを oldStartIdx の前に挿入します' );
        // 新しい newCh を走査し、まだ処理されていない古いものに追加します
(i = newStartIdx; i <= newEndIdx; i++)の場合{
            // insertBefore メソッドはnull を自動的に識別し、 nullの場合は自動的にキューの末尾に配置されます。
            // newCh[i]はまだ実際のDOMを持っていないので、createElement関数を呼び出してDOMにします
            親Elm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm);
        }
    }
そうでない場合 (oldStartIdx <= oldEndIdx) {
        console.log( 'old にはまだ処理されていないノードが残っているので、その項目を削除する必要があります' );
        // oldStart と oldEnd ポインタ間の項目を一括削除します
(i = oldStartIdx; i <= oldEndIdx; i++)の場合{
            もし (oldCh[i]) {
                親Elm.removeChild(oldCh[i].elm);
            }
        }
    }
 }