比较相同内容的可迭代对象，但不考虑顺序 [英] Comparing iterables for same content, but not regarding order
问题描述
我正在尝试比较相同大小的Java中的两个Iterable.我只需要知道内容是一样的.但是，诸如[1、2]和[1、2、2]之类的东西不应该相等，而[1、2、2、4]之类的应该等于[1、2、4、2].
boolean functionName() {
boolean pvk;
... setup ...
for(Edge e : pMST.edges()) {
pvk = false;
for(Edge f : kMST.edges()) {
if(e == f) {
pvk = true;
System.out.println("True.");
}
}
if(!pvk) return false;
}
return true;
}
这是我最初的糟糕尝试，但这不仅会始终返回false，而且无法正确处理重复项.
将此答案与此线程，尤其是此答案要创建有效但可读的解决方案，您可以使用
static boolean unorderedEquals(Collection<?> coll1, Collection<?> coll2) {
if(coll1.size() != coll2.size()) return false;
Map<Object, Integer> freq = new HashMap<>();
for(Object o: coll1) freq.merge(o, 1, Integer::sum);
for(Object o: coll2)
if(freq.merge(o, -1, Integer::sum) < 0) return false;
return true;
}
第一个循环会像链接的答案中那样创建一个频率图，但是要建立昂贵的比较，第二个循环会减少计数，而不是构建第二个图，如果计数变为负数，则会立即返回. merge方法可以顺利处理缺少键的情况.
由于在方法开始时就已经检查出两个列表的大小相同，因此在增加和减少之后，总计数必须为零.由于我们已经证明没有负数，因此我们立即返回了它们，因此也不能有非零的正数.因此，我们可以在第二个循环之后返回true，而无需进一步检查.
支持任意Iterable不同于Collection之处在于不一定具有size()方法，这有点棘手，因为我们当时无法进行预检查，因此必须保持计数:
static boolean unorderedEquals(Iterable<?> iter1, Iterable<?> iter2) {
Map<Object, Integer> freq = new HashMap<>();
int size = 0;
for(Object o: iter1) {
freq.merge(o, 1, Integer::sum);
size++;
}
for(Object o: iter2)
if(--size < 0 || freq.merge(o, -1, Integer::sum) < 0) return false;
return size == 0;
}
如果要避免装箱开销，则必须对地图采用可变的值，例如
static boolean unorderedEquals(Collection<?> coll1, Collection<?> coll2) {
if(coll1.size() != coll2.size()) return false;
Map<Object, int[]> freq = new HashMap<>();
for(Object o: coll1) freq.computeIfAbsent(o, x -> new int[1])[0]++;
int[] absent = { 0 };
for(Object o: coll2) if(freq.getOrDefault(o, absent)[0]-- == 0) return false;
return true;
}
但是我认为他不会有所回报.对于少量事件，装箱将重用Integer实例，而使用可变值时，我们需要为每个不同的元素使用不同的int[]对象.
但是，像
static boolean unorderedEquals(Iterable<?> coll1, Iterable<?> coll2) {
Map<Object, int[]> freq = new HashMap<>();
for(Object o: coll1) freq.computeIfAbsent(o, x -> new int[1])[0]++;
int[] absent = {};
for(Object o: coll2)
if(freq.compute(o, (key,c) -> c == null || c[0] == 0? absent:
--c[0] == 0? null: c) == absent) return false;
return freq.isEmpty();
}
那样使用compute对于Iterable解决方案可能会很有趣
static boolean unorderedEquals(Iterable<?> coll1, Iterable<?> coll2) {
Map<Object, int[]> freq = new HashMap<>();
for(Object o: coll1) freq.computeIfAbsent(o, x -> new int[1])[0]++;
int[] absent = {};
for(Object o: coll2)
if(freq.compute(o, (key,c) -> c == null || c[0] == 0? absent:
--c[0] == 0? null: c) == absent) return false;
return freq.isEmpty();
}
当计数达到零时，它会从地图中删除条目，因此我们只需要在最后检查地图是否为空.
I'm attempting to compare two Iterables in Java of same size. I only need to know that the contents are the same. However, something like [1, 2] and [1, 2, 2] should not be equal, while [1, 2, 2, 4] should equal [1, 2, 4, 2].
boolean functionName() {
boolean pvk;
... setup ...
for(Edge e : pMST.edges()) {
pvk = false;
for(Edge f : kMST.edges()) {
if(e == f) {
pvk = true;
System.out.println("True.");
}
}
if(!pvk) return false;
}
return true;
}
There's my initial lousy attempt, but not only does this always return false, it doesn't account for duplicates properly.
Combining this answer with ideas from this thread, notably this answer to create an efficient but readable solution, you may use
static boolean unorderedEquals(Collection<?> coll1, Collection<?> coll2) {
if(coll1.size() != coll2.size()) return false;
Map<Object, Integer> freq = new HashMap<>();
for(Object o: coll1) freq.merge(o, 1, Integer::sum);
for(Object o: coll2)
if(freq.merge(o, -1, Integer::sum) < 0) return false;
return true;
}
The first loop creates a frequency map like in the linked answer, but instead of building a second map, to perform an expensive comparison, the second loop decreases the counts on each occurrence, returning immediately, if a count became negative. The merge method smoothly handles the case of absent keys.
Since it has been checked right at the beginning of the method that both lists have the same size, after increasing and decreasing, the total count must be zero. Since we have proven that there are no negative numbers, as we returned immediately for them, there can’t be positive non-zero values either. So we can return true after the second loop without further checks.
Supporting arbitrary Iterables, which differ from Collection in not necessarily having a size() method, is a bit trickier, as we can’t do the pre-check then and hence, have to maintain the count:
static boolean unorderedEquals(Iterable<?> iter1, Iterable<?> iter2) {
Map<Object, Integer> freq = new HashMap<>();
int size = 0;
for(Object o: iter1) {
freq.merge(o, 1, Integer::sum);
size++;
}
for(Object o: iter2)
if(--size < 0 || freq.merge(o, -1, Integer::sum) < 0) return false;
return size == 0;
}
If we want avoid the boxing overhead, we have to resort to a mutable value for the map, e.g.
static boolean unorderedEquals(Collection<?> coll1, Collection<?> coll2) {
if(coll1.size() != coll2.size()) return false;
Map<Object, int[]> freq = new HashMap<>();
for(Object o: coll1) freq.computeIfAbsent(o, x -> new int[1])[0]++;
int[] absent = { 0 };
for(Object o: coll2) if(freq.getOrDefault(o, absent)[0]-- == 0) return false;
return true;
}
But I don’t think that his will pay off. For small numbers of occurrences, boxing will reuse the Integer instances whereas we need a distinct int[] object for each distinct element when using mutable values.
But using compute might be interesting for the Iterable solution, when using it like
static boolean unorderedEquals(Iterable<?> coll1, Iterable<?> coll2) {
Map<Object, int[]> freq = new HashMap<>();
for(Object o: coll1) freq.computeIfAbsent(o, x -> new int[1])[0]++;
int[] absent = {};
for(Object o: coll2)
if(freq.compute(o, (key,c) -> c == null || c[0] == 0? absent:
--c[0] == 0? null: c) == absent) return false;
return freq.isEmpty();
}
which removes entries from the map when their count reaches zero, so we only have to check the map for emptiness at the end.
这篇关于比较相同内容的可迭代对象，但不考虑顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
