LINUX.ORG.RU
Форум — Development  

Как правильно слить/объеденить несколько множеств в одно?

 , ,


0

2

Собственно есть несколько set<char>'ов и приходится иногда проверять нахождение в одном из них определенного элемента. Сейчас мне потребовалось точно сказать, что ни в одном из них не находится некий элемент. Возник вопрос: что будет быстрее слить множества и пробежаться по одном find'ом или несколько раз пробежаться find'ом?
В любо случае хотелось бы узнать как можно разом слить несколько множеств?
Пока нагуглил такое решение для слияния для 2х множеств:

std::set_union(setA.begin(), setA.end(),
               setB.begin(), setB.end(),
               back_inserter(result));

★★★★★
← scala Parallel Collections и таинственный метод ForkJoinPool.scan, который жрёт процессорное время
Новая (возможно) концепция универсального редактора ждет критики →

Возник вопрос: что будет быстрее слить множества и пробежаться по одном find'ом или несколько раз пробежаться find'ом?

Проверка на вхождение элемента в дерево: O(log N) от количества элементов. Проверка на вхождение в N множеств по N элементов: O(N log N).

Объединение двух множеств: это N вставок. То есть O(N log N). Объединение N множеств: N вставок по N элементов. То есть O(N^2 log N).

То есть в пределе получается O(N log N) для прохода по всем множестам против O(N^2 log N) для объединения всех и прохода. Так что если искать надо часто, то лучше объединить. Если изредка, лучше не париться.

Ну и как всегда, дьявол в константах.

ilammy ★★★
()

Для однократного поиска конечно лучше не сливать, а обойти множества. А для многократного при неизменных множествах может заиметь смысл сливать. Поиск имеет сложность O(log N), поиск в эквивалентных K раздельных непересекающихся множеств - O(K * log N/K) (т.е. конечно больше). Стоимость слияния двух множеств размером N - не меньше O(N * log N).

Pavval ★★★★★
()

И вообще. Если это set<char> то это всего 256 разнообразных элементов. Можно быстро схлопнуть их std::array<bool, 256> и проверять вхождение сколько влезет со скоростью света.

ilammy ★★★
()
Ответ на: комментарий от Pavval

bitset не так просто объединяется. Это не «|» для uin64_t или char.

Но для него же определён operator|() и компания :\

ilammy ★★★
()
Ответ на: комментарий от ilammy

Блин, пора спать... Сори, у меня были какие-то куевые маны.

Pavval ★★★★★
()

Помимо того, что посоветовали выше, можешь попробовать вместо std::set заюзать std::unordered_set (или std::tr1::unordered_set, если относительно старый компилятор).

DELIRIUM ☆☆☆☆☆
()
Ответ на: комментарий от ilammy

Проверка на вхождение в N множеств по N элементов: O(N log N).

А с чего ты, собственно, взял, что количество множеств и количество элементов в этих множествах - это одно и то же N? Гораздо вероятнее, что набор множеств фиксирован или, по крайней мере, меняется слабо

Gvidon ★★★★
()

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

pathfinder ★★★★
()
Ответ на: комментарий от Gvidon

А ещё в документации должно быть написано, что set хранит данные в отсортированном виде

Кхм, действительно.

pathfinder ★★★★
()

Посмотрел я на set_union. Он очень медленно работает. Сделай лучше несколько find-ов.

pathfinder ★★★★
()

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

EugeneBas ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← scala Parallel Collections и таинственный метод ForkJoinPool.scan, который жрёт процессорное время
Development
Новая (возможно) концепция универсального редактора ждет критики →