4

これがこの質問に対して間違ったstackexchangeWebサイトである場合は、他の場所に私を向けてください！

ノードの通常の2次元グリッドがあります。また、グリッドのノード間のエッジに関するデータを保存したいのですが、これを効率的に行う方法がわかりません。

私がすぐに思いついた3つのアイデアには両方とも短所があり、どちらが好ましいか、または実際に完全に良い方法があるかどうかはわかりません。

  1. エッジデータを2D配列に格納します。グラフノードは基本的に2次元配列を形成するため、エッジデータを通常の2次元配列に簡単に格納できます。0,0は左下のノード、1,0はその右、0,1は直接 "上記」など。

この方法の問題は、データの重複です。0,0と0,1の間のエッジに関するデータは、2つの別々の場所に保存されます。データを更新する必要があるときはいつでも、両方の場所でデータを更新する必要があります。もちろん、（半分が複製されている場合でも）潜在的に2倍のデータを保持する必要があるため、余分なメモリオーバーヘッドがあります。

  1. 「上」と「左」のエッジのみを2D配列に格納します。これは方法1の拡張であり、冗長データの保存を回避します。ただし、ノードのすべてのエッジ（x、y; x + 1、y;およびx、y-1）を収集または設定するために3回の呼び出しが必要になるため、これによりデータの取得と保存がさらに困難になります。

  2. 辞書（ポイントのタプル）を使用dictionary<<<x,y>,<x,y>>,Edge>して、グラフ内の2つのノード間のエッジに関するデータを格納および取得します。

これにより冗長性は回避されますが、ディクショナリのルックアップは配列よりも遅く、4つのエッジすべてを一度に取得することはできません（ノードを取り込んで4つのエッジを返すディクショナリは後者を解決しますが、冗長性の問題を再導入します）。私の目的では、ノードの小さなグループ間のすべての可能なエッジに主に関心があるため、すべてのノードを取得しないことは大きな問題ではありません。

現在、私は方法1に傾倒しており、冗長データを吸い上げて処理しています。エッジに関するデータを保存/取得するためのより良い方法はありますか、それともこれが得られる最良の方法ですか。

例-Edgeに色を保存する：

ここに画像の説明を入力してください

4

2 に答える 2

1

もう 1 つの方法は、エッジ オブジェクトの大きな 1D リストを作成し、それらをノードに適切にリンクすることです。たとえば、ノード クラスにはTopEdge、LeftEdge、BottomEdge、およびRightEdgeメンバーがあり、それぞれがエッジ リスト内のオブジェクトへの参照になります。

これは、最初のセットアップが少し複雑になる可能性がありますが、データの重複を回避し、ノードから適切なエッジに簡単にアクセスできるようになります。

より正式な解決策が必要な場合は、グラフ理論についても読みたいと思うかもしれません。

于 2012-12-30T04:00:41.727 に答える
1

すべてがメモリに収まり、エッジが極端にまばらではないと仮定すると、リストしたオプションの中でおそらく最高のキャッシュ パフォーマンスが得られるため、「2 次元配列に "上" と "左" のエッジのみを格納する」を選択します。

ただし、ノードのすべてのエッジ (x,y; x+1,y; および x,y-1) を収集または設定するには 3 つの呼び出しが必要になるため、データの取得と保存がさらに難しくなります。

私はあなたがこれで何を意味するのか理解できません。すべてを使いやすいインターフェイスへのクラスにカプセル化する必要があります。ノードのすべてのエッジを設定する必要がある場合は、そのためのメソッドを記述します。

于 2012-12-30T05:02:59.350 に答える