14

私はintのペアのセットを持っています set<pair<int,int> > x1, x2, ... xn（nは2から20の間である可能性があります）。それらの集合の和集合を見つけるための最速の方法は何ですか？

申し訳ありませんが、最初に明確にしなかった場合は、パフォーマンスが速いことを意味し、メモリ割り当ては問題ではありません。

4

7 に答える 7

11

x_i結果もセットである必要があると仮定すると、それぞれのすべての要素をその結果セットに挿入する以外に選択肢はありません。したがって、明らかな実装は次のとおりです。

set<pair<int,int>> x(x1);
x.insert(x2.begin(), x2.end());
// etc

残りの問題は、これをスピードで打ち負かすことができるかどうかです。

単一要素insertはpositionヒントを取ります。これが正しければ、挿入が高速化されます。したがって、このようなものは次よりも高速であることが判明する可能性がありx.insert(x2.begin(), x2.end());ます。

auto pos = x.begin()
for (auto it = x2.begin(); it != x2.end(); ++it) {
    pos = x.insert(pos, *it);
}

ただし、データによって異なります。その位置は正確な場合とそうでない場合があります。始める前にすべての要素を整理することで、それが確実に行われるようにすることができます。これには、おそらく最良のツールがありset_unionます。merge_and_dedupe_sorted_rangesそれが行うことは特にとは何の関係もないので、それはより良い名前が付けられるかもしれませんstd::set。set_union中間ベクトルにすることも、次のようなセットにすることもできます。

set<pair<int,int>> x;
set_union(x1.begin(), x1.end(), x2.begin(), x2.end(), inserter(x, x.end());

使用に関する私の懸念set_unionは、要素を昇順でセットに追加する利点を得るには、呼び出すたびに新しい空のコンテナーを作成する必要があることです（空でない場合は、追加された要素をインターリーブする必要があるため）すでにその中にある値）。これらのコンテナのオーバーヘッドは、任意の順序でセットに挿入するオーバーヘッドよりも高くなる可能性があります。テストする必要があります。

于 2012-07-06T12:24:48.133 に答える
6

最初に最小のセットの和集合を見つけます。つまり、セットの長さでセットを並べ替え、2つの最小のセットの和集合を計算し、それらのセットを削除し、そのサイズに従って集合リストに和集合を挿入します。

2つのセットがどの程度類似している可能性が高いかを測定した場合は、最初に最も類似したセットの和集合を最初に見つけることが最善の策です。これは、重複を早期に排除するユニオン操作を優先します。

編集：そして、2つのセット間の和集合演算ごとに、小さいセットを大きいセットにマージします。

于 2012-07-06T12:27:43.290 に答える
6

残念ながら、O(N)すべての結合は両方のセットの要素の組み合わせであるため、線形ソリューションに制限されていると思います。

template<typename S>
S union_sets(const S& s1, const S& s2)
{
     S result = s1;

     result.insert(s2.cbegin(), s2.cend());

     return result;
}
于 2012-07-06T12:23:37.913 に答える
4

私はあなたが速いとあなたが実装するのが速いことを意味すると思います。

次に：std :: set_union（*）

2セットの例：

#include <set>
#include <algorithm>
#include <iterator>
using namespace std;

int main () {
    set<pair<int,int> > a, b, uni;
    set_union (a.begin(), a.end(),
               b.begin(), b.end(),
               inserter(uni, uni.begin()));

}

nセットの場合、手書きで最も保守しやすいソリューションになる可能性があります。

#include <set>
#include <vector>
using namespace std;

int main () {
    vector<set<pair<int,int>>> sets;
    set<pair<int,int>> uni;

    for (const auto &s : sets)
        for (const auto &elem : s)
            uni.insert (elem);
}

ただし、一般的には、標準的なアルゴリズムを好み、その品質の実装から利益を得る必要があります。

高速でパフォーマンスを意味する場合、要件がないため、私たちは助けることができません。アプローチが異なれば、状況によって結果が異なる可能性があります。

（*）注：サイトは、標準に対して100％正確ではないために時々眉をひそめます

于 2012-07-06T12:23:00.723 に答える
3

ヘッダーアルゴリズムでset_unionを試してください。

于 2012-07-06T12:20:47.833 に答える
3

メモリの割り当てを節約し、局所性を向上させるには、単一vector<T>のメモリを作業メモリとして使用することをお勧めします。

avector<T>を作成し、すべてのsの要素の総数を予約します（重複をカウントします）。次に、空の範囲から始めて、[v.begin(), v.begin())各セットの内容を追加し、マージして一意化することにより、セットのような（一意の、ソートされた）範囲に拡張します。

vector<T> v;
v.reserve(<total size>);
for (set<T> &s: sets) {
    auto middle = v.insert(v.end(), s.begin(), s.end());
    inplace_merge(v.begin(), middle, v.end());
    v.erase(v.unique(v.begin(), v.end()), v.end());
}
于 2012-07-06T12:38:38.587 に答える
2

std :: set_unionを再帰的に使用することも 、単にすべてのセットを結果セットに挿入することもできます（重複するアイテムはセットによって削除されます）。アイテムの数が非常に少ない場合は、すべてをベクターに挿入して並べ替え、ベクターで std::uniqueを使用してみてください。

于 2012-07-06T12:21:33.067 に答える