Эффективный способ найти наиболее похожие списки <String>

Question

У меня есть list1<String> и другие 1000 list<String>. Мне нужно выбрать список с самыми точными значениями соответствия.

Сегодня я просматриваю каждый list<String> и сравниваю с list1, сохраняю прикрытие в каком-то отсортированном списке и в конце выбираю самый похожий список.

public static <T> List<T> intersection(List<T> list1, List<T> list2) { 
     List<T> list = new ArrayList<T>(); 

     for (T t : list1) { 
      if(list2.contains(t)) { 
       list.add(t); 
      } 
     } 

     return list; 
    } 

Эта операция, чтобы перечислить все уникальные 1000 уникальных списков, считается потерянной, если у меня есть много списков, чтобы сравнить ее.

Не могли бы вы предложить мне эффективный способ/алгоритм?

Answer 1

Ваши списки не отсортированы, поэтому любая операция contains() нуждается в поиске всего списка (или до тех пор, пока он не будет найден таким образом, чтобы N/2 в среднем).
Итак, сначала соберите (Collections.sort()) все списки, затем используйте Collections.binarySearch(), чтобы найти, содержит ли строка или нет. Это требует только (log N) вместо N/2, как и раньше.

Answer 2

Принятый андерсор хорош, но его можно улучшить. Вы можете просто использовать LinkedHashSet, который возьмет O (n), чтобы сбрасывать данные в набор, а O (1) для каждого содержит операцию. Это поможет, если ваш список большой, но для небольших, используйте сортировку.

Если у вас есть повторяющиеся записи в вашем списке, вы можете получить неожиданный результат, так как ваш исходный код создаст более одного результата. В этом случае используйте что-то вроде Google Guava LinkedHashMultiset. Если вы не используете Guava в своем пути к классу, вероятно, вам придется написать его самостоятельно, если вы хотите O (1) время поиска.

Как раз в качестве примечания стороны, Collections.sort() изменит первоначальный список. Если вам потребуется первоначальный заказ позже или список каким-то образом не поддаётся редактированию, вы должны создать его копию, и в этом случае я думаю, вы должны попробовать установить вместо этого, потому что они занимают одинаковое количество времени для сборки, а HashSet используют меньше времени для выполните команду contains