JavaScript のフラット配列をツリー構造に変換する例

バックグラウンドで10,000個のデータが失われた

どれだけ計画を立てても、逃れられませんでした。バックエンドは本当に一度に何万ものデータをフロントエンドに投げ込んでいました。まあ、少なくともまだ10万には達していません。以下に示すように、背景は次の構造を返します。

定数flatArr = [
  { id: '001'、名前: 'ノード 1' },
  { id: '0011'、親ID: '001'、名前: 'ノード1-1' },
  { id: '00111'、親ID: '0011'、名前: 'ノード 1-1-1' },
  { id: '002'、名前: 'ノード 2' },
]

ご覧のとおり、これは実際にはフラットな配列です。私たちの要件は、次のようなツリー構造を受け取る Element-ui のカスケード セレクターでこのようなデータをレンダリングすることです。

オプション = [
  {
    値: 'zhinan'、
    ラベル: 'ガイド'、
    子供たち： [
      {
        値: 'shejiyuanze'、
        ラベル: 「デザイン原則」、
        子供たち： [
          { 値: 'yizhi'、ラベル: 'consistent' },
          { 値: 'fankui'、ラベル: 'フィードバック'}
        ]、
      }
    ]
  }
]

ああ、これはフラット配列をツリー構造に変換する必要がある!
その作戦は虎のように獰猛で、一言も発することなく再帰が書かれていた。

再帰法

完成しました。コードは簡潔で、アイデアは明確です。実行するとどうなるでしょうか?ページが停止しています。console.time() によると、必要なツリー構造を計算するのに約 18 秒かかりました。
自分を振り返ってみました。何万ものデータがあります。親ノードの子ノードを下から上へ再帰的に検索するたびに、配列を 1 回走査する必要があり、当然時間がかかります。さらに、計算時間によってページがフリーズするのは明らかなので、この方法は絶対にお勧めできません。では、もっと良い解決策はあるのでしょうか?

非再帰的方法

ここでは、オブジェクトが参照を保存する機能を巧みに適用しています。毎回、現在のノードの ID がキーとして使用され、対応するノードの参照情報が保存されます。配列をトラバースすると、objMap の子情報が毎回更新されます。このようにして、すべてのノードとその子ノードが objMap に保持されます。最も重要なのは、配列を 1 回トラバースするだけでよく、時間の計算量は O(n) であることです。この方法を使用すると、計算時間はわずか 60 ミリ秒です。

要約する

• 再帰的方法: 現在のノードの子ノードを再帰的に検索するたびに、配列を再度走査する必要があり、時間の計算量は O(nlogn) です。
• 非再帰的方法: ルートノードから下に向かって子ノードを検索し、各ノードとその子ノードの情報をマップに保存します。子ノードはマップ上の参照を保存し、各ノードの子ノードは ID によってマップ内で見つけることができます。時間計算量は O(n) です。

比較表を見てみましょう:

データ量が増えるにつれて時間の計算量も増加するという上記の傾向から、データがどんどん大きくなると、再帰アルゴリズムによって消費される時間は非再帰アルゴリズムによって消費される時間よりもはるかに長くなることがわかります。したがって、データ量が少ない場合は再帰アルゴリズムを使用すると一定の利点がありますが、データがある程度大きくなると、再帰アプローチの欠点がますます明らかになり、非再帰アルゴリズムを使用する方がはるかに高速になります。

最後に、この比較を通じて、アルゴリズムの重要性をはっきりと感じることができると言わなければなりません。実装方法が異なると大きな違いが生じる可能性があり、すべての開発者が注目する価値があります。

JavaScript のフラット配列をツリー構造に変換する実装例については、これで終わりです。JavaScript のフラット配列をツリー構造に変換することに関するより関連性の高いコンテンツについては、123WORDPRESS.COM の以前の記事を検索するか、以下の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM をよろしくお願いいたします。