2つのベクトル aとbの違い

StackOverflow https://stackoverflow.com/questions/3135261

  •  01-10-2019
  •  | 
  •  

質問

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

役に立ちましたか？

解決

データが事前に（IDフィールドによって）ソートされない限り、通常、順序付けられていないアプローチには二次的な複雑さがあります。その場合、それは線形であり、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テンプレート引数に使用される比較で設定されたstd :: setのような順序付きコンテナを使用することです。多くのセット操作を適用する必要がある場合、これはより良いと思います。それには独自のオーバーヘッドがあります（木である）が、それが本当に効率の問題であることがわかった場合は、高速メモリアロケーターを実装して要素を非常に高速に挿入して削除することができます（注：プロファイルしてこれを決定し、これを決定した場合にのみ行うことができます。ボトルネック）。

警告：やや複雑な領域に入る。

該当する場合は非常に高速なものを考慮することができる別のソリューションがあり、データのソートを心配する必要はありません。基本的に、同じIDストアを共有するカウンター（Ex：unsigned intへのポインター）を共有するmyTypeオブジェクトのグループを作成します。

これには、カウンターにIDのマップを作成する必要があり、IDに基づいてmyTypeオブジェクトが作成されるたびにマップからカウンターを取得する必要があります。 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ビットの符号なしのINTである場合、約40億のトラバーサルで1回だけ発生する必要があります。

これは、指定された問題に適用できる最速のソリューションについてです。非セットデータの線形複雑さで任意の操作を行うことができます（常に、ハッシュテーブルのようなベストケースシナリオだけでなく）。

他のヒント

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

struct comp
{
    bool operator()(MyType * lhs, MyType * rhs) const
    {
        return lhs->id < rhs->id;
    }
};

まず問題を見てください。あなたは「bではないすべてのもの」が欲しいです。つまり、「すべて」に訪問しなければならないということです。また、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) 各要素の続いて、AO（n）を横切る反復が続き、（log n）の各要素を検索して、合計を示します。 O(2n log n). 。それを呼びましょう O(3n), 、それは少し良いです。

最後に、UNORDERED_SET（またはUNORDERED_MAP）を使用し、平均的なケースが得られると仮定すると O(1) 挿入と O(1) ルックアップ、私たちにはアプローチがあります O(2n). 。 a-ha！

ここでの本当の勝利は、unordered_set（またはマップ）が おそらく そもそもデータを表現するための最も自然な選択、つまり適切な設計により、最適化された実装が得られます。それは常に起こるとは限りませんが、それがそうするときはいいことです！

bがAに既存の場合は、Aの居住中に、cベクターで簿記をすることができます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top