Efficient intersection of two List<String> in Java?

小开

最佳答案

你可以使用 retainAll方法:

columnsOld.retainAll (columnsNew);

小开

由于 retainAll 不会触及参数集合，这样会更快:

List<String> columnsOld = DBUtils.GetColumns(db, TableName);
List<String> columnsNew = DBUtils.GetColumns(db, TableName);


for(int i = columnsNew.size() - 1; i > -1; --i){
String str = columnsNew.get(i);
if(!columnsOld.remove(str))
columnsNew.remove(str);
}

交集将是 column nsNew 中剩下的值。从 column sOld 中删除已经进行比较的值将减少所需的比较数量。

小开

怎么样

private List<String> intersect(List<String> A, List<String> B) {
List<String> rtnList = new LinkedList<>();
for(String dto : A) {
if(B.contains(dto)) {
rtnList.add(dto);
}
}
return rtnList;
}

小开

使用谷歌的 Guava库:

Sets.intersection(Sets.newHashSet(setA), Sets.newHashSet(setB))

注意: 这比天真地使用两个列表进行交叉要有效得多: 它是 O (n + m) ，而清单版本是 O (n × m)。对于两百万条目列表，它是操作的 几百万和操作的万亿之间的区别。

小开

有一种很好的方法可以在一行代码中实现这一点，而且你可以在两个不属于同一类型的列表中实现这一点，这在 contsAll 方法 afaik 中是不可能的:

columnsOld.stream().filter(c -> columnsNew.contains(c)).collect(Collectors.toList());

具有不同类型的列表的示例。如果你在 foo 和 bar 之间有一个关系，并且你可以从 foo 中得到 bar-object，那么你就可以修改你的数据流:

List<foo> fooList = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<bar> barList = new ArrayList<>(Arrays.asList(new bar(), new bar()));


fooList.stream().filter(f -> barList.contains(f.getBar()).collect(Collectors.toList());

小开

如果将第二个列表放在一个集合中，请说 HashSet。只需迭代第一个列表，检查集合中是否存在，如果不存在，则删除，第一个列表最终将具有所需的交集。它将比 retainAll 或包含在列表中快得多。这里的重点是使用集合而不是列表。查找是 O (1)。 firstList.retainAll (new HashSet (secondList)) will also work.

小开

使用 retainAll if don’t care 事件，否则使用 N 交叉

a = N.asList(12, 16, 16, 17, 19);
b = N.asList(16, 19, 107);
a.retainAll(b); // [16, 16, 19]
N.println(a);


a = N.asList(12, 16, 16, 17, 19);
b = N.asList(16, 19, 107);
a = N.intersect(a, b);
N.println(a); // [16, 19]

N 是 abacus-common中的一个实用程序类

小开

use org.apache.commons.collections4.ListUtils#intersection

小开

使用 Java8流 API(和 Java9 List.of ()) ，您可以执行以下操作:

List<Integer> list1 = List.of(1, 1, 2, 2);
List<Integer> list2 = List.of(2, 2, 3, 3);


List<Integer> intersection = list1.stream()
.filter(list2::contains)
.distinct()
.collect(Collectors.toList());