What is the fastest way to compare two sets in Java

Question

I am trying to optimize a piece of code which compares elements of list   Eg   public void compare Set lt Record gt  firstSet  Set lt Record gt  secondSet       for Record firstRecord   firstSet           for Record secondRecord   secondSet                  comparing logic                     Please take into account that the number of records in sets will be high   Thanks  Shekhar

User · Answer

I think method reference with equals method can be used  We assume that the object type without a shadow of a doubt has its own comparison method  Plain and simple example is here   Set lt String gt  set   new HashSet lt  gt     set addAll Arrays asList  leo   bale   hanks      Set lt String gt  set2   new HashSet lt  gt     set2 addAll Arrays asList  hanks   leo   bale      Predicate lt Set gt  pred   set  equals  boolean result   pred test set2   System out println result        true

User · Answer

There s an O N  solution for very specific cases where    the sets are both sorted  both sorted in the same order   The following code assumes that both sets are based on the records comparable   A similar method could be based on on a Comparator       public class SortedSetComparitor  lt Foo extends Comparable lt Foo gt  gt               implements Comparator lt SortedSet lt Foo gt  gt              Override         public int compare  SortedSet lt Foo gt  arg0  SortedSet lt Foo gt  arg1                 Iterator lt Foo gt  otherRecords   arg1 iterator                for  Foo thisRecord   arg0                       Shorter sets sort first                  if   otherRecords hasNext    return 1                  int comparison   thisRecord compareTo otherRecords next                     if  comparison    0  return comparison                               Shorter sets sort first             if  otherRecords hasNext    return -1              else return 0

User · Answer

You have the following solution from https   www mkyong com java java-how-to-compare-two-sets   public static boolean equals Set lt   gt  set1  Set lt   gt  set2        if set1    null    set2   null           return false             if set1 size      set2 size             return false             return set1 containsAll set2       Or if you prefer to use a single return statement   public static boolean equals Set lt   gt  set1  Set lt   gt  set2      return set1    null       amp  amp  set2    null       amp  amp  set1 size      set2 size         amp  amp  set1 containsAll set2

User · Answer

There is a method in Guava Sets which can help here   public static  lt E gt   boolean equals Set lt   extends E gt  set1  Set lt   extends E gt  set2   return Sets symmetricDifference set1 set2  isEmpty

User · Answer

firstSet equals secondSet    It really depends on what you want to do in the comparison logic    ie what happens if you find an element in one set not in the other  Your method has a void return type so I assume you ll do the necessary work in this method   More fine-grained control if you need it   if   firstSet containsAll secondSet          do something if needs be   if   secondSet containsAll firstSet          do something if needs be     If you need to get the elements that are in one set and not the other  EDIT  set removeAll otherSet  returns a boolean  not a set  To use removeAll    you ll have to copy the set then use it   Set one   new HashSet lt  gt  firstSet   Set two   new HashSet lt  gt  secondSet   one removeAll secondSet   two removeAll firstSet     If the contents of one and two are both empty  then you know that the two sets were equal  If not  then you ve got the elements that made the sets unequal   You mentioned that the number of records might be high  If the underlying implementation is a HashSet then the fetching of each record is done in O 1  time  so you can t really get much better than that  TreeSet is O log n

User · Answer

I would put the secondSet in a HashMap before the comparison  This way you will reduce the second list s search time to n 1   Like this   HashMap lt Integer Record gt  hm   new HashMap lt Integer Record gt  secondSet size     int i   0  for Record secondRecord   secondSet       hm put i secondRecord       i      for Record firstRecord   firstSet       for int i 0  i lt secondSet size    i           use hm for comparison

User · Answer

public boolean equals Object o            if  o    this              return true          if    o instanceof Set               return false           Set lt String gt  a   this          Set lt String gt  b   o          Set lt String gt  thedifference a b   new HashSet lt String gt  a             thedifference a b removeAll b           if thedifference a b isEmpty      false  return false           Set lt String gt  thedifference b a   new HashSet lt String gt  b           thedifference b a removeAll a            if thedifference b a isEmpty      false  return false           return true

User · Answer

If you simply want to know if the sets are equal  the equals method on AbstractSet is implemented roughly as below       public boolean equals Object o            if  o    this              return true          if    o instanceof Set               return false          Collection c    Collection  o          if  c size      size                return false          return containsAll c           Note how it optimizes the common cases where    the two objects are the same the other object is not a set at all  and the two sets  sizes are different    After that  containsAll      will return false as soon as it finds an element in the other set that is not also in this set   But if all elements are present in both sets  it will need to test all of them   The worst case performance therefore occurs when the two sets are equal but not the same objects   That cost is typically O N  or O NlogN  depending on the implementation of this containsAll c    And you get close-to-worst case performance if the sets are large and only differ in a tiny percentage of the elements     UPDATE  If you are willing to invest time in a custom set implementation  there is an approach that can improve the  almost the same  case   The idea is that you need to pre-calculate and cache a hash for the entire set so that you could get the set s current hashcode value in O 1    Then you can compare the hashcode for the two sets as an acceleration     How could you implement a hashcode like that   Well if the set hashcode was    zero for an empty set  and the XOR of all of the element hashcodes for a non-empty set    then you could cheaply update the set s cached hashcode each time you added or removed an element   In both cases  you simply XOR the element s hashcode with the current set hashcode   Of course  this assumes that element hashcodes are stable while the elements are members of sets   It also assumes that the element classes hashcode function gives a good spread   That is because when the two set hashcodes are the same you still have to fall back to the O N  comparison of all elements     You could take this idea a bit further     at least in theory   WARNING - This is highly speculative   A  thought experiment  if you like   Suppose that your set element class has a method to return a crypto checksums for the element   Now implement the set s checksums by XORing the checksums returned for the elements   What does this buy us   Well  if we assume that nothing underhand is going on  the probability that any two unequal set elements have the same N-bit checksums is 2-N   And the probability 2 unequal sets have the same N-bit checksums is also 2-N   So my idea is that you can implement equals as       public boolean equals Object o            if  o    this              return true          if    o instanceof Set               return false          Collection c    Collection  o          if  c size      size                return false          return checksums equals c checksums           Under the assumptions above  this will only give you the wrong answer once in 2-N time   If you make N large enough  e g  512 bits  the probability of a wrong answer becomes negligible  e g  roughly 10-150    The downside is that computing the crypto checksums for elements is very expensive  especially as the number of bits increases   So you really need an effective mechanism for memoizing the checksums   And that could be problematic   And the other downside is that a non-zero probability of error may be unacceptable no matter how small the probability is    But if that is the case     how do you deal with the case where a cosmic ray flips a critical bit   Or if it simultaneously flips the same bit in two instances of a redundant system

User · Answer

If you are using Guava library it s possible to do           SetView lt Record gt  added   Sets difference secondSet  firstSet           SetView lt Record gt  removed   Sets difference firstSet  secondSet     And then make a conclusion based on these

[java] What is the fastest way to compare two sets in Java?

Examples related to java

Examples related to performance

Examples related to set