配列対マップの性能

Question

各要素が別の要素を指している大きな配列の要素のサブセットをループする必要があります（大きなグラフの接続されたコンポーネントの検出に起因する問題）。

私のalgoは次のようになります： 1.第1要素を考慮してください。 2.次の要素を前の要素が指しているものとみなしてください。 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 

を、私はそれが配列の場合のみ一定のですが（Nを記録）マップ内のキーへのアクセスがOであることを知っているが、 mallocがより多くのメモリを必要とする一方で、作成コストがそれほど高くないかどうかはわかりません。

Answer 1

疑問がある場合は、は両方の代替品のパフォーマンスを測定します。これは、どのアプローチがアプリケーションにとって最速になるかを知る唯一の方法です。

つまり、ワンタイムの大きなmallocは一般的にひどく高価ではありません。また、マップはO（log N）ですが、big-Oは少なくとも私の経験ではstd::mapの実装では比較的大きな定数を隠しています。アレイのアプローチがこの場合より速いことに気づくことはありませんが、確かに知る唯一の方法は測定することです。

マップには大量の初期メモリ割り当てはありませんが、オブジェクトの存続期間に渡って小さな割り当てが多数あります（新しい要素を挿入するたびに別の割り当てが行われるたびに要素を削除すると、別の要素が解放されます）。これらの数が非常に多い場合は、ヒープが断片化する可能性があり、アプリケーションが同時に何をしているのかによってパフォーマンスに悪影響を与える可能性があります。

Answer 2

マップのアクセスキーはO（log N）ですが、配列に対しては定数ですが、mallocの作成にはコストがかかりませんが、さらにメモリが必要ですか？

ダイナミックアロケーションが問題である場合、マップ内の各エントリはマップ内でより大きな問題になります。データ構造体としては、int型の単純な配列ではなくビットマップを使用できます。これにより、32ビットのアーキテクチャでは32の倍数で配列のサイズが縮小されます。配列にインデックスをマッピングするための余分なコストは、ほとんどの場合、余分なメモリのコストよりもはるかに小さくなります。コンパクトで、より少ないキャッシュラインに収まることができます。

他の点として、セット内の要素の密度が小さいかどうかを検討する必要があります。エントリが非常に少ない場合（グラフが疎な場合）、どちらのオプションも問題ありません。最後のオプションとして、pair<int,int>のベクトルを使用してマップを手動で実装し、それらを短くしてバイナリ検索を使用することができます。これは割り当ての数を減らし、ソートにいくらかの追加コストがかかり、マップよりもよりコンパクトなO（log N）ソリューションを提供します。それでも、私はビットマスクのために行くことを試みるでしょう。

Answer 3

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

この詳細については、previous postをご覧ください。