Лучший способ найти подмножество набора из группы наборов

Question

Во-первых, простите за неоднозначное название.

Предположим, у меня есть следующая группа наборов:

Группа 1

s1 = ( x1, y1 )
s2 = ( x2 )

Группа 2

m1 = ( x1, y1, y2 )
m2 = ( x1 )
m3 = ( x1 , x2 )

Для каждого из наборов в Group 1 - вызвать набор s, мне нужно найти наборы в Group 2 - назвать его m - так, чтобы m было подмножеством s.

Итак, для моего примера ответом будет:

s1 -> m2
s2 -> nothing

Пока я храню значения в std:set, но я могу изменить это при необходимости. Кроме того, наборы могут стать большими, поэтому алгоритм должен быть эффективным. Пока у меня есть подход грубой силы, который я не совсем удовлетворен.

Есть предложения?

Answer 1

Первым шагом будет сортировка группы 1 по количеству элементов (т.е. по размеру). Тогда алгоритм выглядит примерно так:

foreach std::set M in "Group 2" {
  foreach std::set S in "Group 1" and S.size()>=M.size() {  // replace with binary search
     if ( std::includes(S.begin(),S.end(),M.begin(),M.end()) )
       { /* M is a subset of S */ }
    }
  }
}

Это должно иметь временную сложность ~ O (MSR), где M - количество наборов в «Группе 2», S - количество наборов в «Группе 1», а R - размер наибольшего набора в «Группе №». 1" .

Редактировать: Мне только что пришло в голову, что было бы более эффективно использовать S.find() вместо вызова std::includes() (который повторяется последовательно), но я думаю, что это будет верно, только если M.size () намного меньше, чем S.size () - O (M + S) против O (MlogS).

Answer 2

Вы можете попробовать что-то вроде этого.Шаги:

• создать массив, содержащий все объекты в обеих группах
• преобразовать каждые s и m в битовый массив, где array (i) = 1, если набор содержит объект (i), 0 в противном случае
• m (k) является подмножеством s (j), если m (k) И s (j) = m (k)

Answer 3

Ваши наборы часто модифицируются или они доступны только для чтения / в основном?

• Если часто изменяются, std::set - это точный баланс между модификацией и производительностью сортировки.
• Еслитолько для чтения или в основном для чтения, вы можете использовать сортировку std::vector.Сортировка стоит дорого, но на самом деле дешевле, чем построение целого дерева в std::set, поэтому производительность будет лучше, если вы будете делать это достаточно редко.

Как только вы создадите отсортированные контейнеры (будь то "автоматически отсортированные "std::set или отсортированные вручную std::vector), вы можете проверить подмножество, используя std::includes.Кстати, если вам нужно найти правильных подмножеств, вы можете сравнить количество элементов впоследствии.

Answer 4

Вы не знаете, насколько грубым является ваш подход. Пока вы используете функции набора запросов в пространстве имен std ::, они могут быть настолько эффективными, насколько это возможно. Например, тестирование, если set_intersection (s1.begin (), s2.end (), m1.begin (), m1.end ()) эквивалентно m1.

Вы могли бы быть более эффективным, чем это, поскольку вам не нужна копия соответствующих элементов, просто чтобы знать, что все они появляются. Это можно сделать, скопировав код set_intersection, но изменив реализацию так, чтобы просто считать количество подходящих элементов, а не копировать их. Тогда, если количество совпадает с размером m, то у вас есть совпадение.

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