алгоритм — Эффективное пересечение множеств коллекции множеств в Stack Overflow
У меня есть коллекция std::set, Я хочу найти пересечение всех наборов в этой коллекции, самым быстрым способом. Количество наборов в коллекции обычно очень мало (~ 5-10), а количество элементов в каждом наборе обычно меньше 1000, но иногда может доходить до 10000. Но мне нужно сделать эти пересечения десятками тысячи раз, как можно быстрее. Я попытался сравнить несколько методов следующим образом:
- Пересечение на месте в
std::setобъект, который изначально копирует первый набор. Затем для последующих наборов он перебирает все свои элементы и i-й набор коллекции и удаляет элементы из себя по мере необходимости. - С помощью
std::set_intersectionво временныйstd::set, поменяйте содержимое на текущий набор, затем снова найдите пересечение текущего набора со следующим набором и вставьте во временный набор, и так далее. - Вручную переберите все элементы всех множеств, как в 1), но используя
vectorв качестве контейнера назначения вместоstd::set, - То же, что в 4, но с использованием
std::listвместоvectorподозреваяlistобеспечит более быстрое удаление из середины. - Использование хэш-наборов (
std::unordered_set) и проверка всех предметов во всех наборах.
Как оказалось, используя vector незначительно быстрее, когда число элементов в каждом наборе мало, и list немного быстрее для больших наборов. Использование на месте set существенно медленнее, чем оба, а затем set_intersection и хэш-наборы. Существует ли более быстрый алгоритм / структура данных / приемы для достижения этой цели? Я могу опубликовать фрагменты кода, если требуется. Спасибо!
Решение
Вы можете попробовать обобщение std::set_intersection()алгоритм использует итераторы для всех множеств:
- Если какой-либо итератор достиг
end()его соответствующего набора, вы сделали. Таким образом, можно предположить, что все итераторы верны. - Возьмите значение первого итератора в качестве следующего значения кандидата
x, - Перемещение по списку итераторов и
std::find_if()первый элемент по крайней мере такой же большой, какx, - Если значение больше чем
xсделайте это новым значением кандидата и ищите снова в последовательности итераторов. - Если все итераторы имеют значение
xВы нашли элемент пересечения: запишите его, увеличьте все итераторы, начните заново.
Другие решения
Ночь — хороший советник, и я думаю, что у меня есть идея;)
- В наши дни память намного медленнее, чем центральный процессор, если все данные помещаются в кэш L1, это не составляет большого труда, но легко переносится на L2 или L3: 5 наборов из 1000 элементов — это уже 5000 элементов, то есть 5000 узлов, а набор узлов содержит по крайней мере 3 указателя + объект (то есть, по крайней мере, 16 байтов на 32-битной машине и 32 байта на 64-битной машине) => это по крайней мере 80 КБ памяти, а последние ЦП имеют только 32 КБ для L1D, поэтому мы уже разливаем в L2
- Предыдущий факт усугубляется проблемой, заключающейся в том, что множества узлов, вероятно, разбросаны по памяти и не плотно упакованы вместе, а это означает, что часть строки кэша заполнена совершенно не связанными вещами. Это может быть облегчено предоставлением распределителя, который держит узлы близко друг к другу.
- И это еще более усугубляется тем фактом, что процессоры намного лучше при последовательном чтении (где они могут предварительно выбирать память, прежде чем она вам понадобится, поэтому вы не ждете этого), а не при случайном чтении (а древовидная структура, к сожалению, приводит к довольно случайному читает)
Вот почему скорость имеет значение, vector (или возможно deque) такие замечательные структуры: они очень хорошо играют с памятью. Поэтому я определенно рекомендую использовать vector как наши посреднические структуры; хотя необходимо соблюдать осторожность, чтобы только когда-либо вставлять / удалять из конечности, чтобы избежать перемещения.
Поэтому я подумал о довольно простом подходе:
#include <cassert>
#include <algorithm>
#include <set>
#include <vector>
// Do not call this method if you have a single set...
// And the pointers better not be null either!
std::vector<int> intersect(std::vector< std::set<int> const* > const& sets) {
for (auto s: sets) { assert(s && "I said no null pointer"); }
std::vector<int> result; // only return this one, for NRVO to kick in
// 0. Check obvious cases
if (sets.empty()) { return result; }
if (sets.size() == 1) {
result.assign(sets.front()->begin(), sets.front()->end());
return result;
}// 1. Merge first two sets in the result
std::set_intersection(sets[0]->begin(), sets[0]->end(),
sets[1]->begin(), sets[1]->end(),
std::back_inserter(result));
if (sets.size() == 2) { return result; }// 2. Merge consecutive sets with result into buffer, then swap them around
// so that the "result" is always in result at the end of the loop.
std::vector<int> buffer; // outside the loop so that we reuse its memory
for (size_t i = 2; i < sets.size(); ++i) {
buffer.clear();
std::set_intersection(result.begin(), result.end(),
sets[i]->begin(), sets[i]->end(),
std::back_inserter(buffer));
swap(result, buffer);
}
return result;
}
Похоже на то правильный, Я не могу гарантировать его скорость, хотя, очевидно.