0

私はいくつかの数字のセットを交差させており、これを行うには、マップに数字が表示されるたびにカウントを保存します。

パフォーマンスが非常に遅いことがわかりました。

詳細：-セットの1つに150,000の数字が含まれています-そのセットと別のセットの交差には、最初は約300ミリ秒、2回目は約5000ミリ秒かかります-まだプロファイリングを行っていませんが、ブレークするたびにmalloc.cで交差を実行している間のデバッガー！

では、どうすればこのパフォーマンスを向上させることができますか？別のデータ構造に切り替えますか？マップのメモリ割り当てパフォーマンスをどのように改善しますか？

アップデート：

  1. std::mapまたはboost::unordered_mapにスペースを事前に割り当てるように依頼する方法はありますか？
  2. または、これらを効率的に使用するためのヒントはありますか？

Update2：

C＃HashSet<T>やDictionary<K、V>のようなFastC++コンテナを参照してください。

Update3：

set_intersectionのベンチマークを行い、ひどい結果が得られました。

(set_intersection) Found 313 values in the intersection, in 11345ms
(set_intersection) Found 309 values in the intersection, in 12332ms

コード：

int runIntersectionTestAlgo()
{   

    set<int> set1;
    set<int> set2;
    set<int> intersection;


    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.insert(value);
    }

    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() % 200000 + 1;
        random *= 10;

        int value = 1000000000 + random;
        set2.insert(value);
    }

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), inserter(intersection, intersection.end()));

    return intersection.size(); 
}
4

9 に答える 9

3

あなたは間違いなくはるかに速い事前に割り当てられたベクトルを使用する必要があります。stlセットとのセット交差を行う際の問題は、次の要素に移動するたびに、動的に割り当てられたポインターを追跡していることです。これは、CPUキャッシュに簡単に含めることはできません。ベクトルを使用すると、前の要素に物理的に近いため、次の要素がキャッシュに含まれることがよくあります。

ベクトルの秘訣は、このようなタスクにメモリを事前に割り当てない場合、初期化ステップ中にサイズが変更されるときにメモリの再割り当てが行われるため、さらに悪い結果が発生することです。

このインスタレーションのようなものを試してください-それははるかに速くなります。

int runIntersectionTestAlgo() { 

vector<char> vector1; vector1.reserve(100000);
vector<char> vector2; vector2.reserve(1000);

// Create 100,000 values for set1
for ( int i = 0; i < 100000; i++ )    {
    int value = 1000000000 + i;
    set1.push_back(value);
}

sort(vector1.begin(), vector1.end());

// Create 1,000 values for set2
for ( int i = 0; i < 1000; i++ )    {
    int random = rand() % 200000 + 1;
    random *= 10;
    int value = 1000000000 + random;
    set2.push_back(value);
}

sort(vector2.begin(), vector2.end());

// Reserve at most 1,000 spots for the intersection
vector<char> intersection; intersection.reserve(min(vector1.size(),vector2.size()));
set_intersection(vector1.begin(), vector1.end(),vector2.begin(), vector2.end(),back_inserter(intersection));

return intersection.size(); 
}
于 2009-06-30T14:28:48.763 に答える
1

私はそれらを分類するための提案を2番目にします。ソートされた範囲（set_intersection、set_unionなど）で動作するSTLセットアルゴリズムがすでにあります。

set_intersection

于 2009-06-29T02:28:00.630 に答える
1

あなたの問題についてこれ以上知らなくても、「良いプロファイラーに確認する」が私が与えることができる最高の一般的なアドバイスです。それ以上...

メモリ割り当てが問題になる場合は、への呼び出しを減らす、ある種のプールされたアロケータに切り替えてくださいmalloc。Boostには、と互換性のあるカスタムアロケータがいくつかありますstd::allocator<T>。実際、debug-breakサンプルが常にで終わることにすでに気付いている場合は、プロファイリングの前にこれを試すこともできますmalloc。

数値空間が密集していることがわかっている場合は、ベクトルのインデックスとして数値を使用して、 vector-またはベースの実装を使用するように切り替えることができます。bitset

