Эффективный подход для расчета взаимодействия или объединения двух множеств - PullRequest
2 голосов
/ 27 июня 2011

У меня есть два массива, каждый из которых хранит набор элементов.Я хотел бы получить и вывести пересечение этих двух наборов.Есть ли эффективный и элегантный способ добиться этого?Как насчет союза?

Ответы [ 4 ]

5 голосов
/ 27 июня 2011
HashSet s0 = new HashSet(arraylist0);
s0.retainAll(arraylist1);
System.out.println("Intersection: " + s0);

s0 = new HashSet(arraylist0);
s0.addAll(arraylist1);
System.out.println("Union: " + s0);
1 голос
/ 27 июня 2011

Самый простой способ вычислить пересечение / объединение - это сделать это лениво.Это занимает постоянное количество времени и памяти.Например, чтобы объединить два набора, которые описываются некоторым точечным классификатором членства (он же PMC), вы можете сделать следующее:

def union(pmc_a, pmc_b)
    return lambda x : pmc_a(x) or pmc_b(x)

Конечно, чтобы избежать таких тривиальностей, вы должны определитьобъединение и пересечение относительно типа интересующих вас наборов и типа структуры данных, которую вы хотите использовать.

  1. Например, если наборы являются дискретными, вам следует использоватьхэш установлен, как предлагают и Марцин, и Пайтон.

  2. Если они представляют собой непрерывные множества, образованные пересечениями, объединениями и дополнениями замкнутых полупространств (т. Е. Неф полиэдры ), то дерево BSP - лучшая структура данных, дающая вамлогические операции с линейным временем (для фиксированного размера).

  3. С другой стороны, если они являются произвольными алгебраическими множествами (другими словами, заданными нулями системы полиномиальных уравнений), то вы застряли бы, используя алгоритм Бухбергера для вычисления Гробнера .

  4. Наконец, для общих полуалгебраических множеств (т. Е. Множеств полиномиальных неравенств) лучшее, что вы можете сделать, это использовать Тарски-Седенберг и цилиндрическую алгебраическую декомпозицию.Эти последние методы являются несколько ненадежными и неразрешимыми в целом.

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

1 голос
/ 27 июня 2011

Если данные логически представляют собой набор, они должны храниться в Set, таком как HashSet, а не List.Если вы не возражаете против создания нового набора копий и / или изменения одного из существующих наборов, можно использовать addAll и retainAll, чтобы получить объединение / пересечение.

Другой вариант - использовать Guava 's Устанавливает класс для создания представлений объединения, пересечения и т. Д. Из двух наборов:

Set<Foo> union = Sets.union(firstSet, secondSet);

Такие виды очень эффективны для создания (постоянное время) и выполнять большинство операций (в частности, contains), но, возможно, придется перебирать элементы для других операций, таких как size.Они также отражают состояние своих входных наборов, даже если эти наборы изменены после создания.

0 голосов
/ 27 июня 2011

Объединение: добавьте их в хэш-набор.

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...