Эффективно находя пересечение переменного количества наборов строк
У меня есть переменное число ArrayList, из которого я должен найти пересечение. Реалистическое ограничение на количестве наборов строк - вероятно, приблизительно 35, но могло быть больше. Я не хочу кода, просто идеи о том, что могло быть эффективным. У меня есть реализация, которую я собираюсь начать кодировать, но хотеть услышать некоторые другие идеи.
В настоящее время, просто думая о моем решении, похоже, что у меня должно быть асимптотическое время выполнения Θ (n2).
Спасибо за любую справку!
tshred
Править: Для разъяснения я действительно просто хочу знать, там более быстрый способ сделать это. Быстрее, чем Θ (n2).
5 ответов
Set.retainAll () - это способ нахождения пересечения двух множеств. Если вы используете HashSet , то преобразование ваших ArrayList s в Set s и использование keepAll () в цикле по всем из них будет на самом деле O (n).
Еще одна идея - если ваши массивы / наборы имеют разные размеры, имеет смысл начать с самого маленького.
Вы можете использовать один HashSet. Его метод add () возвращает false, когда объект уже находится в наборе. добавление объектов из списков и отметка счетчиков ложных возвращаемых значений даст вам объединение в наборе + данные для гистограммы (а объекты, у которых счетчик + 1 равен счетчику списка, являются вашим пересечением). Если вы перебросите счетчики в TreeSet, вы сможете обнаружить пустое пересечение раньше.
Лучшим вариантом было бы использовать HashSet для хранения содержимого этих списков вместо ArrayList. Если вы можете это сделать, вы можете создать временный HashSet, в который вы добавляете элементы, которые будут пересекаться (используйте метод putAll (..)). Сделайте tempSet.retainAll (storedSet) и tempSet будет содержать пересечение.
Отсортируйте их (n lg n), а затем выполните двоичный поиск (lg n).