最も効果的な方法で2つのベクトルを比較する

Question

基本的に私はアプリケーションのアニメーションを記録しようとしています。私はフレームごとの録音でこれをやっています。

私は、フレーム（アニメーションのすべてのメタデータ）を記録し、前のフレームと比較します。オブジェクトのいずれかが前のフレームにない場合は、それらを保存して、あなたに知りたくないものを入れます：P

問題は時間効率です。私は半秒後にもう一度呼び出さなければならないので、半分の時間内にこの機能を完了できるようにしたい。フレームのサイズは1000-1500になります。

私はset_differenceと他の方法をチェックしました。私は十分なものではないと思います。まず、並べ替えができないメタデータがあります。ソート基準を含めても、多くの変更が必要です。 2つのベクトルをソートし、それらを比較することは計算上高価である。

今私が思いついたのは最高です。

一例に過ぎない私の実際のコード

auto itr1 = list1.begin(); 
auto itr2 = list2.begin(); 

for (i; i<total_items;i++) 
{ 
    if (*itr1 != *itr2) 
     do something 
     itr1++; itr2++; 
    } 
} 

これは私が思いついた最高のであり、その複雑さはnです。両方のリストが同じサイズであれば動作するようになりました。あなたは新しい要素が第二のリストに挿入されます場合は、その後のすべての要素が順序外となります見ることができるようにしかし、最新のリストのサイズが大きくなる場合は、すべての要素は、例えば順不同で

a a 

b b 

c c 

d z 

e d 

f e 

g f 

を取得します。計算時間をできるだけ少なくしながら、これを回避する方法を見つけることはできないようです。 助けていただければ幸いです。

Answer 1

1）ほとんどの場合、std::vectorは、プロセッサのキャッシュ使用のためにstd::listより速くなります。

2）両方の配列を並べ替えます。正しい位置に新しい要素を挿入して、 に並べ替えます。

3）バイナリ検索を使用して、vector1のvector2からの要素の存在をチェックします。

複雑さはM * log(N)である必要があります.Nは最初のベクトルの長さで、Mは2番目のベクトルの長さです。

Answer 2

次のプログラムでは、コピーと移動のコンストラクタと代入演算子が削除され、大きなオブジェクトをコピーまたは移動しないようにしています。並べ替えは、フレームごとに1回のみポインタに対して実行されるため、最小限の時間が必要です。

#include <iostream> 
#include <vector> 
#include <set> 
#include <algorithm> 
#include <iterator> 

class MyBigObject { 
public: 
    MyBigObject(char name) : name{name} {}; 
    MyBigObject(const MyBigObject&) = delete; 
    MyBigObject(MyBigObject&&) = delete; 
    MyBigObject& operator=(const MyBigObject&) = delete; 
    MyBigObject& operator=(MyBigObject&&) = delete; 

    bool operator< (const MyBigObject& rhs) const 
    { 
     return name < rhs.name; 
    } 

    char name; 
    char bigdata[100000]; 
}; 

void doSomething(const MyBigObject& object) 
{ 
    std::cout << "Working on object that was added:" << object.name << '\n'; 
} 


void calculate_frame(const std::set<MyBigObject>& objects) 
{ 
    static std::vector<const MyBigObject*> last_frame_objects; 
    std::vector<const MyBigObject*> new_frame_objects; 
    std::vector<const MyBigObject*> difference; 
    std::for_each(objects.begin(),objects.end(),[&new_frame_objects](const MyBigObject& object) {new_frame_objects.push_back(&object); }); 
    std::sort(new_frame_objects.begin(),new_frame_objects.end()); 
    std::set_difference(new_frame_objects.begin(),new_frame_objects.end(),last_frame_objects.begin(),last_frame_objects.end(), 
     std::inserter(difference,difference.begin())); 
    for (auto object_ptr : difference) { 
     doSomething(*object_ptr); 
    } 
    last_frame_objects = new_frame_objects; 
} 

int main() 
{ 
    std::set<MyBigObject> objects; 
    std::cout << "Start of frame\n"; 
    objects.emplace('a'); 
    objects.emplace('b'); 
    objects.emplace('c'); 
    calculate_frame(objects); 
    std::cout << "Start of frame\n"; 
    objects.emplace('d'); 
    objects.emplace('e'); 
    objects.emplace('f'); 
    calculate_frame(objects); 
    std::cout << "Start of frame\n"; 
    objects.erase('a'); 
    objects.erase('c'); 
    calculate_frame(objects); 
    std::cout << "Start of frame\n"; 
    objects.emplace('c'); 
    calculate_frame(objects); 
    return 0; 
} 

が生成されます

Start of frame 
Working on object that was added:a 
Working on object that was added:b 
Working on object that was added:c 
Start of frame 
Working on object that was added:d 
Working on object that was added:e 
Working on object that was added:f 
Start of frame 
Start of frame 
Working on object that was added:c