Самый простой способ вычислить пересечение / объединение - это сделать это лениво.Это занимает постоянное количество времени и памяти.Например, чтобы объединить два набора, которые описываются некоторым точечным классификатором членства (он же PMC), вы можете сделать следующее:
def union(pmc_a, pmc_b)
return lambda x : pmc_a(x) or pmc_b(x)
Конечно, чтобы избежать таких тривиальностей, вы должны определитьобъединение и пересечение относительно типа интересующих вас наборов и типа структуры данных, которую вы хотите использовать.
Например, если наборы являются дискретными, вам следует использоватьхэш установлен, как предлагают и Марцин, и Пайтон.
Если они представляют собой непрерывные множества, образованные пересечениями, объединениями и дополнениями замкнутых полупространств (т. Е. Неф полиэдры ), то дерево BSP - лучшая структура данных, дающая вамлогические операции с линейным временем (для фиксированного размера).
С другой стороны, если они являются произвольными алгебраическими множествами (другими словами, заданными нулями системы полиномиальных уравнений), то вы застряли бы, используя алгоритм Бухбергера для вычисления Гробнера .
Наконец, для общих полуалгебраических множеств (т. Е. Множеств полиномиальных неравенств) лучшее, что вы можете сделать, это использовать Тарски-Седенберг и цилиндрическую алгебраическую декомпозицию.Эти последние методы являются несколько ненадежными и неразрешимыми в целом.
Существует, конечно, еще много типов алгоритмов, которые специализируются на различных типах множеств и их представлениях.Итак, суть в том, что для вычисления этих операций вы должны сначала описать, с какими объектами вы работаете, и как они должны быть представлены.