Diff（差分）

一、はじめに#

Vueと同様に、ReactはVirtual DOMの概念を導入することで、無効なDom操作を大幅に減らし、ページの構築効率を大幅に向上させます。

そして、diffアルゴリズムは、新しいVirtual DOMと古いVirtual DOMを比較して、実際のDomの変更箇所を見つけるための効率的な方法です。

従来のdiffアルゴリズムは、ノードを再帰的に比較するため、効率が低く、アルゴリズムの計算量は O (n^3) に達します。Reactはこのアルゴリズムを最適化し、計算量を O (n) にしました。両者の効率の違いは以下の図の通りです：

二、原理#

Reactのdiffアルゴリズムは、主に 3 つのレベルの戦略に従います：

ツリーレベル
コンポーネントレベル
要素レベル

ツリーレベル#

ノードの異なるレベル間の操作は最適化されず、同じレベルのノードのみが比較されます。

削除や作成の操作のみがあり、移動の操作はありません。以下の図のようになります：

Reactは、新しいツリーで R ノードの下に A がなくなったことを検出し、A を直接削除し、D ノードの下に A とその下位ノードを作成します。

上記の操作では、削除と作成の操作のみが行われます。

コンポーネントレベル#

同じクラスのコンポーネントの場合、再帰的にdiff演算が行われます。異なるクラスのコンポーネントの場合、そのコンポーネントのすべての子ノードが直接削除され、新しいものが作成されます。

component Dをcomponent Gに変更した場合、両者の構造が非常に似ていても、Dを削除してからGを再作成します。

要素レベル#

同じレベルのノードを比較する場合、各ノードには一意のkeyが識別子として使用されます。

3 つのノード操作が提供されています：INSERT_MARKUP（挿入）、MOVE_EXISTING（移動）、REMOVE_NODE（削除）

以下のシナリオ：

keyを使用することで、新しいコレクションと古いコレクションのノードが正確に同じノードであることがわかるため、ノードの削除や作成は必要ありません。古いコレクションのノードの位置を新しいコレクションのノードの位置に移動するだけで済みます。

プロセスは次の表のようになります：

index：新しいコレクションの反復インデックス。
oldIndex：古いコレクション内の現在のノードのインデックス
maxIndex：新しいコレクションでアクセスされたノードの中で、古いコレクションの最大インデックス

現在のノードの位置が新しいコレクションの位置よりも前の場合、後続のノード操作には影響しません。この場合、ノードは移動しません。

操作中には、oldIndex と maxIndex の比較のみが行われ、次のルールに従います：

oldIndex > maxIndex の場合、oldIndex の値を maxIndex に代入します。
oldIndex = maxIndex の場合、操作は行われません。
oldIndex < maxIndex の場合、現在のノードを index の位置に移動します。

diffのプロセスは次のようになります：

ノード B：この時点で maxIndex=0、oldIndex=1。maxIndex <oldIndex が満たされるため、B ノードは移動しません。この時点で maxIndex = Math.max (oldIndex, maxIndex) は 1 です。
ノード A：この時点で maxIndex=1、oldIndex=0。maxIndex <oldIndex が満たされないため、A ノードは移動します。この時点で maxIndex = Math.max (oldIndex, maxIndex) は 1 です。
ノード D：この時点で maxIndex=1、oldIndex=3。maxIndex <oldIndex が満たされるため、D ノードは移動しません。この時点で maxIndex = Math.max (oldIndex, maxIndex) は 3 です。
ノード C：この時点で maxIndex=3、oldIndex=2。maxIndex < oldIndex が満たされないため、C ノードは移動します。これで比較が完了しました。

ABCD ノードの比較が完了した後、diffプロセスはまだ終わっていません。古いコレクションのノード全体を反復処理し、使用されていないノードがあれば削除します。

三、注意事項#

単純なリストのレンダリングの場合、keyを使用しない方が使用するよりもパフォーマンスが良いです。例えば：

[1,2,3,4,5] を以下のようにレンダリングする場合：

<div>1</div>
<div>2</div>
<div>3</div>
<div>4</div>
<div>5</div>

後で [1,3,2,5,4] に変更する場合、keyの有無による効果は次のようになります：

1. keyを使用する場合
<div key='1'>1</div>             <div key='1'>1</div>     
<div key='2'>2</div>             <div key='3'>3</div>  
<div key='3'>3</div>  ========>  <div key='2'>2</div>  
<div key='4'>4</div>             <div key='5'>5</div>  
<div key='5'>5</div>             <div key='4'>4</div>  
操作：ノード2をインデックス2の位置に移動し、ノード4をインデックス4の位置に移動します。

2. keyを使用しない場合
<div>1</div>             <div>1</div>     
<div>2</div>             <div>3</div>  
<div>3</div>  ========>  <div>2</div>  
<div>4</div>             <div>5</div>  
<div>5</div>             <div>4</div>  
操作：1番目から5番目のノードのinnerTextを変更します。

このコレクションに対して追加や削除の操作を行う場合、[1,3,2,5,6] に変更する場合：

1. keyを使用する場合
<div key='1'>1</div>             <div key='1'>1</div>     
<div key='2'>2</div>             <div key='3'>3</div>  
<div key='3'>3</div>  ========>  <div key='2'>2</div>  
<div key='4'>4</div>             <div key='5'>5</div>  
<div key='5'>5</div>             <div key='6'>6</div>  
操作：ノード2をインデックス2の位置に移動し、新しいノード6をインデックス4の位置に追加し、ノード4を削除します。

2. keyを使用しない場合
<div>1</div>             <div>1</div>     
<div>2</div>             <div>3</div>  
<div>3</div>  ========>  <div>2</div>  
<div>4</div>             <div>5</div>  
<div>5</div>             <div>6</div> 
操作：1番目から5番目のノードのinnerTextを変更します。

domノードの移動操作はコストが高いため、keyがない場合の方がパフォーマンスが良いです。