查找最相似列表的有效方法<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()查找是否包含String。这只需要 (log N) 而不是像以前那样 N/2。

Answer 2

接受的答案很好，但仍有待改进。您可以简单地使用 LinkedHashSet，这将花费 O(n) 将数据转储到集合中，并且每个包含操作的时间为 O(1)。如果您的列表很大，这会有所帮助，但对于较小的列表，请改用排序。

如果您的列表中有重复的条目，您可能会得到一些意想不到的结果，因为您的原始代码会在结果中创建多个条目。在这种情况下，使用类似 Google Guava 的 LinkedHashMultiset 的东西。如果您的类路径中没有 Guava，如果您想要 O(1) 搜索时间，您可能必须自己编写一个。

作为旁注，Collections.sort() 将更改原始列表。如果您稍后需要原始订单或列表无法修改，您应该创建它的副本，在这种情况下我认为您应该尝试使用集合，因为它们需要相同的时间来构建，并且 HashSet使用更少的时间来执行 contains

查找最相似列表的有效方法<String>

Efficient way to Find most similar List<String>

java

vector

similarity

knn