Reactの設計コンセプトのキーは、全ての更新でAPIがアプリケーション全体を再描画しているかのようにするという事です。 これはアプリケーション作成を容易にしてくれますが、扱いやすさに対する大いなる挑戦でもあります。 この記事では、強力な発見的指導法(heuristics)を用いて、 我々がどのようにしてO(n³)の問題をO(n)に変えることが出来たのかを説明します。

動機付け

1つのツリーを別のものに変換する最小限処理の組み立ては、複雑でよく研究対象とされています。 The state of the art algorithms (PDFファイル)は、 nがツリー内のノード数であるとすると、おおよそO(n³)の複雑さを持ちます。

これは、1000のノードが表示されていれば、おおよそ10億の対照が必要となることを意味します。 これは我々のユースケースにとって、あまりにもコストが高過ぎます。 仮にこれを実行するとなると、現在のCPUで概ね1秒間に30億回の処理命令が必要となります。 そのため、例え最良のパフォーマンスで実装したとしても、とても1秒以内で差分計算を行うことは出来ません。

最適化アルゴリズムは扱いやすいものでは無いため、 我々は2つの想定に基づいた発見的指導法(heuristics)を用いた非最適化O(n)アルゴリズムを実装します。

1. 2つの同じクラスのコンポーネントは同様のツリーを作成し、 2つの異なるクラスのコンポーネントは異なるツリーを作成する。
2. 一意のキーが提供される要素は、異なる描画で一定に保たれる可能性がある。

実際のところ、これらの想定はあらゆるユースケースの速度向上において、驚くべき効果をもたらしてくれます。

一組に対しての賢い差分処理

ツリーの差分を取得するには、まず2つのノードの差分が取得可能である必要があります。 これには3つの異なるケースが存在します。

異なるノードの型(Type)

もしノードの型が異なる場合、Reactはそれらを2つの異なるサブツリーとして扱い、 1つ目のツリーを破棄し、2つ目のツリーを構築または挿入します。

renderA: <div />
renderB: <span />
=> [removeNode <div />], [insertNode <span />]

カスタムコンポーネントに同じロジックが使用されます。 もし、同じ型で無ければ、Reactはそれらが描画するもののマッチングを試みることすらしません。 ReactはDOMから1つ目を削除し、2つ目を挿入するだけです。

renderA: <Header />
renderB: <Content />
=> [removeNode <Header />], [insertNode <Content />]

何故Reactの差分アルゴリズムが速さと正確さを合わせ持つことが出来るのかという観点から、 この高水準の知識を持つことが非常に重要になります。 これは素早くツリーの大部分を整理し、よく似たパーツの可能性が高い部分に焦点を当てる優れた発見的指導法(heuristic)を提供します。

<Header>要素が<Content>が生成しそうなDOMを生成することは、通常は考えられないことです。 これら2つの構造をマッチさせるために時間を費やす代わりに、Reactはゼロからツリーの再構築を行うだけです。

当然ですが、もし連続する2つの描画処理で<Header>要素が同じ場所にあるのであれば、 あなたはこれらが非常に似通った構造をしていて、細かく調べる価値があると考えるでしょう。

DOMノード

2つのDOMノードを比較する際に、両方の属性を見て線形時間内にどちらが変更されたのかを決定します。

renderA: <div id="before" />
renderB: <div id="after" />
=> [replaceAttribute id "after"]

不明瞭な文字列としてstyleを取り扱う代わりに、key-valueのオブジェクトが使用されます。 これは変更されたプロパティの更新だけを行ってくれます。

renderA: <div style={{color: 'red'}} />
renderB: <div style={{fontWeight: 'bold'}} />
=> [removeStyle color], [addStyle font-weight 'bold']

属性の更新後、全ての子で再帰処理します。

カスタムコンポーネント

我々は2つのカスタムコンポーネントが同じものであると考えることにしました。 コンポーネントはステートフル(状態を保持する)であるため、新しいコンポーネントをただ使えばいいというわけにはいきません。 Reactは新しいコンポーネントから全ての属性を取得し、 前のコンポーネント上でcomponent[Will/Did]ReceiveProps()を呼び出します。

前のコンポーネントはそのまま機能します。 そのrender()メソッドが呼び出され、新しい結果と前の結果を使用して差分アルゴリズムが再起動されます。

リストに対しての賢い差分処理

問題のあるケース

子(要素)の調停をするために、Reatcはとても愚直なアプローチをします。 同時に両方の子のリストを見渡して、違いが存在すればその変化を生成します。

例えば、末尾に要素を追加した場合は次のようになります。

renderA: <div><span>first</span></div>
renderB: <div><span>first</span><span>second</span></div>
=> [insertNode <span>second</span>]

先頭への要素の挿入は難しいものになります。 Reactは両方のノードがspanであることを確認し、変化モード(mutation mode)に入ります。

renderA: <div><span>first</span></div>
renderB: <div><span>second</span><span>first</span></div>
=> [replaceAttribute textContent 'second'], [insertNode <span>first</span>]

要素のリストの変換操作を最小限にしようとするアルゴリズムは数多く存在します。 レーベンシュタイン距離(Levenshtein distance)は、 O(n²)内で単一要素の挿入・削除・置換を使用して最小限の処理を見つけることが出来ますが、 我々がレーベンシュタインを使用していたとしても、ノードが別の位置に移動していた場合は見つからず、 アルゴリズムはより酷くて複雑なことを行います。

Keys

この一見して手に負えそうにない問題を解決するために、任意の属性を導入します。 各子(要素)に対してキーを提供し、これがマッチングに使用されます。 キーを指定すれば、Reactはハッシュテーブルを使用して要素の挿入・削除・置換・移動をO(n)内で見つけることが出来ます。

renderA: <div><span key="first">first</span></div>
renderB: <div><span key="second">second</span><span key="first">first</span></div>
=> [insertNode <span>second</span>]

実際、キーを見つけることは難しいことではありません。 ほとんどの場合、あなたが表示しようとしている要素は既に一意のidを持っています。 そうではない場合、キーを生成するために新しいIDプロパティをモデルまたはコンテンツの幾つかのパーツのハッシュに追加することが出来ます。 また、そのキーはグローバル空間で一意なのでは無く、その兄弟要素の中でだけ一意であることを覚えておいて下さい。

トレードオフ

調停アルゴリズムを細部まで理解しておくことは重要なことです。 Reactはアクションの度にアプリケーション全体を再描画(re-render)し、最終的に同じ結果をもたらします。 我々は一般的なユースケースで処理速度をより上げるために、定期的に発見的指導法(heuristics)を見なおしています。

最新の実装では、兄弟要素間(siblings)の中でサブツリーが移動されたことを示すことは出来ますが、 それ以外のどこかへ移動されたことを伝える術はありません。 このアルゴリズムではサブツリーを完全に再描画します。

我々は2つの発見的指導法に依存しているため、 その背後にある前提条件が満たされない場合、パフォーマンスは低下します。

1. このアルゴリズムは、異なるコンポーネントクラスのサブツリーのマッチを行おうとしません。 もし、あなたが出力が非常に似ている2つのコンポーネントクラスが交互に表示されていることに気づいた場合、 これを同じクラスにしたいと考えるでしょう。 当然我々もこれを問題だと考えませんでした。
2. 一定のキーを(例えば、Math.random()を使用して)を提供しない場合、 そのサブツリーは各一定時間毎に再描画(re-rendered)されてしまいます。 それらにキー選択の選択肢を与えてしまうことは、自ら墓穴を掘る機会を与えてしまうようなものです。

 Back to top