diffアルゴリズム

前置き

データが変更されたとき、reactとVueはどのようにViewを更新しますか？

実際の DOM ノードをレンダリングするオーバーヘッドは非常に大きく、例えば、あるデータが変更され、それを実際の DOM ツリーにレンダリングすると DOM ツリー全体が再描画され、再配置されることがあります。 diff アルゴリズムはこれを実現できます。

まず、実DOMを元に仮想DOMを生成し、仮想DOM内のノードのデータが変更されると、新しいnewVnodeを生成し、newVnodeとoldVnodeを比較し、差異があればそのまま実DOMを変更し、oldVnodeの値をnewVnodeに更新します。newVnode

vdomは純粋なJSオブジェクトであるため、操作は非常に効率的ですが、vdomの変更は最終的にDOM操作に変換されるため、効率的なDOM操作を実現するには、一連の効率的な仮想DOM差分アルゴリズムが必要です。

Virtual DOM 実際のDOMとの差分？

仮想DOMは、実際のDOMのデータを抽出し、オブジェクトの形でツリー構造をシミュレートするもので、差分アルゴリズムも仮想DOMと比較されます：

 <div>
 <span>content</span>
 </div>

対応する仮想 DOM

var vnode = {
 tag: '<div>',
 children: [
 { tag: 'span', text: 'content'}
 ],
}

Diff

Diff アルゴリズムの役割

Diff アルゴリズムは、仮想 DOM のどの部分が変更されたかを把握し、ページ全体を再レンダリングすることなく、その部分に対してネイティブ DOM 操作を実行するために使用されます。

diff アルゴリズムは、和解の具体的な実装です。リコンシリエーションは 、仮想 DOM ツリーを実際の DOM ツリーに変換する最小限の操作です。

Diffアルゴリズムとは

ツリー構造をレベル別に分解し、同じレベルの要素のみを比較します。比較を容易にするために、リスト構造の各セルに一意のキー属性を追加します。

従来のDiffアルゴリズム

差分アルゴリズムとは、木構造を別のレッスンの木構造へ変換して計算することであり、最小のステップ数を必要とします。従来の差分アルゴリズムを使用して比較のためにループ再帰を介してノードをトラバースする場合、その複雑さはO(n^3)に達し、nはノードの総数であり、効率は非常に低く、1,000ノードの表示に参加するには、一度に数十億回の比較を実行する必要があります。

let result = [];
// リーフノードを比較する
const diffLeafs = funnction(beforeLeaf, afterLeaf){
 // 大きい方のノードの長さを取得する
 let count = Math.max(beforeLeaf.children.length, afterLeaf.children.length);
 for (let i = 0; i < count; i ++) {
 const beforeTag = beforeLeaf.children[i];
 const afterTag = afterLeaf.children[i];
 if (beforeTag === undefined) {
 // afterTagノードを追加する
 result.push({ type: 'add', element: afterTag });
 } else if (afterTag === undefined) {
 // beforeTagノードを削除する
 result.push({ type: 'remove', element: beforeTag });
 } else if (beforeTag.tagName !== afterTag.tagName) {
 // ノード名が変わったら、前のノードを削除し、後のノードを追加する。
 result.push({ type: 'remove', element: beforeTag });
 result.push({ type: 'add', element: afterTag });
 } else if (beforeTag.innerHTML !== afterTag.innerHTML) {
 // ノード名が同じで内容が変わる場合は、ノードを変更する。
 if (beforeTag.children.length === 0) {
 result.push({
 type: 'changed',
 beforeElement: beforeTag,
 afterElement: afterTag,
 html: afterTag.innerHTML
 });
 } else {
 // 再帰的比較
 diffLeafs(beforeTag, afterTag);
 }
 }
 }
 return result;
}

diff 3つの戦略

• 1 戦略 I. ツリーの差分

  ウェブUIにおいて、階層レベルをまたぐDOMノードの移動は稀であり、無視できるものです。

• 2 戦略2, コンポーネントの差分

  同じクラスを持つ2つのコンポーネントは、同じようなツリー構造を生成します。異なるクラスを持つ2つのコンポーネントは、異なるツリー構造を生成します。

• 3 ストラテジー 3、要素の差分

  同じレベルの子ノードのグループでは、一意の ID によって区別されます。

tree diff

React は、updateDepth を介して仮想 DOM ツリーを階層的に制御します。

ツリーは階層的に比較され、2 つのツリーは同じレベルのノードに対してのみ比較されます。ノードが存在しない場合、ノードとそのノードは完全に削除され、それ以降の比較は行われません。

