Эффективно найти пересечение переменного числа наборов строк

Question

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

В настоящее время, просто думая о своем решении, похоже, что у меня должно быть асимптотическое время выполнения Θ (n ² ).

Спасибо за любую помощь!

tshred

Редактировать: Чтобы уточнить, я действительно просто хочу знать, есть ли более быстрый способ сделать это. Быстрее чем Θ (n ² ).

Answer 1

Set.retainAll() - это способ нахождения пересечения двух множеств. Если вы используете HashSet, то преобразование ваших ArrayList s в Set s и использование retainAll() в цикле по всем из них на самом деле O (n).

Answer 2

Принятый ответ просто отлично; как обновление: начиная с Java 8 есть немного более эффективный способ найти пересечение двух Set s.

Set<String> intersection = set1.stream()
    .filter(set2::contains)
    .collect(Collectors.toSet());

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

Строго говоря, вы могли бы сделать это и до Java 8, но без Stream s код был бы немного более трудоемким.

Если оба набора значительно различаются по размеру, вы предпочли бы потоковую передачу меньшему.

Answer 3

Существует также статический метод Sets.intersection(set1, set2) в Google Guava , который возвращает неизменяемое представление о пересечении двух множеств.

Answer 4

Еще одна идея - если ваши массивы / наборы имеют разные размеры, имеет смысл начать с самых маленьких.

Answer 5

Лучшим вариантом будет использование HashSet для хранения содержимого этих списков вместо ArrayList. Если вы можете сделать это, вы можете создать временный HashSet, в который вы добавляете элементы для пересечения (используйте метод putAll (..)). Сделайте tempSet.retainAll (StoreSet) и TempSet будет содержать пересечение.

Answer 6

Вы можете использовать один HashSet. Его метод add () возвращает false, когда объект уже задан. добавление объектов из списков и подсчет отметок ложных возвращаемых значений даст вам объединение в наборе + данные для гистограммы (а объекты, у которых количество + 1 равно числу списков, являются вашим пересечением). Если вы выбрасываете счетчики в TreeSet, вы можете рано обнаружить пустое пересечение.

Answer 7

Сортируйте их (n lg n), а затем выполните бинарный поиск (lg n).