Compare 2 lists with different objects to find equals object attribute

Question

I'm looking for elegant and efficient way to do this in Java:

public class Object1{
   String name;
   int age;
}

public class Object2{
   String name;
   String adress;
}

List<Object1> list1;
List<Object2> list2;

I want find out for every Object1 in list1 if there is Object2 in list2 with the same name. Is there better way then I wrote below?

for (Object1 element1 : list1) {
   for (Object2 element2 : list2) {
     if (element2.name.equals(element1.name)){
       // DO MY STUFF
      }
   }
}

Depending on what // DO MY STUFF is, but generally this approach is fine. Other possibility is HashMap, or if the objects are related then inherence and equals method comparing the objects names. — Uhla
– Uhla, Commented Nov 13, 2014 at 9:41

Thomas · Accepted Answer · 2014-11-13 10:15:39Z

I'd probably use a map:

Map<String, Object1> m = new HashMap<>();
for( Object1 o1 : list1 ) {
  m.put(o1.name, o1);
}

for( Object2 o2 : list2 ) {
  Object1 o1 = m.get(o2.name);
  if( o1 != null ) {
    //do something
  }
}

If multiple objects with the same name are allowed, you could use a map that supports this, e.g. Google Guava's Multimap, or a Map<String, List<Object1>> and maintain the lists yourself.

This should reduce the complexity to O(n+m), O(n) for building the map and O(m) for checking list2. There's some constant overhead for building the map but depending on the size of those lists it might be a considerable speedup.

Update:

I did a quick benchmark of sort-first and the map approach and although the sort-first might not be highly optimized (I used Collections.sort() and then iterate over both collections simultaneously), the map approach seems to quickly get more efficient.

Here are some results from my machine:

size  sort-first  map-lookup
  100      2 ms       1 ms 
  500      5 ms       2 ms
 1000      7 ms       3 ms
 5000     20 ms       8 ms
10000     37 ms      14 ms

user4233758 · Accepted Answer · 2014-11-13 09:42:11Z

1

If you would implement a comparator on names in those classes you could, sort them. Having those lists sorted, would allow you to do binary search on them. So what you would is for each element in Object1, do a binary search in object2.

This will make your code faster, from O(n * m) complexity, to O(n * log(m)) complexity.

answered Nov 13, 2014 at 9:42

user4233758

Comments

Eran · Accepted Answer · 2014-11-13 09:50:41Z

Your current algorithm has a running time of O(n*m), for two lists of sizes n and m.

You can pre-sort the lists in O(nlog(n)+mlog(m)) time, and then iterate once on both lists to find elements having the same name (that iteration would take O(m+n)).

Therefore, if n is the size of the larger list, you can have an O(nlog(n)) algorithm instead of the O(n^2) you currently have.

The iteration step would look similar to the merge part of merge sort.

int i=0;
int j=0;
while (i<list1.size() && j<list2.size()) {
    if (list1.get(i).getName().compareTo(list2.get(j).getName())<0) {
        i++;
    } else if (list1.get(i).getName().compareTo(list2.get(j).getName())>0) {
        j++;
    } else {
        // list(i).getName() is equal to list(j).getName()
    }
}
while (i < list1.size() && list1.get(i).getName().equals(list2.get(list2.size()-1).getName()) {
    // list(i).getName() is equal to the name of the last element in list2
    i++;
}
while (j < list2.size() && list2.get(j).getName().equals(list1.get(list1.size()-1).getName()) {
    // list(j).getName() is equal to the name of the last element in list1
    j++;
}

Azodious · Accepted Answer · 2014-11-13 09:43:04Z

0

Add break after DO MY STUFF

for (Object1 element1 : list1) 
{
    for (Object2 element2 : list2) 
    {
        if (element2.name.equals(element1.name))
        {
             // DO MY STUFF
             break;
        }
    }
}

answered Nov 13, 2014 at 9:43

Azodious

13.9k1 gold badge41 silver badges75 bronze badges

1 Comment

Thomas Over a year ago

What if there are multiple elements with the same name in list2?

Collectives™ on Stack Overflow

Compare 2 lists with different objects to find equals object attribute

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related