在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);
如果one和two的内容都是空的，那么你知道这两个集合是平等的。 如果没有，那么你已经有了使这些集合不相等的元素。
你提到logging数可能很高。 如果底层实现是一个HashSet那么每个logging的获取都是在O(1)时间完成的，所以你不可能比这更好。 TreeSet是O(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
