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