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

Question

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

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

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

tshred

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

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

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

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

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