Разница между двумя векторами<MyType *> A и B

У меня два vector<MyType*> объекты называются A а также B, У класса MyType есть поле ID и я хочу получить MyType* которые находятся в A но не в B, Я работаю над приложением для анализа изображений и надеюсь найти быстрое / оптимизированное решение.

Источник

4 ответа

Решение

Неупорядоченный подход, как правило, будет иметь квадратичную сложность, если только данные не сортируются заранее (по полю вашего идентификатора), и в этом случае они будут линейными и не потребуют повторных поисков через 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) );

Другое решение - использовать упорядоченный контейнер, такой как std::set, с CompareId, который используется для аргумента шаблона StrictWeakOrdering. Я думаю, что было бы лучше, если вам нужно применить множество операций над множествами. Это имеет свои накладные расходы (будучи деревом), но если вы действительно обнаружите, что это является проблемой эффективности, вы можете реализовать быстрый распределитель памяти для вставки и удаления элементов очень быстро (примечание: делайте это только в том случае, если вы профилируете и определите, что это узкое место).

Предупреждение: попадание на несколько сложную территорию.

Существует другое решение, которое вы можете рассмотреть, которое может быть очень быстрым, если применимо, и вам никогда не придется беспокоиться о сортировке данных. По сути, в любой группе объектов MyType, имеющих один и тот же идентификатор, хранится общий счетчик (например, указатель на unsigned int).

Это потребует создания карты идентификаторов для счетчиков и извлечения счетчика из карты каждый раз, когда объект MyType создается на основе его идентификатора. Поскольку у вас есть объекты 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;
}

Теперь давайте вернемся туда, где у вас есть векторы A и B, хранящие MyType*. Чтобы получить элементы в A, которых нет в B, мы сначала вызываем traversal_counter(). Предполагая, что это первый раз, когда мы его называем, это даст нам значение обхода 1.

Теперь выполните итерацию по каждому объекту MyType* в B и установите общий счетчик для каждого объекта от 0 до значения обхода 1.

Теперь перебираем все объекты MyType* в A. Те, у которых есть значение счетчика, которое не соответствует текущему значению обхода (1), являются элементами в A, которые не содержатся в B.

Что происходит, когда вы переполняете счетчик обхода? В этом случае мы перебираем все счетчики, хранящиеся в карте ID, и устанавливаем их обратно в ноль вместе с самим счетчиком обхода. Это должно произойти только один раз примерно за 4 миллиарда обходов, если это 32-разрядное целое число без знака.

Это самое быстрое решение, которое вы можете применить к данной проблеме. Он может выполнять любую операцию набора с линейной сложностью для несортированных данных (и всегда, не только в лучших сценариях, таких как хеш-таблица), но он вносит некоторую сложность, поэтому рассматривайте ее только в том случае, если она действительно нужна.

Источник

Сортировать оба вектора (std::sort) в соответствии с ID, а затем использовать std::set_difference, Вам нужно будет определить собственный компаратор, чтобы перейти к обоим этим алгоритмам, например

struct comp
{
    bool operator()(MyType * lhs, MyType * rhs) const
    {
        return lhs->id < rhs->id;
    }
};
Источник

Сначала посмотрите на проблему. Вы хотите "все в A, а не в 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) каждого элемента с последующей итерацией по A O(n) с поиском для каждого элемента A (log n), дает в итоге: O(2n log n), Давайте назовем это O(3n), что немного лучше.

Наконец, используя unordered_set (или unordered_map) и предполагая, что мы получаем средний случай O(1) вставка и O(1) поиск, у нас есть подход, который O(2n), Ага!

Настоящая победа здесь в том, что unordered_set (или map), вероятно, является наиболее естественным выбором для представления ваших данных в первую очередь, т. Е. Правильный дизайн дает оптимизированную реализацию. Это не всегда происходит, но приятно, когда это происходит!

Источник

Если B существует до A, то при заполнении A вы можете вести учет в векторе C.

Источник
Другие вопросы по тегам