数空間がほとんどスパースであるが、自然なクラスタリングがある場合（これは大きな場合）、ベクトルのマップに切り替えることができます。マップのインデックス作成には上位ビットを使用し、ベクトルのインデックス作成には下位ビットを使用します。これは、単にプールされたアロケータを使用するのと機能的に非常に似ていますが、より良いキャッシュ動作を提供する可能性があります。マシンにより多くの情報を提供しているので、これは理にかなっています（クラスタリングは、プールの割り当てから期待されるランダムな分散ではなく、明示的でキャッシュに適しています）。

于 2009-06-29T01:58:10.770 に答える
1

交差点を作るためになぜ地図を使わなければならないのか分かりません。人々が言っ​​ているように、あなたはセットをstd::set'sに入れて、それからを使うことができますstd::set_intersection()。

hash_setまたは、それらを'sに入れることができます。ただし、交差を手動で実装する必要があります。技術的には、セットの1つをに入れhash_setてから、他のセットをループして、各要素がに含まれているかどうかをテストするだけhash_setです。

于 2009-06-29T03:33:16.817 に答える
0

私は何かを理解しました。デバッガーをRELEASEビルドまたはDEBUGビルドのいずれかに接続すると（たとえば、IDEでF5キーを押すと）、ひどい時間が発生します。

于 2009-06-29T20:25:38.837 に答える
0

地図との交差が遅いので、試してみてくださいhash_map。（ただし、これはすべてのSTL実装で提供されるわけではありません。

または、両方のマップを並べ替えて、マージソートのような方法で実行します。

于 2009-06-29T02:26:38.900 に答える
0

あなたの交差アルゴリズムは何ですか？たぶん、いくつかの改善が必要ですか？

別の方法は次のとおりです

速いか遅いかはわかりませんが、試してみるのもいいかもしれません。その前に、プロファイラーを使用して、実際にホットスポットで作業していることを確認することもお勧めします。std::set<int>代わりに使用するために、交差している数字のセットを変更します。次に、見つけた各値を見て、最小のものを繰り返し処理します。最小のセットの各値について、このfindメソッドを使用して、その番号が他の各セットに存在するかどうかを確認します（パフォーマンスについては、最小から最大の順に検索します）。

これは、すべてのセットで番号が見つからない場合に最適化されるため、交差が比較的小さい場合は高速になる可能性があります。

次に、std::vector<int>代わりに交差点を保存します-を使用した挿入push_backも非常に高速です。

これが別の代替方法です

数値のセットをに変更し、std::vector<int>を使用std::sortして最小から最大に並べ替えます。次にstd::binary_search、上記とほぼ同じ方法を使用して、を使用して値を検索します。std::set配列はメモリに密に詰め込まれているため、これは検索よりも高速な場合があります。実際には、気にしないでください。その後、ロックステップで値を繰り返し処理し、同じ値を持つ値を確認できます。前のステップで見た最小値よりも小さいイテレータのみをインクリメントします（値が異なる場合）。

于 2009-06-29T01:58:10.003 に答える
0

あなたのアルゴリズムかもしれません。私が理解しているように、あなたは各セット（私が標準セットであることを望んでいます）を回転させ、それらをさらに別のマップに投げ込んでいます。標準セットのキーはすでにソートされているため、これは必要のない多くの作業を実行します。代わりに、「マージソート」のようなアプローチを取ります。最小値を見つけるために逆参照しながら、各iterをスピンオーバーします。その最小値を持つ数を数え、それらをインクリメントします。カウントがNの場合は、交差点に追加します。最初のマップが終わりに達するまで繰り返します（開始する前にサイズを比較する場合、毎回すべてのマップの終わりを確認する必要はありません）。

更新への対応： boost :: pool_allocのように、スペースを事前に予約することでメモリ割り当てを高速化する機能があります。何かのようなもの：

std::map<int, int, std::less<int>, boost::pool_allocator< std::pair<int const, int> > > m;

しかし正直なところ、mallocはそれが何をするかについてはかなり得意です。極端なことをする前にプロファイリングします。

于 2009-06-29T02:13:21.783 に答える
0

アルゴリズムを確認してから、適切なデータ型を選択してください。セットのような振る舞いをし、交差点などをやりたい場合std::setは、使用するコンテナです。

要素はソートされた方法で格納されるため、挿入にはO（log N）のコストがかかる場合がありますが、別の（ソートされた！）との交差std::setは線形時間で実行できます。

于 2009-06-29T07:51:52.383 に答える