Java中两个 List<String> 的有效交集?

声明:本页面是StackOverFlow热门问题的中英对照翻译,遵循CC BY-SA 4.0协议,如果您需要使用它,必须同样遵循CC BY-SA许可,注明原文地址和作者信息,同时你必须将它归于原作者(不是我):StackOverFlow 原文地址: http://stackoverflow.com/questions/2400838/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me): StackOverFlow

提示:将鼠标放在中文语句上可以显示对应的英文。显示中英文
时间:2020-08-13 07:04:00  来源:igfitidea点击:

Efficient intersection of two List<String> in Java?

javalistintersection

提问by Pentium10

Question is simple:

问题很简单:

I have two List

我有两个列表

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

And I need to get the intersection of these. Is there a quick way to achieve this?

我需要得到这些的交集。有没有一种快速的方法来实现这一目标?

采纳答案by Roman

You can use retainAllmethod:

您可以使用retainAll方法:

columnsOld.retainAll (columnsNew);

回答by bjornhol

Since retainAll won't touch the argument collection, this would be faster:

由于 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);
}

The intersection will be the values left in columnsNew. Removing already compared values fom columnsOld will reduce the number of comparisons needed.

交集将是 columnsNew 中剩余的值。从 columnsOld 中删除已经比较的值将减少所需的比较次数。

回答by Gigas

How about

怎么样

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;
}

回答by Sergii Shevchyk

Using Google's Guavalibrary:

使用谷歌的番石榴库:

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

Note:This is much more efficient than naively doing the intersection with two lists: it's O(n+m), versus O(n×m) for the list version. With two million-item lists it's the difference between millionsof operations and trillionsof operations.

注意:这比天真地与两个列表进行交集更有效:它是 O(n+m),而列表版本的O(n×m) 。有 200 万个项目列表,这是数百万次操作和数万亿次操作之间的区别。

回答by Deutro

There is a nice way with streams which can do this in one line of code and you can two lists which are not from the same type which is not possible with the containsAll method afaik:

流有一种很好的方法可以在一行代码中完成此操作,并且您可以使用两个不同类型的列表,这在 containsAll 方法中是不可能的:

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

An example for lists with different types. If you have a realtion between foo and bar and you can get a bar-object from foo than you can modify your stream:

具有不同类型的列表的示例。如果您在 foo 和 bar 之间有一个关系,并且您可以从 foo 获取一个 bar 对象,那么您可以修改您的流:

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());

回答by Ravi Sanwal

If you put the second list in a set say HashSet. And just iterate over the first list checking for presence on the set and removing if not present, your first list will eventually have the intersection you need. It will be way faster than retainAll or contains on a list. The emphasis here is to use a set instead of list. Lookups are O(1). firstList.retainAll (new HashSet (secondList)) will also work.

如果您将第二个列表放入集合中,请说 HashSet。只需遍历第一个列表,检查集合中是否存在,如果不存在则删除,您的第一个列表最终将具有您需要的交集。它比retainAll 或包含在列表中要快得多。这里的重点是使用集合而不是列表。查找是 O(1)。firstList.retainAll (new HashSet (secondList)) 也会起作用。

回答by user_3380739

using retainAll if don't care occurrences, otherwise using N.intersection

如果不关心出现,则使用retainAll,否则使用N.intersection

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 is an utility class in AbacusUtil

N 是AbacusUtil 中的一个实用类

回答by Dheeraj Sachan

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

使用 org.apache.commons.collections4.ListUtils#intersection