Сравнение двух векторов самым эффективным способом

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

Это лучшее, что я придумал и ее сложность п. Теперь он работает, если оба списка имеют одинаковый размер. Но если размер увеличивается с последней версией списка в то все элементах выходят из строя, например

a a 

b b 

c c 

d z 

e d 

f e 

g f 

Как вы можете увидеть, если новые элементы Вставляются во втором списке, то все элементы после этого выйдут из строя. Кажется, я не могу найти способ обойти это, сохраняя вычислительное время как можно меньше. Любая помощь будет оценена по достоинству.

Answer 1

1) В большинстве случаев std::vector быстрее, чем std::list из-за использования кеша процессора.

2) Сортируйте оба массива. Вставьте новый элемент в правильное положение в . Сохраните отсортированный заказ.

3) Используйте бинарный поиск, чтобы проверить наличие элемента vector2 в векторе1.

Сложность должна быть M * log(N), где N - длина первого вектора, а M - длина второго.

Answer 2

В следующей программе операции копирования и перемещения конструкторов и операторов присваивания удаляются, чтобы гарантировать, что мы не копируем и не перемещаем большие объекты. Сортировка выполняется только по указателям один раз за кадр и требует минимального времени.

#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