10

のコレクションを持っていstd::setます。このコレクション内のすべてのセットの交点を最速の方法で見つけたいと考えています。通常、コレクション内のセットの数は非常に少なく (~5 ～ 10)、各セット内の要素の数は通常 1000 未満ですが、10000 程度になることもあります。何千回も、可能な限り速く。次のように、いくつかの方法のベンチマークを試みました。

  1. std::set最初に最初のセットをコピーするオブジェクトのインプレース交差。次に、後続のセットについて、それ自体のすべての要素とコレクションの i 番目のセットを反復処理し、必要に応じてそれ自体からアイテムを削除します。
  2. std::set_intersectionを一時的に使用して、std::setコンテンツを現在のセットにスワップし、現在のセットと次のセットの共通点を再度見つけて、一時セットに挿入します。
  3. 1) のように、すべてのセットのすべての要素を手動で繰り返しますが、 のvector代わりに を宛先コンテナーとして使用しstd::setます。
  4. 4 と同じですが、 a のstd::list代わりに avectorを使用しlistます。
  5. ハッシュ セット ( std::unordered_set) を使用し、すべてのセット内のすべてのアイテムをチェックします。

vector結局のところ、各セットの要素数が少ない場合はa を使用するとわずかに速くlistなり、大きなセットの場合はわずかに速くなります。インプレース使用は、ハッシュ セットsetが続く両方よりも大幅に遅くなります。set_intersectionこれを達成するためのより高速なアルゴリズム/データ構造/トリックはありますか? 必要に応じてコード スニペットを投稿できます。ありがとう！

4

2 に答える 2

10

の一般化を試してみてくださいstd::set_intersection(): アルゴリズムは、すべてのセットにイテレータを使用することです:

  1. いずれかのイテレータがend()対応するセットの に到達した場合、作業は完了です。したがって、すべての反復子が有効であると想定できます。
  2. 最初の反復子の値を次の候補値として取得しますx。
  3. イテレータのリストとstd::find_if()、少なくとも と同じ大きさの最初の要素を移動しますx。
  4. 値がそれよりも大きい場合x、それを新しい候補値にして、反復子のシーケンスで再度検索します。
  5. すべての反復子が値にあるx場合は、共通部分の要素が見つかりました。それを記録し、すべての反復子をインクリメントして、最初からやり直してください。
于 2012-10-13T19:16:45.527 に答える
5

夜は良きアドバイザーであり、アイデアがあるかもしれないと思います ;)

  • 最近では、すべてのデータが L1 キャッシュに収まる場合、メモリは CPU よりもはるかに遅くなりますが、L2 または L3 に簡単にあふれてしまいます。少なくとも 3 つのポインター + オブジェクト (つまり、32 ビット マシンでは少なくとも 16 バイト、64 ビット マシンでは 32 バイト) => 少なくとも 80k のメモリであり、最近の CPU は L1D 用に 32k しかないため、すでにあふれています。 L2に
  • 前の事実は、セット ノードがおそらくメモリ内に散らばっており、密集していないという問題によって悪化しています。つまり、キャッシュ ラインの一部がまったく無関係なもので満たされていることを意味します。これは、ノードを互いに近くに保つアロケーターを提供することで軽減できます。
  • そしてこれは、CPU がランダム読み取りよりもシーケンシャル読み取り (メモリが必要になる前にプリフェッチできるため、それを待つ必要がない) の方がはるかに優れているという事実によってさらに悪化します (残念ながら、ツリー構造は非常にランダムな読み取りにつながります)。読む）

これが、速度が重要な場合、 a vector(またはおそらく a deque) が非常に優れた構造である理由です。それらはメモリで非常にうまく機能します。vectorそのため、中間構造として使用することを強くお勧めします。ただし、再配置を避けるために、末端からの挿入/削除のみに注意する必要があります。

そこで、かなり単純なアプローチを考えました：

#include <cassert>

#include <algorithm>
#include <set>
#include <vector>

// Do not call this method if you have a single set...
// And the pointers better not be null either!
std::vector<int> intersect(std::vector< std::set<int> const* > const& sets) {
    for (auto s: sets) { assert(s && "I said no null pointer"); }

    std::vector<int> result; // only return this one, for NRVO to kick in

    // 0. Check obvious cases
    if (sets.empty()) { return result; }

    if (sets.size() == 1) {
        result.assign(sets.front()->begin(), sets.front()->end());
        return result;
    }


    // 1. Merge first two sets in the result
    std::set_intersection(sets[0]->begin(), sets[0]->end(),
                          sets[1]->begin(), sets[1]->end(),
                          std::back_inserter(result));

    if (sets.size() == 2) { return result; }


    // 2. Merge consecutive sets with result into buffer, then swap them around
    //    so that the "result" is always in result at the end of the loop.

    std::vector<int> buffer; // outside the loop so that we reuse its memory

    for (size_t i = 2; i < sets.size(); ++i) {
        buffer.clear();

        std::set_intersection(result.begin(), result.end(),
                              sets[i]->begin(), sets[i]->end(),
                              std::back_inserter(buffer));

        swap(result, buffer);
    }

    return result;
}

正しいようですが、明らかにその速度は保証できません。

于 2012-10-14T12:12:43.363 に答える