今日は Vue でよく聞く Diff アルゴリズムに関する知識を共有します。
まだ Diff アルゴリズムが何で、どのように役立つのかよくわからない友達もいるかもしれませんので、まずは Vue3 における Diff アルゴリズムの役割などの関連知識を大まかに紹介し、基礎がない学生でもできるだけ理解できるようにこの文章を見やすくします。
もしあなたがすでに関連する前提知識を大まかに理解しているのであれば、この部分を飛ばして、下の文章でパッチの最小化更新（つまり Diff アルゴリズム）の歴史を見てみましょう。
この記事ではできるだけコードを減らし、より多くの画像アニメーションデモを使用して、私たちは一枚一枚の思考図を通じて先輩たちの知恵の結晶を探求します。
イントロダクション#
Vue では仮想 VNode を使用して比較し、マウント / 更新 / アンマウント操作を行いますが、その中で最も重要なのは更新操作です。更新操作の効率はレンダリングページの更新量に影響を与え、コンパイル時にフレームワークがもたらす更新量に近づくほど性能が向上します。Vue というコンパイル時 + 実行時のフレームワークがもたらす更新量を最小化するために、Diff アルゴリズムが導入され、新旧ノードツリー間の最小の差異を検出し、最小の更新量をもたらし、ページ性能を向上させます。
現在、『Vue.js の設計と実装』においてDiff アルゴリズムは新旧ノードの両方にkeyが存在する場合に限られており、無 keyの場合にパッチの最小化をどのように行うかについては言及されていません。keyは要素の一意の識別子として新旧ノードの比較に使用できます。
次に、コードとアイデアの進化に伴い、更新操作における性能向上を体験し、単純で粗暴な方法から複雑で優雅な方法へと進んでいきます。
直接的な方法#
最も単純で粗暴な方法は、新旧ノードに差異が存在するかどうかを全く気にせず、旧ノードをすべてアンマウントし、新ノードをコンテナに再マウントすることです。これにより更新操作が完了します。この方法はDiffと呼ばれる必要すらありません。なぜなら、差異を全く気にせず、無思考でアンマウントとマウントを行うだけだからです。以下の図のように、こうした直接的な全アンマウントと全マウントの操作は、直接的で粗暴ですが簡単です。しかし、性能は命令型コードとの差が大きく、アンマウントする必要がないノードは単に位置を移動するだけで目標を達成できるのに、依然としてアンマウントと再マウントの操作を行う必要があるため、このようなアルゴリズムについての考察が始まりました。より高い性能を求めて苦心する旅が始まります。
図 0-1 全アンマウント & 全マウント
簡単な方法#
起源#
全アンマウント & 全マウントのような粗暴なプロセスと比較して、私たちはまず再利用可能なノードの評価という問題を明確に見ることができます。図 1-1の新旧二組のノードを観察してみましょう。
図 1-1 新旧二つの木の比較図
私たちは明らかに、いくつかのノードは非常に簡単に移動するだけで済むこと、いくつかのノードはテキスト内容の差異を更新するだけで済むこと、またいくつかのノードは余分な旧ノードをアンマウントするか、余分な新ノードをマウントするだけで済むことを発見できます。
再利用と key#
では、新旧二つの木のノードが同じかどうかをどのように比較すればよいのでしょうか？苦心の末、Vue は私たちに答えを与えました。ノードに新しい属性keyを追加し、ノードの一意の値として使用します。これはノードの身分証明書のような存在です。
図 1-2 key ありと key なしのノード比較状況
このように、ノードを比較する際に根拠ができ、無思考の全アンマウント & 全マウントのような操作を避けることができ、真にdiffアルゴリズムの探求プロセスに入ることができます。
現在、私たちは主観的にこのノードリスト内の各ノードに一意のkeyがあると規定しましたので、次のステップとしてdomノードの再利用を処理することができます。
次に、図 1-1の新旧ノードツリーを再度観察し、できるだけ少ない操作で dom を処理するために何をすべきかを見てみましょう。
この新旧ノードツリーの中で、以下のような状況を発見しました：
- p-1、p-2、p-3、p-4 ノードは旧ノードと再利用可能です。
- p-5 ノードはアンマウントする必要があります。
- p-6 ノードはマウントする必要があります。
- ノードは位置を移動する必要があるかもしれません。
次に私たちが行うべきことは非常に簡単です。大まかに上記の状況に対応して処理します：
- 新しい木に基づいて旧木にkey 同値のノードがあるかどうかを確認します。もしあれば、最初にパッチ操作を行います。
- 新しい木のあるノードが旧木に再利用可能なノードを見つけられない場合、それはマウントする必要がある新しいノードであることを示します。
- 旧木のあるノードが新しい木に対応するノードを見つけられない場合（つまり再利用されていない場合）、それはアンマウントする必要がある旧ノードであることを示します。
- 移動が必要なノードを移動します。
/**
* 簡単Diffアルゴリズム
* @param oldVNode 旧ノードリスト
* @param vNode 新ノードリスト
* @param container ノードリストマウントコンテナ
*/
function simpleDiff(oldVNode: VNode[], vNode: VNode[], container: ContainerElement) {
for (let i = 0; i < vNode.length; i++) {
let findLock = false; // この新ノードが再利用可能な旧ノードを見つけたかどうかを示す
for (let j = 0; j < oldVNode.length; j++) {
if ((typeof vNode[i].key !== "undefined") && vNode[i].key === oldVNode[j].key) { // 一意のkeyに基づいて再利用可能な要素を探す
findLock = true; // 再利用可能なノードを見つけた
// このステップでoldノードのelementをnewノードのelement属性に同期します
patch(oldVNode[j], vNode[i], container);
// ??? ノードは移動する必要がありますか？どこに移動すべきですか？
break;
};
}
if (!findLock) {
// ここに到達した場合、再利用可能なノードが見つからなかったことを示し、新しいノードを作成して挿入操作を行う必要があります
// patch(null, vNode[i], container, ???); 挿入要素のアンカー位置
}
};
// 旧木を遍歴し、アンマウント操作を行う必要があるノードを見つけます
oldVNode.forEach(oldElement => {
if (!vNode.find(newElement => newElement.key === oldElement.key)) {
unMountElement(oldElement);
};
});
};
これらの処理手順の中での難点はノードの移動です。どのように移動すべきか、どのノードの前に移動すべきか？新ノードはどの位置にマウントすべきか？これもまた Diff プロセスにおいて非常に重要なステップです。
移動#
次に、図 1-2を組み合わせて、私たちがどのように要素を移動 / マウントすべきかを観察します。以下の図図 1-3
図 1-3 新旧仮想ノードと実際のノード
少し混乱していると感じませんか？ここでの移動要素のアンカー位置はどこでしょうか？私たちは逆の思考を考えて、ノードが移動する必要がないのはどのような場合かを考えてみましょう。その答えは、新旧二組のノードリストの順序が変わらない場合です。順序が変わらないということは、毎回新ノードリストが旧ノードリストに再利用可能なノードを見つける際の旧ノードのインデックスが増加する傾向があることを示しています。
例えば、図 1-2を組み合わせると、見つかった旧ノードのインデックスの傾向は [0, 1, 2, 3, 4] であることが明らかにわかります。
図 1-3を組み合わせて見ると、見つかった旧ノードのインデックスの傾向は [3, 2, -1, 0, 1] です（ここでは新しくマウントされたノードが見つかった旧ノードのインデックス値を **-1** と表現していますが、実際の移動プロセスでは新しくマウントされたノードは傾向計算に入らないことに注意してください）。さて、見つかった旧ノードのインデックスの傾向を見てみると、p-4 は旧ノードのインデックス 3 にあり、p-3 は旧ノードのインデックス 2 にあります。これにより、新ノードの中で p-3 ノードが移動する必要があることがわかります。p-3 の実際の要素位置は p-4 の実際の要素位置の後にあります。このように、この例ではすべての新しいノードが p-4 の後にあり、私たちは p-4 の旧インデックス位置を基準にして比較を行います。しかし、より大きな例では、基準を更新し続ける必要があります（増加傾向の終了位置のインデックス）し、このノードが移動する必要があるかどうかを判断し続ける必要があります。
この移動プロセスをより便利で直接的、包括的、迅速に体験するために、このコード実行アニメーションデモ図 1-4を見てみましょう。
図 1-4 ノード移動実行全プロセスアニメーションデモ図
/**
* 簡単Diffアルゴリズム
* @param oldVNode 旧ノードリスト
* @param vNode 新ノードリスト
* @param container ノードリストマウントコンテナ
*/
function simpleDiff(oldVNode: VNode[], vNode: VNode[], container: ContainerElement) {
let lastMaxIndex = 0; // 現在の最大旧インデックス値
for (let i = 0; i < vNode.length; i++) {
let findLock = false;
for (let j = 0; j < oldVNode.length; j++) {
if ((typeof vNode[i].key !== "undefined") && vNode[i].key === oldVNode[j].key) {
// ***patchコードを省略***
if (j < lastMaxIndex) { // 移動が必要
const prevElement = vNode[i - 1];
if (prevElement) {
insertElement(container, oldVNode[j]._element, prevElement._element?.nextSibling ?? null);
};
} else {
lastMaxIndex = j;
}
break;
};
}
if (!findLock) {
// ここに到達した場合、再利用可能なノードが見つからなかったことを示し、新しいノードを作成して挿入操作を行う必要があります。アンカー位置は上のロジックと一致します。
const prevElement = vNode[i - 1];
patch(null, vNode[i], container, prevElement?._element?.nextSibling ?? null);
}
};
// ***ノードアンマウントコードを省略***
};
双端#
起源#
簡単 Diff アルゴリズムでは、時々いくつかの例でより迅速なステップを発見することがあります。以下の図
図 2-1 特殊な例
簡単 Diff アルゴリズムの実行プロセスに従うと、p-1 を p-3 要素の後方に移動させ、次に p-2 を p-1 要素の後方に移動させる必要があります。しかし、私たちの目でこの新旧ノードリストを観察すると、明らかに p-3 を p-1 ノードの前方に移動させるだけで済むことがわかります。図 2-2のように、明らかに一度で解決できる方法が Diff アルゴリズムでは二回のノード移動を必要とします。
図 2-2 一部の状況で DOM の移動回数を減らす処理
思想#
最適化ポイントが見つかったので、私たちはどのように最適化するかを考えなければなりません。双端 Diff アルゴリズムの思想では、新旧ノードリストのそれぞれに対応する先頭と末尾のインデックスを作成し、4 つのインデックスが指す VNode を比較し、対応するインデックスを移動させ続けます。図 2-3
図 2-3 双端インデックスと比較指示図
いくつかの状況では、確かにこの 4 回の比較を通じて対応するインデックスを移動させることで、先頭と末尾でkey 同値の処理が必要なノードを見つけることができます。例えば図 2-3の例では、私たちはまだ考えないでおきましょう（p-3<=>p-1、p-2<=>p-3、p-3<=>p-3、p-2<=>p-1）この 4 回の比較で同keyが見つからなかった場合、この場合は後で処理します。まず、私たちはこのような状況に遭遇した場合、ノードをどのように移動すべきかを考えます。
移動#
-
newVNode[newStartIndex].key === oldVNode[oldStartIndex].key等しい場合、ノードは移動する必要がなく、パッチ補修操作を行うだけで済み、
newStartIndexとoldStartIndexを後方に移動させます。 -
newVNode[newEndIndex].key === oldVNode[oldEndIndex].key等しい場合、ノードは移動する必要がなく、パッチ補修操作を行うだけで済み、
newEndIndexとoldEndIndexを前方に移動させます。 -
newVNode[newEndIndex].key === oldVNode[oldStartIndex].key元々旧ノードリストの先頭インデックス位置にあり、現在は新ノードリストの末尾インデックス位置に移動する必要があることを示します。この比較では、元々旧ノードリストの先頭にあったものが現在新ノードリストの末尾にあることを示し、ノードを
oldVNode[oldEndIndex]の次の位置に移動させる必要があります。その後、このラウンドで使用されたインデックスを正しく更新し、newEndIndexを前方に移動させ、oldStartIndexを後方に移動させます。 -
newVNode[newStartIndex].key === oldVNode[oldEndIndex].key元々旧ノードリストの末尾インデックス位置にあり、現在は新ノードリストの先頭インデックス位置に移動する必要があることを示します。この比較では、元々旧ノードリストの末尾にあった要素が現在新ノードリストの先頭にあることを示し、ノードを
oldVNode[oldStartIndex]の前の位置、つまり先頭に移動させる必要があります。その後、参加インデックスを正しく更新し、newStartIndexを後方に移動させ、oldEndIndexを前方に移動させます。
図 2-3の例に従って、明らかにこの 4 つの条件だけで十分ですが、図 2-4の例を見てみると、これらの 4 つの状況が満たされない場合、どのように処理すべきか？
図 2-4 特殊な例
明らかに、私たちはnewVNode[newStartIndex]を基準にして、oldVNode の中でkey同値のノードを見つけようとすればよいのです。もし見つかれば、patchを行い、newStartIndexインデックスを後方に移動させ、oldVNode の同keyのノードをundefinedにします。この時、私たちは oldVNode の中で再度探し、見つかったものをundefinedに処理します。これにより、後続のインデックスがこのノードに到達した際に、重複処理を引き起こすことを防ぎます。しかし、同様に、oldVNode[oldStartIndex]またはoldVNode[oldEndIndex]がundefinedである状況を避けるために、前述の 4 重判断の条件を前置きし、状況に応じてoldStartIndexまたはoldEndIndexのインデックスを適時移動させる必要があります。当然、同keyのノードを見つける状況が存在する場合、見つからない場合も存在します。見つからない場合は、newVNode[newStartIndex]が新しいノードであることを示し、マウント操作が必要です。
現在、私たちは状況判定を完了し、特殊な状況も処理しましたが、より特殊な例では、上部のノード数が異なる場合、一方がすでにoldStartIndex > oldEndIndexでループを終了したり、もう一方がnewStartIndex > newEndIndexでループを終了したりすることがあり、ノードが多い方に未アンマウント / 未マウントの状況が発生します。このような状況は常に片側のものであることがわかります。したがって、私たちは一定の規則をまとめ、whileループの終了に備えます。
簡単 Diff アルゴリズムと同様に、ここでもコード実行アニメーションデモを提供し、双端 Diff を視覚的に理解するのを助けます。下の図 2-5を参照してください。
図 2-5 双端 Diff 実行フローチャート
/**
* 双端diffアルゴリズム
* @param oldVNode
* @param vNode
* @param container
*/
function doubleEndedDiff(oldVNode: (VNode | undefined)[], vNode: VNode[], container: ContainerElement) {
let oldStartIndex = 0;
let newStartIndex = 0;
let oldEndIndex = oldVNode.length - 1;
let newEndIndex = vNode.length - 1;
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
const oldStartVNode = oldVNode[oldStartIndex];
const oldEndVNode = oldVNode[oldEndIndex];
const newStartVNode = vNode[newStartIndex];
const newEndVNode = vNode[newEndIndex];
// 旧ノードがundefinedに操作されるのを防ぐ
if (!oldStartVNode) {
oldStartIndex++;
continue;
}
if (!oldEndVNode) {
oldEndIndex--;
continue;
}
// 4つの比較移動ノードの状況
if (oldStartVNode.key === newStartVNode.key) {
patch(oldStartVNode, newStartVNode, container)
oldStartIndex++;
newStartIndex++;
} else if (oldEndVNode.key === newEndVNode.key) {
patch(oldEndVNode, newEndVNode, container);
oldEndIndex--;
newEndIndex--;
} else if (oldStartVNode.key === newEndVNode.key) {
patch(oldStartVNode, newEndVNode, container);
insertElement(container, oldStartVNode._element, oldEndVNode._element?.nextSibling);
oldStartIndex++;
newEndIndex--;
} else if (oldEndVNode.key === newStartVNode.key) {
// パッチを打つ
patch(oldEndVNode, newStartVNode, container);
insertElement(container, oldEndVNode._element, oldStartVNode._element);
// インデックスを移動
oldEndIndex--;
newStartIndex++;
} else {
// 旧ノードの中で新ノードと同じkeyのノードを見つける
const findOldIndex = oldVNode.findIndex(node => node && node.key === newStartVNode.key);
if (findOldIndex > 0) {
// パッチを打つ
patch(oldVNode[findOldIndex]!, newStartVNode, container);
insertElement(container, oldVNode[findOldIndex]!._element, oldStartVNode._element);
oldVNode[findOldIndex] = undefined;
newStartIndex ++;
} else { // このnewStartVNodeは新しいノードであることを示します
patch(null, newStartVNode, container, oldStartVNode._element);
newStartIndex++;
}
}
}
// 旧ノードがすでにループを終えたが、新ノードに残りがある場合、これらの残りの新ノードをマウント操作する必要があります
if (oldEndIndex < oldStartIndex && newStartIndex <= newEndIndex) {
for (let i = newStartIndex; i <= newEndIndex; i++) {
patch(null, vNode[i], container, vNode[i - 1]?._element?.nextSibling);
}
} else if(newEndIndex < newStartIndex && oldStartIndex <= oldEndIndex) {
for (let i = oldStartIndex; i <= oldEndIndex; i++) {
oldVNode[i] && unMountElement(oldVNode[i]!);
}
}
}
高速#
起源#
双端 Diff アルゴリズムを使用する際、Vue がjs-framework-benchmarkでスコアを測定する際に、iviとinfernoが採用している高速 Diffの性能が、双端 Diff を使用する Vue よりも若干優れていることに気付きました。そのため、性能向上のためにその考え方や経験を理解し、参考にする必要があります。
図 3-1 ivi,inferno,vue,react 実測性能比較
雑談ですが、以前、ある人が React の性能が遅いのは、React 内部で仮想ノードのデータ構造が独自に設計された単方向リスト構造であるため、React は双端 Diff のようなアルゴリズムを使用できず、単方向で Diff を探すしかないからだと不満を言っていました。ある開発者は React の考え方を参考にし、独自に設計されたデータ構造を放棄し、双端 Diff を採用した結果、性能が明らかに向上しました。例えばUnisのように。
思想#
あるシナリオでは、要素の前置ノードと後置ノードが同じで、中央部分の要素だけが異なる場合、非常に似た考え方のアルゴリズム処理が **「純テキスト Diff」** と呼ばれます。このアルゴリズムは主に純テキストに使用されます。以下の図 3-1。
図 3-1 純テキスト Diff 思想の例
私たちは、新旧のテキストの中で、中央のdivだけが変化していることを発見しました。文字のinputのために。では、この考え方が新旧ノードリストの処理に役立つかどうかを見てみましょう。以下の例を観察します。図 3-2
図 3-2 純テキスト Diff 思想を応用した例
私たちは、同じ前置ノード（つまりnewVNode[startIndex] === oldVNode[startIndex]）と同じ後置ノード（newVNode[endIndex] === oldVNode[endIndex]）を優先的に処理し、その後、混乱した中間ノードを個別に処理することが良い選択のように思えます。これにより、更新操作が必要なノードに遭遇した際に、現在の新ノードが移動する必要があるかどうかを考慮する必要がなくなります。
しかし、考えを進めると、この考え方の最適化ポイントだけでどれだけの性能向上が見込めるのか、少し信じられない気がします。もちろん、高速 Diff アルゴリズムでは、最長増加部分列という概念も導入されています。この概念を導入する目的は、同じ前後ノード以外の残りのノードをより効率的に処理し、移動などの操作を助けるためです。以下の図 3-3を参照してください。
図 3-3 高速 diff アルゴリズムノード移動実行示意図
移動#
上の図を見た後、重要なポイントはsourceがどのように生成されるかです。sourceは新ノードが旧ノードの中で対応するインデックスを記録するために使用されます。通常、二重forループを通じてこのような効果を達成し、sourceを形成しますが、これには時間計算量が高いという欠点があります。O(n^2)に達し、データ量が増えるほど、時間が倍増します。
const newVNodePatchCount = newEndIndex - startIndex + 1;
const source = new Array(newVNodePatchCount).fill(-1); // 新旧ノード位置マッピング
let moved = false;
let pos = 0;
// 二重for時間計算量高い, O(n^2)
for (let i = startIndex; i <= newEndIndex; i++) {
for (let j = startIndex; j <= oldEndIndex; j++) {
if (vNode[i].key === oldVNode[j].key) { // 新旧ノードマッピングポイントを見つける
patch(oldVNode[j], vNode[i], container);
source[i - startIndex] = j;
if (j < pos) { // 新ノードツリーの中での最大インデックスを特定し、ノード移動の必要性を判断する
moved = true;
} else {
pos = j;
}
break;
}
}
}
// 再利用されなかったノードをアンマウントするために旧ノードリストをループします
oldVNode.forEach(oldElement => {
if (!vNode.find(newElement => newElement.key === oldElement.key)) {
unMountElement(oldElement);
};
});
時間計算量はアルゴリズムの中で必ず把握しておくべき基礎であり、アルゴリズムの所要時間を大まかに示すために使用されます。それに相応して、空間計算量が頻繁に伴って現れます。空間計算量は、アルゴリズムが必要とする / 消費するメモリの大きさを大まかに示すために使用されます。現在の時代において、メモリ容量は完全にサポートされているため、時間計算量を低下させるために、しばしば空間を時間で交換するという手法が取られます。つまり、より多くのメモリを使用して時間計算量を低下させるということです。
私たちは再び上記のコードを振り返ると、何か見覚えがある感じがします。そうです、これは簡単 Diff アルゴリズムです。移動ノードと新規ノードの機能を除いて、他はほぼ一致しています。次に、以下の最適化後のコードを観察します。
const newVNodePatchCount = newEndIndex - startIndex + 1;
const source = new Array(newVNodePatchCount).fill(-1); // 新旧ノード位置マッピング
let moved = false;
let pos = 0;
const keySourceMap: Record<number | string | symbol, number> = {};
for (let i = startIndex; i <= newEndIndex; i++) {
keySourceMap[vNode[i].key!] = i; // 一意のkey+配列を使用して新旧二つの木の差異を関連付けます
}
for (let i = startIndex; i <= oldEndIndex; i++) {
const sourceKey = keySourceMap[oldVNode[i].key!];
if (sourceKey !== undefined) { // 再利用可能なノードがあることを示します
patch(oldVNode[i], vNode[sourceKey], container); // パッチ操作
source[sourceKey - startIndex] = i; // 新旧ノード同keyマッピングポイント
if (sourceKey < pos) { // 新ノードツリーの中での最大インデックスを特定し、ノード移動の必要性を判断する
moved = true;
} else {
pos = sourceKey;
}
} else { // 見つからなかった場合、この旧ノードはアンマウントする必要があります
unMountElement(oldVNode[i]);
};
}
元々のO(n^2)の二重forループの時間計算量は、成功裏に分割され、時間計算量はO(n)に低下しました。しかし、keySourceMapという変数が追加されました。これは、処理時に空間を時間で交換する最適化手法です。
次に、sourceを基にして最長増加部分列を計算する必要があります。ここで、なぜ最長増加部分列が必要なのかを考えてみましょう。最長増加部分列は増加するリスト項目であり、これは最長増加部分列のノード順序が正しく、ノードを移動する必要がないことを示します。これにより、ノード移動の回数が最小限に抑えられます。これが最長増加部分列の最大の役割です。
次に、私たちは以前と同様に、高速 Diff のコード実行示意アニメーションを提供します。図 3-4をご覧ください。
図 3-4 高速 diff アルゴリズム実行フローチャート
/**
* 高速diffアルゴリズム
* @param oldVNode
* @param vNode
* @param container
*/
function fastDiff(oldVNode: VNode[], vNode: VNode[], container: ContainerElement) {
let startIndex = 0;
while(oldVNode[startIndex] && vNode[startIndex] && oldVNode[startIndex]?.key === vNode[startIndex]?.key) { // 前置ノードチェック
patch(oldVNode[startIndex], vNode[startIndex], container);
startIndex ++;
};
let oldEndIndex = oldVNode.length - 1;
let newEndIndex = vNode.length - 1;
// 前置ノードが新ノード/旧ノードのいずれかを観測完了した場合、後置ノードチェックを行う必要はありません。このチェックがなければ、予期しないレンダリング状況を引き起こすことになります。
if ((startIndex !== oldVNode.length) || (startIndex !== vNode.length)) {
while(oldVNode[oldEndIndex] && vNode[newEndIndex] && oldVNode[oldEndIndex].key === vNode[newEndIndex].key) { // 後置ノードチェック
patch(oldVNode[oldEndIndex], vNode[newEndIndex], container);
oldEndIndex--;
newEndIndex--;
};
}
if (newEndIndex >= startIndex && oldEndIndex < startIndex) { // 旧ノードがすでに排除されたが、新ノードに未排除のノードが残っていることを示します
for (let i = startIndex; i <= newEndIndex; i++) {
patch(null, vNode[i], container, vNode[newEndIndex + 1]?._element); // マウント
}
} else if (newEndIndex < startIndex && oldEndIndex >= startIndex) { // 新ノードがすでに排除されたが、旧ノードに未排除のノードが残っていることを示します
for (let i = startIndex; i <= oldEndIndex; i++) {
unMountElement(oldVNode[i]); // アンマウント
}
} else { // 新旧ノードの両方に未マウント/未アンマウントのノードが存在することを示します
// doubleEndedDiff(oldVNode.slice(startIndex, oldEndIndex + 1), vNode.slice(startIndex, newEndIndex + 1), container);
const newVNodePatchCount = newEndIndex - startIndex + 1;
const source = new Array(newVNodePatchCount).fill(-1); // 新旧ノード位置マッピング
let moved = false;
let pos = 0;
// 二重for時間計算量高い, O(n^2)
// for (let i = startIndex; i <= newEndIndex; i++) {
// for (let j = startIndex; j <= oldEndIndex; j++) {
// if (vNode[i].key === oldVNode[j].key) { // 新旧ノードマッピングポイントを見つける
// patch(oldVNode[j], vNode[i], container);
// source[i - startIndex] = j;
// if (j < pos) { // 新ノードツリーの中での最大インデックスを特定し、ノード移動の必要性を判断する
// moved = true;
// } else {
// pos = j;
// }
// break;
// }
// }
// }
// // 再利用されなかったノードをアンマウントするために旧ノードリストをループします
// oldVNode.forEach(oldElement => {
// if (!vNode.find(newElement => newElement.key === oldElement.key)) {
// unMountElement(oldElement);
// };
// });
// 空間を時間で交換し、時間計算量を低下させる、O(n)
const keySourceMap: Record<number | string | symbol, number> = {};
for (let i = startIndex; i <= newEndIndex; i++) {
keySourceMap[vNode[i].key!] = i; // 一意のkey+配列を使用して新旧二つの木の差異を関連付けます
}
for (let i = startIndex; i <= oldEndIndex; i++) {
const sourceKey = keySourceMap[oldVNode[i].key!];
if (sourceKey !== undefined) { // 再利用可能なノードがあることを示します
patch(oldVNode[i], vNode[sourceKey], container); // パッチ操作
source[sourceKey - startIndex] = i; // 新旧ノード同keyマッピングポイント
if (sourceKey < pos) { // 新ノードツリーの中での最大インデックスを特定し、ノード移動の必要性を判断する
moved = true;
} else {
pos = sourceKey;
}
} else { // 見つからなかった場合、この旧ノードはアンマウントする必要があります
unMountElement(oldVNode[i]);
};
}
if (moved) {
// 最長増加部分列を計算します
const result = getSequence(source);
let longestLastIndex = result.length - 1; // 最長増加部分列の最後のインデックス
let newLastIndex = newEndIndex - startIndex; // 新ノードリストがstartIndexを基準にした最後のインデックス値
for (let i = newLastIndex; i >= 0; i--) { // 逆方向にループ
if (source[i] === -1) { // このノードは新しいノードであることを示します
const currentVNode = vNode[i + startIndex];
patch(null, currentVNode, container, vNode[i + startIndex + 1]?._element); // 新ノードの現在の位置の次のノードをアンカーポジションとして挿入します
} else if (i !== result[longestLastIndex]) { // 最長増加部分列ではない、ノードは移動する必要があります
// ノードはすでにパッチで修正されており（element属性も同期されています）、移動ノードのみを考慮すればよいです。アンカーポジションは上記の新ノードと同様に処理します。
const currentVNode = vNode[i + startIndex];
insertElement(container, currentVNode._element, vNode[i + startIndex + 1]?._element);
} else { // 最長増加部分列に出会ったことを示します。このノードは移動する必要がなく、longestLastIndexインデックスを前方に移動させます。
longestLastIndex--;
}
}
};
}
};
参考資料#
『Vue.js の設計と実装』第七、八、九、十、十一章の内容