Эффективно находим пересечение переменного числа множеств строк

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

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

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

tshred

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

Ответы

Ответ 1

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

Ответ 2

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

Ответ 3

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

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

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

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

Ответ 7

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