In Java what is the quickest way to check if list contains items from another list, both list are of same type?

Question

Say I have class called MyClass as follow:

public class MyClass
{
     //Identifier is alpha-numeric. If the identifier starts will 'ZZ'
     //is special special identifier.
     private String identifier = null;
     //Date string format YYYY-MM-DD
     private String dateString = null;
     //Just a flag (not important for this scenario)
     private boolean isCoolCat = false;
     //Default Constructor and getters/setters implemented
     //Overrides the standard Java equals() method.
     //This way, when ArrayList calls contains() for MyClass objects
     //it will only check the Date (for ZZ identifier) 
     //and identifier values against each other instead of
     //also comparing the isCoolCat indicator value.
     @Override
     public boolean equals(Object obj)
     {
          if(this == obj)
          {
               return true;
          }
          if(obj == null)
          {
               return false;
          }
          if(getClass() != obj.getClass())
          {
               return false;
          }
          MyClass other = (MyClass) obj;
          if(this.identifier == null)
          {
               if(other.identifier != null)
               {
                    return false;
               }
          } else if(!this.identifier.equals(other.identifier)) {
               return false;
          }
          if(other.identifier.startsWith("ZZ"))
          {
               if(!this.dateString.equals(other.dateString))
               {
                    return false;
               }
          }
          return true;
     }
}

In another class I have two List of MyClass type, each contain 100,000 objects. I need to check if items in one list are in the other list and I currently accomplish this as follow:

`

List<MyClass> inList = new ArrayList<MyClass>();
List<MyClass> outList = new ArrayList<MyClass>();
inList = someMethodForIn();
outList = someMethodForOut();
//For loop iterates through inList and check if outList contains
//MyClass object from inList if it doesn't then it adds it.
for(MyClass inObj : inList)
{
     if(!outList.contains(inObj))
     {
          outList.add(inObj); 
     }
}

My question is: Is this the fastest way to accomplish this? If not can you please show me a better implementation that will give me a performance boost? The list size is not always going to be 100,000. Currently on my platform it takes about 2 minutes for 100,000 size. Say it can vary from 1 to 1,000,000.

[`List#retainAll(Collection)`](http://docs.oracle.com/javase/7/docs/api/java/util/List.html#retainAll(java.util.Collection)), should return a `List` of all the elements which are the same between the lists. Fastest, maybe not, simplest, probably (don't forget, you'll want to make a copy of the original `List` first ;)) — MadProgrammer, Aug 06 '15 at 03:16
@MadProgrammer I am not certain if that would be any faster either. Also requires more memory because now I have to duplicate the list which can contain 1,000,000 objects. In addition, retainAll will return a List of all the elements which are the same between the two lists. But how would that help me determine which objects inList are not in outList and how would I add them to outList? This approach wouldn't be faster in my opinion. — PAujla, Aug 06 '15 at 03:24
Well, if you used a `LinkedList`, the memory would be such an issue, as you are only maintaining references to the objects, not new copies ;). `inList.retainAll(outList)` will return you a `List` which contains all the objects from `inList` which are in `outList`, use `outList.retainAll(inList)` for the reverse. Of course, you could also use `removeAll`, which will leave you a `List` on non-matching entities ;) — MadProgrammer, Aug 06 '15 at 03:26
@MadProgrammer from a design perspective this is my favorite answer. In code this will be well tested and understandable. — Pumphouse, Aug 06 '15 at 03:36

score 4 · Accepted Answer · edited May 23 '17 at 12:06

4

You want to use a Set for this. Set has a contains method which can determine if an object is in the set in O(1) time.

A couple things to watch out for when converting from List<MyClass> to Set<MyClass>:

You will lose the ordering of the elements
You will lose the duplicate elements
Your MyClass needs to implement hashcode() and equals(), and they should be consistent.

To convert your List to Set you can just use:

Set<MyObject> s1 = new HashSet<>(inList);
Set<MyObject> s2 = new HashSet<>(outList);

This Java doc explains how to find the union, intersection, and difference of two sets. In particular, it seems like you're interested in the Union:

// transforms s2 into the union of s1 and s2. (The union of two sets 
// is the set containing all of the elements contained in either set.)
s2.addAll(s1)

edited May 23 '17 at 12:06

Community

1
1

answered Aug 06 '15 at 03:32

bcorso

45,608
10
63
75

Thanks! I am **not** looking for an intersection. I need to check if the MyClass object in inList exists (ignoring the value of isCoolCat variable) in outList and if it doesn't then I need to add the object to outList. Your 1 and 2 do not effect me as ordering is not important and duplicates can be removed. I am wondering if I merge the two lists and then convert it to Set and then back to list if that would be the fastest. If the case is that when converting to Set it automatically removes duplicates. – PAujla Aug 06 '15 at 03:51
But if all variables are the same except for isCoolCat indicator which is true in one and false in the other would that be considered a duplicate with my override equals method? – PAujla Aug 06 '15 at 03:52
You are free to define the `hashcode` and `equals` methods however you like. If you want to ignore the `isCoolCat` variable, do not include it in the equals implementation. – bcorso Aug 06 '15 at 04:01
BTW, `Set` also has a Union method, which it seems like you are doing from your description. I'll update the answer. Also, this should be the fastest way, O(n), time. – bcorso Aug 06 '15 at 04:03
Thank you @bcorso. Your Solution worked out the best. I noticed for low number of MyClass in the list both solutions seem to take about the same time. I implemented as follow: 'Set tempOutSet = Collections.synchronizedSet(new HashSet(inList.size()+1,1)); tempOutSet.addAll(outList); tempOutSet.addAll(inList); outList = new ArrayList(tempOutSet);' On my platform, for size = 100,000, original implementation took **1 minute, 55 seconds, 268 milliseconds** and implementation made according to your suggestion took **39 seconds, 956 milliseconds.** – PAujla Aug 07 '15 at 19:46
@PAujla , I'm glad it helped! Yes, because this method has a lower asymptotic running time, you'll see the time savings you get using `Set` increase more the large your input is. – bcorso Aug 07 '15 at 22:58

score 0 · Answer 2 · edited May 23 '17 at 12:21

Hashing ! Hashing is always the answer !

Current complexity of this code is, O(nm) where n is the size of inList and m is the size of outList.

You can use a HashSet to reduce your complexity to O(n). Because contains will now take O(1)

This can be done like this,

   HashSet<MyClass> outSet = new HashSet<>(outList);
   for(MyClass inObj : inList)
   {
        if(!outSet.contains(inObj))
        {
              outList.add(inObj); 
         }
    }

Credits and Sources.

returning difference between two lists in java

Time complexity of contains(Object o), in an ArrayList of Objects

HashSet.contains performance

Thanks for the suggestion but bcorso's solution (similar to yours) worked out the best. — PAujla, Aug 07 '15 at 19:37

score 0 · Answer 3 · answered Aug 06 '15 at 17:26

2 minutes comparing 2 very large lists, probably not going to get much time savings here, so depending on your application, can you set a flag so that things dependant on this cannot run until finished and push this into it's own thread and let the user do something else (while also telling them this is on-going.) Or at least put up a progress bar. Letting the user know the app is busy and telling them (ish) how long it will take on something only taking a few minutes in a very complex computation like this is OK and probably better than just shaving a few seconds off the time. users are quite tolerant of delays if they know how long they will be and you tell them there is time to go get a coffee.

Not applicable in my current situation but thanks for the suggestion and will keep in mind for future use. — PAujla, Aug 07 '15 at 19:38

In Java what is the quickest way to check if list contains items from another list, both list are of same type?

3 Answers3