3

とという2つのvector<MyType*>オブジェクトがAありBます。MyTypeクラスにはフィールドがあり、にあるが入っていないものIDを取得したい。私は画像分析アプリケーションに取り組んでおり、高速で最適化されたソリューションを見つけたいと思っていました。MyType*AB

4

4 に答える 4

2

std::sortIDに従って両方のベクトル（）を並べ替えてから、を使用しますstd::set_difference。たとえば、これらのアルゴリズムの両方に渡すカスタムコンパレータを定義する必要があります。

struct comp
{
    bool operator()(MyType * lhs, MyType * rhs) const
    {
        return lhs->id < rhs->id;
    }
};
于 2010-06-28T18:56:58.063 に答える
2

順序付けされていないアプローチは、データが事前に（IDフィールドで）並べ替えられていない限り、通常は2次の複雑さを持ちます。この場合、データは線形であり、Bを繰り返し検索する必要はありません。

struct CompareId
{
    bool operator()(const MyType* a, const MyType* b) const
    {
        return a>ID < b->ID;
    }
};
...
sort(A.begin(), A.end(), CompareId() );
sort(B.begin(), B.end(), CompareId() );

vector<MyType*> C;
set_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(C) );

別の解決策は、StrictWeakOrderingテンプレート引数に使用されるCompareIdを使用してstd::setのような順序付けされたコンテナーを使用することです。多くの集合演算を適用する必要がある場合は、これが良いと思います。これには独自のオーバーヘッド（ツリー）がありますが、効率の問題であることが本当にわかった場合は、高速メモリアロケータを実装して、要素を超高速で挿入および削除できます（注：これは、プロファイルを作成して、ボトルネック）。

警告：やや複雑な領域に入ります。

考えられる別の解決策があります。これは、該当する場合は非常に高速であり、データの並べ替えについて心配する必要はありません。基本的に、同じIDを共有するMyTypeオブジェクトのグループには、共有カウンターを格納させます（例：unsigned intへのポインター）。

これには、カウンターへのIDのマップを作成する必要があり、MyTypeオブジェクトがそのIDに基づいて作成されるたびに、マップからカウンターをフェッチする必要があります。IDが重複しているMyTypeオブジェクトがあるため、MyTypeオブジェクトを作成するほど頻繁にマップに挿入する必要はありません（ほとんどの場合、既存のカウンターをフェッチするだけです）。

これに加えて、フェッチされるたびにインクリメントされるグローバルな「トラバーサル」カウンターがあります。

static unsigned int counter = 0;
unsigned int traversal_counter()
{
    // make this atomic for multithreaded applications and
    // needs to be modified to set all existing ID-associated
    // counters to 0 on overflow (see below)
    return ++counter;
}

ここで、MyType*を格納しているAベクトルとBベクトルがある場所に戻りましょう。BにないAの要素をフェッチするには、最初にtraversal_counter（）を呼び出します。初めて呼び出すとすると、トラバーサル値は1になります。

ここで、B内のすべてのMyType *オブジェクトを反復処理し、各オブジェクトの共有カウンターを0からトラバーサル値1に設定します。

ここで、AのすべてのMyType *オブジェクトを反復処理します。現在のトラバーサル値（1）と一致しないカウンター値を持つものは、Bに含まれていないAの要素です。

トラバーサルカウンターをオーバーフローするとどうなりますか？この場合、IDマップに格納されているすべてのカウンターを反復処理し、トラバーサルカウンター自体とともにゼロに戻します。これは、32ビットのunsigned intの場合、約40億回のトラバーサルに1回だけ発生する必要があります。

これは、特定の問題に適用できる最速のソリューションです。ソートされていないデータに対して線形の複雑さで任意の集合演算を実行できますが（常に、ハッシュテーブルのような最良のシナリオだけでなく）、ある程度の複雑さをもたらすため、本当に必要な場合にのみ検討してください。

于 2010-06-28T19:06:45.090 に答える
1

まず問題を見てください。「BではなくAのすべて」が必要です。つまり、「Aのすべて」にアクセスする必要があるということです。また、Bにあるものとないものを知るために、Bのすべてを訪問する必要があります。したがって、O(n) + O(m)解決策があるか、nとmの違いを排除するために自由をとる必要があることを示唆していO(2n)ます。

std::set_differenceアプローチを考えてみましょう。各ソートはO(n log n)、であり、set_differenceはO(n)です。したがって、sort-sort-set_differenceアプローチはO(n + 2n log n)です。それを呼びましょうO(4n)。

別のアプローチは、最初にBの要素をセット（またはマップ）に配置することです。セットを作成するためのB全体での反復は、各要素のO(n)挿入O(log n)に加えて、A（log n）の各要素のルックアップを伴うAO（n）全体での反復であり、合計は次のようになりO(2n log n)ます。O(3n)それを少し良いと呼びましょう。

最後に、unordered_set（またはunordered_map）を使用し、O(1)挿入とO(1)ルックアップの平均的なケースを取得すると仮定すると、次のようなアプローチがありO(2n)ます。A-ha！

ここでの本当の利点は、unordered_set（またはmap）が、最初にデータを表すためのおそらく最も自然な選択であるということです。つまり、適切な設計によって最適化された実装が得られます。それは常に起こるわけではありませんが、それが起こったときは素晴らしいです！

于 2010-06-28T20:29:18.123 に答える
0

BがAにすでに存在する場合、Aにデータを入力している間、Cベクトルで簿記を行うことができます。

于 2010-06-28T23:23:13.053 に答える