Vergleichen von zwei Vektoren auf die effektivste Weise

Question

Grundsätzlich versuche ich, die Animation einer Anwendung aufzunehmen. Ich mache das mit einer Einzelbildaufnahme.

Also was ich tue ist ich einen Frame (alle Metadaten der Animation) aufzeichnen und vergleichen Sie es mit dem vorherigen Rahmen. Wenn eines der Objekte nicht im vorherigen Frame ist, dann speichere ich sie und mache Sachen mit denen ich nicht will, dass ihr es wisst: P

Jetzt ist das Problem die Zeiteffizienz. Ich möchte diese Funktion innerhalb einer halben Sekunde erledigen können, weil sie nach einer halben Sekunde erneut aufgerufen werden muss. Die Größe der Frames wird um 1000-1500 erhalten.

Ich habe set_difference und andere Methoden überprüft und ich denke, das wird nicht genug für mich sein, weil ich zuerst Metadaten habe, die nicht sortiert werden können. Ich würde viele Änderungen vornehmen müssen und selbst wenn ich ein Sortierkriterium, das Sortieren von 2 Vektoren und dann vergleichen sie ist rechenintensiv.

Gerade jetzt das Beste, was ich mit kam, ist;

nur ein Beispiel nicht mein richtiger Code

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

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

Dies ist das beste, das ich mit kam und seiner Komplexität ist n. Jetzt funktioniert es, wenn beide Listen die gleiche Größe haben. Aber wenn die Größe der neuesten Liste steigt dann all Elemente aus, um beispielsweise bekommt

a a 

b b 

c c 

d z 

e d 

f e 

g f 

Wie Sie sehen können, wenn ein neues Element in der zweiten Liste eingefügt wird, dann wird alle Elemente nach, dass aus der Ordnung sein. Ich finde keinen Weg, um dies zu umgehen, während ich die Rechenzeit so gering wie möglich halte. Jede Hilfe wird geschätzt.

Answer 1

1) In den meisten Fällen ist std::vector schneller als std::list aufgrund der Cache-Nutzung des Prozessors.

2) Sortieren Sie beide Arrays. Fügen Sie das neue Element an der richtigen Position in ein, um die sortierte Reihenfolge beizubehalten.

3) Verwenden Sie die binäre Suche, um das Vorhandensein eines Elements von vector2 in vector1 zu überprüfen. Die Komplexität sollte sein, wobei N die Länge des ersten Vektors und M die Länge des zweiten Vektors ist.

Answer 2

Im folgenden Programm werden die Konstruktoren für Kopieren und Verschieben und die Zuweisungsoperatoren gelöscht, um sicherzustellen, dass die großen Objekte nicht kopiert oder verschoben werden. Die Sortierung erfolgt nur einmal pro Frame auf den Zeigern und sollte nur wenig Zeit in Anspruch nehmen.

#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; 
} 

Produziert:

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