在Java中比较两组的最快方法是什么?

我正在尝试优化比较列表元素的一段代码。

例如。

public void compare(Set<Record> firstSet, Set<Record> secondSet){ for(Record firstRecord : firstSet){ for(Record secondRecord : secondSet){ // comparing logic } } } 

请注意套内的logging数量会很高。

谢谢

谢卡尔

 firstSet.equals(secondSet) 

这实际上取决于你想要在比较逻辑中做什么…即如果你发现一个元素不在另一个元素中会发生什么? 你的方法有一个void返回types,所以我假设你会在这个方法中做必要的工作。

如果你需要更细粒度的控制:

 if (!firstSet.containsAll(secondSet)) { // do something if needs be } if (!secondSet.containsAll(firstSet)) { // do something if needs be } 

如果你需要得到一套而不是另一套的元素。
编辑: set.removeAll(otherSet)返回一个布尔值,而不是一组。 要使用removeAll(),您必须复制集合然后使用它。

 Set one = firstSet; Set two = secondSet one.removeAll(secondSet); two.removeAll(firstSet); 

如果onetwo的内容都是空的,那么你知道这两个集合是平等的。 如果没有,那么你已经有了使这些集合不相等的元素。

你提到logging数可能很高。 如果底层实现是一个HashSet那么每个logging的获取都是在O(1)时间完成的,所以你不可能比这更好。 TreeSetO(log n)

如果你只是想知道这些集合是否相等, AbstractSet上的equals方法大致如下:

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

请注意如何优化以下常见情况:

  • 这两个对象是一样的
  • 另一个对象根本就不是一个集合
  • 两套的尺寸是不同的。

之后, containsAll(...)只要在另一个集合中find一个不在这个集合中的元素,就会返回false 。 但是,如果所有元素都出现在两个集合中,则需要testing所有这些元素。

因此,当两组相等而不是相同的对象时,就会出现最坏的情况。 这个代价通常是O(N)O(NlogN)取决于this.containsAll(c)

如果这些设置很大,而且只有很小比例的元素,则会出现接近最差的情况。


UPDATE

如果您愿意投入时间进行自定义设置实施,则可以改善“几乎相同”的情况。

这个想法是,你需要预先计算和caching整个集合的散列,以便你可以得到O(1)的集合的当前哈希码值。 然后你可以比较这两组哈希码作为加速度。

你怎么能实现这样的哈希码? 那么如果设置的哈希码是:

  • 零空一套,和
  • 非空集合的所有元素哈希码的XOR,

那么每次添加或删除元素时,您都可以便宜地更新集合的caching哈希码。 在这两种情况下,只需使用当前设置的哈希码对元素的哈希码进行XOR即可。

当然,这个假设元素hashcodes是稳定的,而元素是集合的成员。 它还假定元素类哈希码function给出了一个很好的传播。 这是因为当两个集合的hashcode是相同的,你仍然必须回落到所有元素的O(N)比较。


你可以把这个想法稍微进一步…至less在理论上。

假设你的set元素类有一个方法来返回元素的encryption校验和。 现在通过XORing为元素返回的校验和来实现该设置的校验和。

这是什么买我们?

那么,如果我们假设什么都不是正在进行,那么任何两个不相等的集合元素都具有相同的N位校验和的概率是2- N 。 而概率2不等套具有相同的N位校验和也是2 -N 。 所以我的想法是,你可以实现equals为:

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

根据上面的假设,这只会在2到N次给你一个错误的答案。 如果N足够大(例如512比特),错误答案的概率变得可以忽略不计(例如大约10-150 )。

缺点是计算元素的encryption校验和是非常昂贵的,特别是随着位数的增加。 所以你真的需要一个有效的机制来记忆校验和。 这可能是有问题的。

番石榴Sets有一个方法可以帮助你:

 public static <E> boolean equals(Set<? extends E> set1, Set<? extends E> set2){ return Sets.symmetricDifference(set1,set2).isEmpty(); } 
 public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Set)) return false; Set<String> a = this; Set<String> b = o; Set<String> thedifference_a_b = new HashSet<String>(a); thedifference_a_b.removeAll(b); if(thedifference_a_b.isEmpty() == false) return false; Set<String> thedifference_b_a = new HashSet<String>(b); thedifference_b_a.removeAll(a); if(thedifference_b_a.isEmpty() == false) return false; return true; } 

对于非常特殊的情况,有一个O(N)解决scheme,其中:

  • 集合都被分类
  • 两者都以相同的顺序sorting

以下代码假定两个集合都是基于可比较的logging。 类似的方法可以基于比较器。

  public class SortedSetComparitor <Foo extends Comparable<Foo>> implements Comparator<SortedSet<Foo>> { @Override public int compare( SortedSet<Foo> arg0, SortedSet<Foo> arg1 ) { Iterator<Foo> 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; } } 

在比较之前,我会把第二个set放在一个HashMap中。 这样你将第二个列表的search时间减less到n(1)。 喜欢这个:

 HashMap<Integer,Record> hm = new HashMap<Integer,Record>(secondSet.size()); int i = 0; for(Record secondRecord : secondSet){ hm.put(i,secondRecord); i++; } for(Record firstRecord : firstSet){ for(int i=0; i<secondSet.size(); i++){ //use hm for comparison } } 

如果你正在使用Guava图书馆,可以这样做:

  SetView<Record> added = Sets.difference(secondSet, firstSet); SetView<Record> removed = Sets.difference(firstSet, secondSet); 

然后根据这些结论做出结论。

我认为可以使用equals方法的方法引用。 我们假设没有疑问的对象types有其自己的比较方法。 简单而简单的例子就在这里,

 Set<String> set = new HashSet<>(); set.addAll(Arrays.asList("leo","bale","hanks")); Set<String> set2 = new HashSet<>(); set2.addAll(Arrays.asList("hanks","leo","bale")); Predicate<Set> pred = set::equals; boolean result = pred.test(set2); System.out.println(result); // true