Самый быстрый способ найти объединение множеств

Ответ 1

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

template<typename S>
S union_sets(const S& s1, const S& s2)
{
     S result = s1;

     result.insert(s2.cbegin(), s2.cend());

     return result;
}

Ответ 2

Предполагая, что результат тоже должен быть набором, тогда у вас нет выбора, кроме как вставить каждый элемент из каждого x_i в этот результирующий набор. Таким образом, очевидная реализация:

set<pair<int,int>> x(x1);
x.insert(x2.begin(), x2.end());
// etc

Остается вопрос, может ли это быть избито для скорости.

Одноэлементный insert принимает подсказку position, которая при правильной скорости вставки. Поэтому может получиться, что что-то вроде этого быстрее, чем x.insert(x2.begin(), x2.end());:

auto pos = x.begin()
for (auto it = x2.begin(); it != x2.end(); ++it) {
    pos = x.insert(pos, *it);
}

Однако это зависит от данных: эта позиция может быть или не быть точным. Вы можете убедиться, что это, поместив все элементы в порядок, прежде чем вы начнете, для которого лучшим инструментом, вероятно, является set_union. Это можно назвать merge_and_dedupe_sorted_ranges, потому что то, что он делает, не имеет ничего общего с std::set. Вы могли бы либо set_union в промежуточные векторы, либо в такие как:

set<pair<int,int>> x;
set_union(x1.begin(), x1.end(), x2.begin(), x2.end(), inserter(x, x.end());

Моя проблема с использованием set_union заключается в том, что для того, чтобы получить преимущество добавления элементов в набор в возрастающем порядке, вам нужно создать новый пустой контейнер каждый раз, когда вы его вызываете (потому что, если он не пуст, добавленные элементы должны чередоваться с уже имеющимися значениями). Накладные расходы этих контейнеров могут быть выше, чем накладные расходы на вставку в набор в произвольном порядке: вам придется его протестировать.

Ответ 3

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

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

Изменить: И для каждой операции объединения между двумя наборами - объединить меньшее множество в большее множество.

Ответ 4

Я предполагаю, что с быстрым вы подразумеваете быстрое выполнение.

Затем: std:: set_union (*)

Пример для двух наборов:

#include <set>
#include <algorithm>
#include <iterator>
using namespace std;

int main () {
    set<pair<int,int> > a, b, uni;
    set_union (a.begin(), a.end(),
               b.begin(), b.end(),
               inserter(uni, uni.begin()));

}

для n наборов, рукописное письмо может быть наиболее удобным для обслуживания решением:

#include <set>
#include <vector>
using namespace std;

int main () {
    vector<set<pair<int,int>>> sets;
    set<pair<int,int>> uni;

    for (const auto &s : sets)
        for (const auto &elem : s)
            uni.insert (elem);
}

хотя в целом, следует отдать предпочтение стандартным алгоритмам и получать прибыль от их качественной реализации.

Если по быстрому вы подразумеваете производительность, мы не можем помочь, поскольку у нас нет требований. Различные подходы могут дать разные результаты для разных обстоятельств.

(*) note: сайт неодобрительно полагается на то, что он не был на 100% точным и стандартным

Ответ 5

Попробуйте set_union в алгоритме заголовка.

Ответ 6

Вы можете использовать std:: set_union рекурсивно или просто вставлять все наборы в результирующий набор (дублирующиеся элементы устраняются набором). Если количество элементов очень мало, вы можете попробовать вставить все это в вектор, отсортировать его и использовать std:: unique на векторе.

Ответ 7

Чтобы сохранить выделение памяти и улучшить локальность, было бы лучше использовать одну рабочую память vector<T>.

Построить a vector<T> и зарезервировать общее количество элементов во всех s (подсчет дубликатов). Затем, начиная с пустого диапазона [v.begin(), v.begin()), расширьте его до набора (уникальный, отсортированный) диапазон, добавив содержимое каждого набора, слияния и uniquifying:

vector<T> v;
v.reserve(<total size>);
for (set<T> &s: sets) {
    auto middle = v.insert(v.end(), s.begin(), s.end());
    inplace_merge(v.begin(), middle, v.end());
    v.erase(v.unique(v.begin(), v.end()), v.end());
}