3

私は現在、都市と橋を扱う割り当てのコードを書いています。次のような尊敬される地区の都市と橋を印刷する必要があります。

//unorganized inputs from user given the # of "paths" we need
4       // the # of paths
1 2 5  // 1 = city , 2 = city, 5 = bridge length
6 7 5  // 6 = city , 7 = city, 5 = bridge length
2 3 7  // 2 = city , 3 = city, 7 = bridge length
6 9 7  // 6 = city , 9 = city, 7 = bridge length

プログラムを実行すると、次のようにソートされます。

first district
1 2 5
2 3 7

2nd district
6 7 5
6 9 7

ここで、cin を介してこれらの入力を読み取ります。1 2 5 などのすべての可能なパスを配列に格納し、プログラムで並べ替えて整理したいと考えています。問題は、ユーザーからのパスが 500,000 を超える可能性があることです。500k の動的配列を作成したいと考えています。これにより、メモリに関して深刻な問題が発生しますか?

kruskalのアルゴリズムや素集合など、これを解決する他の可能な方法を見てきました（最も役立つと思います）。ばらばらなセットのコーディングを理解するのに非常に苦労しています。もっと慣れ親しんだ方法を試してみました。

値を保存し、それらを比較および整理する場所に関するヘルプは素晴らしいでしょう。これに関する情報を読んだ場所へのリンクが役立ちます。ここ数日、たくさん読んだ。あまり役に立ちませんでした。

すべてを要約すると、私の質問は次のとおりです。

  • 500k の動的配列は、メモリに関して深刻な問題を引き起こしますか?
  • 値を保存し、パスを指定してそれらを比較および整理する場所は?
4

3 に答える 3

1

500k の動的配列は、メモリに関して深刻な問題を引き起こしますか?

それぞれが単に 3 つの int の配列であると仮定すると、問題はありません。通常、これを個別の割り当てとして行うのは、過剰であるため避けます。これは少し遅くなり、必要なブックキーピングもかなりの量のメモリを消費します。より良いアプローチがあります：

値を保存し、パスを指定してそれらを比較および整理する場所は?

これらの 3 つのフィールドを保持する構造体/クラスから始めて、そのうちの 1 つを使用しますstd::vector。これにより、すべての値が 1 つの連続した割り当てとして保存されます。比較すると、作成、検索、割り当てが非常に高速です。

于 2012-11-12T06:26:24.347 に答える
1

一般に、アプリに 2 ギガのメモリがあると仮定すると、12 バイトの 500K レコード (値に 32 ビットを使用すると仮定) は問題になりません。
データ セットのサイズを小さくしたい場合は、たとえば次のようなデータ形式を使用できます。 

struct {
   unsigned short city_a;
   unsigned short city_b; 
   char length;
}


都市セットのサイズ (都市の数) と、2 つの都市間の最大長を見てください。
また、都市のペアをインデックス化する (AB が Pair_ID になる) ことによっても、データ セットを減らすことができます。

于 2012-11-12T06:27:35.823 に答える
1

これはあなたの質問とは直接関係ないかもしれませんが、あなたが達成しようとしているのはこれだと思います - http://en.wikipedia.org/wiki/Connected_component_(graph_theory )。また、グラフを隣接行列としてモデル化する場合、500k の動的配列を割り当てる必要はありません。データを保存するには、次の形式を検討してください。

int city_map [MAX_NO_OF_CITIES][MAX_NO_OF_CITIES];

city_map[i][j] = length_of_brigde_connecting_city_i_to_j;

この方法で 500,000 エントリを格納する場合、1MB 強のメモリしか必要としません。

于 2012-11-12T06:57:11.987 に答える