stdvector — Быстрое объединение нескольких векторов в Stack Overflow

Question

stdvector — Быстрое объединение нескольких векторов в Stack Overflow

Я ищу быстрый способ создать объединение нескольких векторов в C ++.

Более конкретно: у меня есть коллекция векторов (обычно 15-20 vectors с несколькими тысячами целых чисел без знака; всегда отсортированы и уникальны, чтобы они могли быть std::set). Для каждого этапа я выбираю несколько (обычно 5-10) из них и строю объединяющий вектор. Затем я сохраняю длину вектора объединения и выбираю несколько других векторов. Это будет сделано несколько тысяч раз. В конце концов меня интересует только длина самого короткого вектора объединения.

Small example:

V1: {0, 4, 19, 40}
V2: {2, 4, 8, 9, 19}
V3: {0, 1, 2, 4, 40}
V4: {9, 10}

// The Input Vectors V1, V2 … are always sorted and unique (could also be an std::set)

Choose V1 , V3;
Union Vector = {0, 1, 2, 4, 19, 40} -> Size = 6;

Choose V1, V4;
Union Vector = {0,4, 9, 10, 19 ,40} -> Size = 6;

… and so on …

На данный момент я использую std::set_union но я уверен, что должен быть более быстрый путь.

vector< vector<uint64_t>> collection;
vector<uint64_t> chosen;

for(unsigned int i = 0; i<chosen->size(); i++) {
set_union(collection.at(choosen.at(i)).begin(),
collection.at(choosen.at(i)).end(),
unionVector.begin(),
unionVector.end(),
back_inserter(unionVectorTmp));
unionVector.swap(unionVectorTmp);
unionVectorTmp.clear();
}

Я благодарен за каждую ссылку.

РЕДАКТИРОВАТЬ 27.04.2017
Новая идея:

     unordered_set<unsigned int> unionSet;
unsigned int counter = 0;

for(const auto &sel : selection){
for(const auto &val : sel){
auto r = unionSet.insert(val);
if(r.second){
counter++;
}
}
}

0

c++set-union stdset stdvector

Решение

Другие решения

Де-факто путь в C ++ 98 set_intersection, но с C ++ 11 (или TR1) вы можете пойти на unordered_set, при условии, что начальный вектор отсортирован, у вас будет хороший алгоритм O (N).

Создайте unordered_set из вашего первого вектора
Проверьте, есть ли элементы вашего второго вектора в наборе

Что-то подобное подойдет:

std::unordered_set<int> us(std::begin(v1), std::end(v1));
auto res = std::count_if(std::begin(v2), std::end(v2), [&](int n) {return us.find(n) != std::end(us);}

0

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

Вот псевдокод:

int countUnique(const std::vector<std::vector<unsigned int>>& selection)
{
std::vector<std::vector<unsigned int>::const_iterator> iters;
for (const auto& sel : selection) {
iters.push_back(sel.begin());
}
auto atEnd = [&]() -> bool {
// check if all iterators equal end
};
int count = 0;
while (!atEnd()) {
const int min = 0; // find minimum value among iterators

for (size_t i = 0; i < iters.size(); ++i) {
if (iters[i] != selection[i].end() && *iters[i] == min) {
++iters[i];
}
}

++count;
}
return count;
}

При этом используется тот факт, что ваши входные векторы отсортированы и содержат только уникальные элементы.

Идея состоит в том, чтобы сохранить итератор в каждом выбранном векторе. Минимальное значение среди этих итераторов — наше следующее уникальное значение в векторе объединения. Затем мы увеличиваем все итераторы, значение которых равно этому минимуму. Мы повторяем это до тех пор, пока все итераторы не окажутся в конце выбранных векторов.

0

Источник

Accepted Answer

Если они отсортированы, вы можете бросить свой собственный, который O (N + M) во время выполнения. В противном случае вы можете использовать хеш-таблицу с аналогичным временем выполнения

2