Java Comparator：违反总承包 [英] Java Comparator: Violates General Contract

问题描述

所以我有这个比较器：

import java.util.Comparator;

public class SolutionComparator implements Comparator<ExpressionTree> {
    private final int target;

    public SolutionComparator(int target) {
        this.target = target;
    }

    @Override
    public int compare(ExpressionTree o1, ExpressionTree o2) {
        int v1 = o1.getValue();
        int v2 = o2.getValue();
        if (v1 == -1 && v2 == -1)
            return 0;
        else if (v1 == -1)
            return 1;
        else if (v2 == -1)
            return -1;
        else if (v1 == v2)
            return (int)Math.signum(solutionCost(o1) - solutionCost(o2));
        else
            return (int)Math.signum(Math.abs(target-v1) - Math.abs(target-v2));
    }

    private int solutionCost(ExpressionTree v) {
        int cost = 0;
        Operation o = v.getOperator();
        if (o != Operation.NONE) {
            cost += o.getCost();
            for (ExpressionTree e : v.getChildren())
                cost += solutionCost(e);
        }
        return cost;
    }
}

我已经看了几个月的代码了，我无法找出它违反比较器一般合同的原因。

I have been looking at this code for months, and I can't find out why it violates comparator general contract.

这个想法是每个ExpressionTree都可以被评估为一个结果。 （ getValue（）方法）。如果它返回-1，它总是高于其他数字。如果值不同，则与 target 的接近程度进行比较。如果值相同，则按解决方案成本进行比较。

The idea is that each ExpressionTree can be evaluated to one result. (the getValue() method). If it returns -1, it is always higher than other number. If the value differs, compare to how close it is to target. If the value is same, compare by solution cost.

使用此比较器，Java抛出IllegalStatesException。但是，如果我删除基于成本的比较，它就有效。

With this comparator Java throws IllegalStatesException. But if I remove cost-based comparison, it works.

编辑：异常跟踪

Exception in thread "Thread-3" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeHi(TimSort.java:868)
    at java.util.TimSort.mergeAt(TimSort.java:485)
    at java.util.TimSort.mergeCollapse(TimSort.java:408)
    at java.util.TimSort.sort(TimSort.java:214)
    at java.util.TimSort.sort(TimSort.java:173)
    at java.util.Arrays.sort(Arrays.java:659)
    at java.util.Collections.sort(Collections.java:217)
    at ***.run(***:123)
    at java.lang.Thread.run(Thread.java:722)

推荐答案

您的比较器违反了合同：

最后，实现者必须确保compare（x，y）== 0表示所有z的sgn（compare（x，z））== sgn（compare（y，z））。

Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.

假设您有三个 ExpressionTree s o 1，o2，o3 各自的值

v1，v2，v3

和solutionCosts < br>
s1，s2，s3

使得
v1 == v2 ，

target - v1 == v3 - target （所以 abs（target-v1） == abs（target-v3））

和

s1< s2 （这样比较（o1，o2）== -1 ，可以说是 o1< o2 为简单起见。）
然后 o1 == o3 和 o2 == o3 但是 o1< o2 ，即
比较（o1，o3）== 0

但< br>
sgn（比较（o1，o2））！= sgn（比较（o3，o2））

自

sgn（比较（o1，o2））== -1 和 sgn（比较（o3，o2））== 0 。

Suppose you have three ExpressionTrees o1, o2, o3 with respective values
v1, v2, v3
and solutionCosts
s1, s2, s3
such that
v1 == v2,
target - v1 == v3 - target (so abs(target-v1) == abs(target-v3))
and
s1 < s2 (so that compare(o1, o2) == -1, which can be said o1 < o2 for simplicity).
Then o1 == o3 and o2 == o3 but o1 < o2, that is,
compare(o1, o3) == 0
but
sgn(compare(o1, o2)) != sgn(compare(o3, o2))
since
sgn(compare(o1, o2)) == -1 and sgn(compare(o3, o2)) == 0.

我不知道你会如何解决这个问题，但这就是它的原因。

编辑： @Nat（OP）提出了这个优雅的解决方案：

@Nat (OP) came up with this elegant solution:

修复是替换

if（v1 == v2）

with

if（Math.abs（target-v1）== Math.abs（target-v2））

这篇关于Java Comparator：违反总承包的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！