DOM ツリー全体が 1 回の走査だけで比較されます。

DOMノードが階層をまたいで操作された場合、diffはどのような動作をしますか？

A: diffは単純に同じレベルでのノード位置の変換のみを考慮し、レベルをまたぐ場合はノードの作成と削除の操作のみです。

上記のように、Aをルートノードとするツリー全体は移動されずに再作成されるため、DOMノードのクロスレベル操作は行わないことが公式に推奨されており、実際にDOMノードを削除したり追加したりする代わりに、CSSを介してノードを非表示にしたり表示したりすることができます。

Vue Diff

Vueの中核は双方向バインディングと仮想DOMです。vdomはvnodeをノードとするツリー構造で、vnodeとブラウザDOMのnodeは1つずつ対応し、対応するnodeにはvnodeのelmプロパティからアクセスできます。

コンセプト：diffアルゴリズムは、2つのモジュールの前後の差分を比較する最適化ツールであり、差分を修正するプロセスをパッチと呼びます。

vueのリストループには、key="一意の識別子 "を追加する必要があります。

ユニークな識別子は、id、indexおよびその他のユニークなフィールド値の内部の項目することができますので、Vueのコンポーネントは、キーがコンポーネントの一意性を識別することができます増加する再利用性が高いので、キーは、仮想DOMをより面白く更新する方法ですか？

• 例

  

  つまり、CをFに更新し、DをCに更新し、EをDに更新し、最後にEを挿入します。

そのため、Diffアルゴリズムがセカンダリノードを正しく識別し、新しいノードを挿入するための正しい位置領域を見つけることができるように、キーを使用して各ノードを一意に識別する必要があります。

Vueは、さまざまな方法で差分のパフォーマンスを向上させます：

特別なシナリオの優先順位付け

先頭に同じ型のノード、末尾に同じ型のノード

これらのノードは更新の前後で位置が変わらないので、対応する DOM を移動する必要はありません。

先頭/末尾の同じタイプのノード

このタイプのノードは位置が明確なので、探す必要はありません。これらのシナリオに対処した後、一方では移動する必要のない一部の DOM が迅速に処理され、他方では処理するノードが少なくなるため、後続の処理の処理範囲が狭まり、パフォーマンスが向上します。

インプレース再利用

インプレース再利用とは、VueがDOMをできるだけ移動させずに再利用することを意味します。

Vueは、変更前と変更後のポインタが同じノードを指しているかどうかを判断しています。実際には、実際に同じDOMノードを参照している必要はなく、ポインタの型が同じかどうかを判断しているだけです。同じ型であれば、VueはDOMを直接再利用するので、DOMを移動する必要がないという利点があります。

React Diff

DiffアルゴリズムはReactの更新フェーズでのみ使用されます。

• リアクトは従来のアルゴリズムを使うことはないでしょう。

ReactのDiffアルゴリズム。

1. つまり、React Diffアルゴリズムの差分検索は、基本的に2つのJavaScriptオブジェクトの差分検索です。
2. 3つの戦略に基づく：[Diffアルゴリズムの3つの戦略] O(n^3)複雑度をO(n)複雑度に変換

調整 仮想 DOM ツリーを最小限の操作で実際の DOM ツリーに変換するプロセスを調整と呼びます。

React Diffアルゴリズム、Diffアルゴリズムは、和解の具体的な実装です。

element diff

ノードが同じ階層にある場合、diffアルゴリズムは3つのノード操作を提供します。

シナリオ1：同じノードが古いセットと新しいセットに存在するが、場所が異なる場合のノードの移動方法：

上図のBを見ると、Reactはまず新ノードからBを取得し、旧ノードにも同じノードBが存在するかどうかを判断し、Bが存在すると判断すると、Bを移動するかどうかを判断しに行きます。旧ノードのBは、旧ノードではindex=1、lastIndex=0であり、index < lastIndexの条件を満たさないため、Bは移動操作を行いません。この時点で、lastIndex=1 の大きい方の操作。

注意: lastIndexはfloatのようなもので、マップのインデックスのようなものです。

Aを見ると、Aは古い時点でindex=0、この時点でlastIndex=1となり、index< />を満たします。

Dを見ると、同じ、移動なし、変更lastIndex=max(index,lastIndex)=3。

Cを見て、同じ、移動で、古いインデックス= 2のCは、インデックス< />を満たしています。

Cはすでに最後のノードなので、diff操作は終了。