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

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 をよろしくお願いいたします。

以下もご興味があるかもしれません:
  • Vue.js ツリー コンポーネントを削除してダブルクリックし、ブランチを追加するサンプル コード
  • Java と JS で無限ツリー構造を実装する方法 (再帰に似ています)
  • JavaScript ツリー コンポーネントは無限のツリー構造を実現します

<<:  MySQL SQL ステートメントが遅い場合の一般的な原因と解決策

>>:  VMware Workstation での VMware vSphere のセットアップ (グラフィック チュートリアル)

推薦する

Angularコンポーネントの仲介モードの詳細な説明

目次1. 仲介業者モデル2. 例1. 見積コンポーネントに購入ボタンを追加する2. 親コンポーネント...

JavaScript CollectGarbage 関数の例

まず、メモリ解放の例を見てみましょう。 <スクリプト言語="JavaScript&q...

MySQL フィールドで NOT NULL を使用する必要があるのはなぜですか?

私は最近新しい会社に入社したのですが、データベース設計にいくつか小さな問題があることに気付きました。...

JSキャンバスは描画ボードと署名ボードの機能を実現します

この記事では、お絵かきボード/サインボード機能を実現するためのJSキャンバスの具体的なコードを参考ま...

MySQL マスタースレーブレプリケーションの実践の詳細説明 - GTID ベースのレプリケーション

GTIDベースのレプリケーション導入GTID ベースのレプリケーションは、MySQL 5.6 以降に...

MySQL と接続関連のタイムアウトの詳細な概要

MySQL と接続関連のタイムアウト序文:今日、同僚から、データ量が多いときに MySQL データベ...

js の getBoundingClientRect() メソッドの詳細な説明

1. getBoundingClientRect() 分析getBoundingClientRect...

読めばわかるVueの8つのヒント

1. v-forでは常に:keyを使用するデータを操作する必要があるときにプログラムを一定かつ予測可...

シェルスクリプトを使用して CentOS7 に python3.8 環境をインストールする (推奨)

ワンクリック実行仮想マシンに Python 3.8 をインストールするには、ネットワーク アダプター...

HTML のメタタグの簡単な比較

メタ タグは、ファイル情報を定義し、検索エンジンによる検索を容易にするために Web ページ ファイ...

HTML におけるいくつかの特殊属性タグの使用法の紹介

以下の属性はブラウザとの互換性があまりありません。 1.transform:rotate(45度) ...

Linuxテキスト処理ツールの詳細な説明

1. /etc/passwdファイル内のデフォルトシェルが/sbin/nologinではないユーザー...

珍しいけれど役に立つJSテクニックをいくつか紹介します

序文プログラミング言語には通常、さまざまな隠されたトリックが含まれており、これらのトリックを上手に使...

ベスト HTML/CSS デザインおよび開発フレームワーク 15 選を紹介します

プロフェッショナルな Web デザインは複雑で時間がかかります。 HTML と CSS フレームワー...

MySQLの認証コマンドgrantの使い方

この記事の例は MySQL 5.0 以降で実行されます。ユーザー権限を付与するための MySQL コ...