Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Efficient intersection of two List<String> in Java?

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?

like image 209
Pentium10 Avatar asked Mar 08 '10 11:03

Pentium10


4 Answers

You can use retainAll method:

columnsOld.retainAll (columnsNew);
like image 115
Roman Avatar answered Oct 31 '22 12:10

Roman


Using Google's Guava library:

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 millions of operations and trillions of operations.

like image 34
Sergii Shevchyk Avatar answered Oct 31 '22 13:10

Sergii Shevchyk


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

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.

like image 19
bjornhol Avatar answered Oct 31 '22 12:10

bjornhol


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;
}
like image 9
Gigas Avatar answered Oct 31 '22 13:10

Gigas