0

JSON形式のDAGがあり、各ノードはエントリです。名前と2つの配列があります。1つの配列は、矢印が入ってくる他のノード用であり、別の配列は、このノードが向けられているノード用です（出て行く矢印）。

したがって、たとえば：

{ 
  'id': 'A',   
  'connected_from' : ['B','C'],  
  'connects_to' : ['D','E']
}

そして、これらのノードのコレクションがあり、それらがすべて一緒にDAGを形成します。

ノードを構造体にマップして、これらのノードを保持したいと思います。ここで、idは単なる文字列であり、配列はこの構造体のポインターのベクトルになります。 

struct node { 
    string id;  
    vector<node*> connected_from;
    vector<node*> connected_to;
}

JSONの配列でノードエントリを「id」として、そのノードを保持している正しい構造体へのポインタに変換するにはどうすればよいですか？

明らかなアプローチの1つは、キーと値のペアのマップを作成することです。ここで、key = id、value =そのidを持つ構造体へのポインターであり、ルックアップを実行しますが、より良い方法はありますか？

4

3 に答える 3

2

いいえ、提供した情報だけを考えると、これ以上の方法はありません。地図を作成する必要があります。

ただし、1文字のIDの場合、マップは、たとえば英語のアルファベットの26エントリを含む単純な配列の形式をとることができます。

于 2012-08-02T02:20:48.160 に答える
1

あなたの提案は結構だと思います... IDからノードにマップします。シンプルで直感的で、実用的な目的には十分高速です。データが JSON から解析されることを考えると、ストレージとルックアップがパフォーマンスに大きな影響を与えることはありません。本当に心配なら、辞書を実装してマップを置き換えてください。

一般論として、私は常に、仕事を成し遂げる最も単純でクリーンなアプローチを提唱しています。コードの実際のボトルネックは別の場所にあるのに、アルゴリズムのメモリやパフォーマンスの影響に頭を悩ませている人が多すぎます。

于 2012-08-02T02:34:03.887 に答える
1

すべてのノードを保持するコンテナ オブジェクトが存在します (そうしないと、ノードがリークします)。いつでもコンテナをスキャンしてノードを見つけることができます。しかし、これは非効率的です - O(N^2) マップルックアップは O(N log N ) になります。

ただし、オブジェクトをコンテナーにソートされた順序で格納する (またはソートされたコンテナーを使用する) 場合、両方のケースを O(N log N) に減らすことができます。

ただし、定数は異なるため、小さなグラフの場合はスキャンが高速になる場合があります。

于 2012-08-02T02:24:18.640 に答える