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

Question

Аннотация Описание:

У меня есть набор строк, назовите его «активный набор», а набор наборов строк - назовите его «возможный набор».Когда новая строка добавляется в активный набор, наборы из возможного набора могут внезапно стать подмножествами активного набора, поскольку активному набору не хватало только этой строки, чтобы быть надмножеством одного из возможных.Мне нужен алгоритм, чтобы эффективно найти их, когда я добавляю новую строку в активный набор.Бонусные баллы, если та же самая структура данных позволяет мне эффективно находить, какой из этих возможных наборов признан недействительным (больше не является подмножеством), когда строка удалена из активного набора.

(Причина, по которой я сформулировал описанную ниже проблему в терминах наборов и подмножеств строк в приведенном выше резюме, заключается в том, что язык, на котором я пишу это (Io), динамически типизирован. У объектов действительно есть поле типа, ноэто строка с названием типа объекта.)

Фон:

В моем игровом движке у меня есть GameObjects , который может иметь несколько типов Представление объектов, добавленных к ним.Например, если GameObject имеет физическое присутствие, к нему может быть добавлен PhysicsRepresentation (или нет, если это не твердый объект).К нему могут быть добавлены различные виды GraphicsRepresentations, такие как эффект сетки или частицы (и у вас может быть более одного, если у вас есть несколько визуальных эффектов, прикрепленных к одному и тому же игровому объекту).

Суть этогосостоит в том, чтобы разделить подсистемы, но вы не можете полностью отделить все: например, когда GameObject имеет и PhysicsRepresentation, и GraphicsRepresentation, что-то должно создать 3-й объект, который соединяет положение GraphicsRepresentation с местоположением PhysicsRepresentation.Для этой цели, сохраняя при этом все компоненты отдельно, у меня есть Interaction объектов.Объект Interaction включает в себя сквозные знания о том, как должны взаимодействовать два системных компонента.

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

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

Ошибки:

Наборы строк не обязательно отсортированы, но я могу сохранить их отсортированными.

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

Я хочу оптимизировать это для случая как можно более быстрого добавления/ удалить представления.

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

Answer 1

Если ваши наборы действительно малы, лучшее представление - это наборы битов. Сначала вы строите карту из строк в последовательные целые числа 0..N, где N - количество различных строк. Затем вы строите свои наборы с помощью побитового ИЛИ из 1<<k в число. Это позволяет вам превратить ваши операции над множествами в побитовые операции, которые являются чрезвычайно быстрыми (пересечение - &; объединение - | и т. Д.).

Вот пример: допустим, у вас есть два набора, A={quick, brown, fox} и B={brown, lazy, dog}. Сначала вы строите карту строки в число, например:

quick - 0
brown - 1
fox   - 2
lazy  - 3
dog   - 4

Тогда ваши сеты станут A=00111b и B=11010b. Их пересечение A&B = 00010b, а их объединение A|B = 11111b. Вы знаете, что набор X является подмножеством набора Y, если X == X&Y.

Answer 2

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

Эта проблема напоминает мне об использовании правил в системе на основе правил, когда факт становится истинным,что соответствует новой строке, добавляемой в активный набор.Многие из этих систем используют http://en.wikipedia.org/wiki/Rete_algorithm. http://www.jboss.org/drools/drools-expert.html - систему с открытым исходным кодом, основанную на правилах - хотя, похоже, в наши дни вокруг нее много корпоративных систем.