2

各要素が別の要素を指す大規模な配列内の要素のサブセットをループする必要があります (大規模なグラフでの接続コンポーネントの検出に起因する問題)。

私のアルゴは次のようになります: 1. 最初の要素を検討します。3. 新しい要素が発見されなくなるまでループする 4. 1-3 でまだ考慮されていない次の要素を考慮し、1 に戻る。考慮する要素の数は、要素の総数よりもはるかに少ないことに注意してください。

私が今見ているものについては、次のいずれかを実行できます。

//create a map of all element, init all values to 0, set to 1 when consider
map<int,int> is_set; // is_set.size() will be equal to N

また

//create a (too) large array (total size), init to 0 the elements to consider
int* is_set = (int*)malloc(total_size * sizeof(int)); // is_set length will be total_size>>N

マップ内のキーへのアクセスは O(log N) であり、配列に対してのみ定数であることは知っていますが、作成時に malloc がより多くのメモリを必要とする一方でコストがかからないかどうかはわかりませんか?

4

3 に答える 3

9

疑わしい場合は、両方の代替案のパフォーマンスを測定してください。 これが、アプリケーションにとってどのアプローチが最速かを確実に知る唯一の方法です。

とはいえ、1 回限りの大きな malloc は、一般的にそれほど高価ではありません。また、マップは O(log N) ですが、big-O は、少なくともstd::map実装に関しては、私の経験では比較的大きな定数要素を隠しています。この場合、配列アプローチの方が高速であることは驚くことではありませんが、確実に知る唯一の方法は測定することです。

マップには大きな事前メモリ割り当てはありませんが、オブジェクトの存続期間にわたって多くの小さな割り当てがあることに注意してください (新しい要素を挿入するたびに、別の割り当てが取得され、要素を削除するたびに要素、あなたは別の無料を取得します)。これらが非常に多い場合、ヒープが断片化する可能性があり、アプリケーションが同時に実行している可能性がある他の処理によっては、パフォーマンスに悪影響を与える可能性があります。

于 2012-05-03T16:46:53.777 に答える
3

インデックス付き検索がニーズに合っている場合 (通常の C スタイルの配列によって提供されるように)、おそらくstd::map適切なクラスではありません。代わりに、std::vector動的なランタイム割り当てが必要なstd::array場合、またはコレクションのサイズが固定されていて、C スタイルのポインターに代わる最速の境界安全な代替手段が必要な場合に使用することを検討してください。

詳細については、この以前の投稿を参照してください。

于 2012-05-03T17:07:19.627 に答える
1

マップ内のキーへのアクセスは O(log N) であり、配列に対してのみ定数であることは知っていますが、作成時に malloc がより多くのメモリを必要とする一方でコストがかからないかどうかはわかりませんか?

マップ内の各エントリは動的に割り当てられるため、動的割り当てが問題になると、マップ内でより大きな問題になります。データ構造に関しては、int の単純な配列ではなくビットマップを使用できます。これにより、32 ビットのアーキテクチャでは配列のサイズが 32 分の 1 に縮小さintれます。ほとんどの場合、インデックスを配列にマッピングするための追加のコストは、構造がよりコンパクトになるため、追加のメモリのコストよりもはるかに小さくなります。より少ないキャッシュ ラインに収まります。

セット内の要素の密度が小さいかどうかなど、考慮すべき点は他にもあります。エントリが非常に少ない (つまり、グラフがまばらである) 場合は、どちらのオプションでも問題ありません。最後のオプションとして、ベクトルを使用してマップを手動で実装し、pair<int,int>それらを短縮してから、二分探索を使用できます。これにより、割り当ての数が減り、ソートに余分なコストが発生し、マップよりもコンパクトな O(log N) ソリューションが提供されます。それでも、ビットマスクを使用しようとします。

于 2012-05-03T16:47:37.750 に答える