私の質問は、ヒューリスティックなO(n)アルゴリズムを実装する動機についてです。
あるツリーを別のツリーに変換するための最小数の操作を生成するというこのアルゴリズムの問題には、いくつかの一般的な解決策があります。ただし、最先端のアルゴリズムには、O(n ^ 3)のオーダーの複雑さがあります。ここで、nはツリー内の要素の数です。
これをReactで使用した場合、1000個の要素を表示するには、10億のオーダーの比較が必要になります。これは高すぎる。代わりに、Reactは2つの仮定に基づいてヒューリスティックなO(n)アルゴリズムを実装します。
- 異なるタイプの2つの要素は、異なるツリーを生成します。
- 開発者は、キープロップを使用して、さまざまなレンダリングでどの子要素が安定しているのかを示唆できます。
Reactのdiffアルゴリズムが現状のままであるのにはかなりの理由がありますが、文書化された「動機付け」は、本当の真実であるために十分に意味がありません。
まず、最適な「ツリー差分」にO(N 3)時間がかかることは確かですが、「ツリー差分」アルゴリズムは、Reactが実際に行うことの唯一の最良の代替手段ではなく、実際、reactの意志に実際には適合しません。レンダリングプロセス。これは主に、最悪の場合、reactコンポーネントをレンダリングすると、既存のコンポーネントのリストと照合する必要があるreact要素のリスト(ツリーではない)が生成されるためです。
新しい要素の子がレンダリングされる前に、新しいリストを既存のツリーと照合する必要があるため、差分が実行されるときに新しいツリーはありません。実際、diffの結果は、子を再レンダリングするかどうかを決定するために必要です。
したがって...これらのリストを照合する際に、React diffを標準の最長共通部分列アルゴリズム(O(N 2)アルゴリズム)と比較する場合があります。それはまだかなり遅いです、そしてなされるべきパフォーマンスの議論があります。LCSがReactdiffと同じくらい高速である場合、それは確実にレンダリングプロセスに位置付けられます。
しかし、LCSの種類が遅いだけでなく、正しいこともしません。Reactが新しい要素のリストを古いツリーと照合しているとき、各要素が新しいコンポーネントであるか、既存のコンポーネントへの単なる小道具の更新であるかを決定しています。LCSは要素タイプの可能な最大の一致を見つけることができますが、可能な最大の一致は必ずしも開発者が望んでいるものではありません。
したがって、LCS(または本当に要点を押したい場合はツリー差分)の問題は、それが遅いというだけでなく、遅いということであり、それが提供する答えは、開発者の意図を推測するだけです。遅いアルゴリズムは、それでも間違いを犯す場合、それだけの価値はありません。
React開発者が使用できたであろう、ほとんどの場合より正確な高速アルゴリズムは他にもたくさんありますが、問題は「それだけの価値があるか」です。一般に、答えは「いいえ」です。なぜなら、開発者の意図を推測するのに本当に良い仕事をするアルゴリズムはなく、開発者の意図を推測することは実際には必要ないからです。
開発者にとって、新しい要素を既存のコンポーネントと適切に一致させて再レンダリングする必要がないことが重要な場合、開発者はこれが当てはまることを確認する必要があります。それは非常に簡単です-彼はリストをレンダリングするときに重要な小道具を提供する必要があります。開発者は、リストをレンダリングするときにほとんど常にこれを行う必要があります。これにより、コンポーネントのマッチングが完全になり、推測に甘んじる必要がなくなります。
マッチングを明確にするために必要な場所にキープロップを配置しない場合、Reactは警告を生成します。これは、より良い差分よりもはるかに役立ちます。それが表示されたら、適切なキー小道具を追加してコンポーネントを修正する必要があります。そうすれば、マッチングは完全になり、不適切に記述されたコンポーネントでより良い仕事をすることができる他のアルゴリズムがあるかどうかは関係ありません。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加