Java Comparator：违反总承包

发布时间：2020-12-14 06:06:30 所属栏目：Java 来源：网络整理

导读：所以我有这个比较器： import java.util.Comparator;public class SolutionComparator implements ComparatorExpressionTree { private final int target; public SolutionComparator(int target) { this.target = target; } @Override public int compare(E

所以我有这个比较器：

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

几个月来我一直在看这个代码,我无法找出它违反比较器总合同的原因.

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

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

编辑：异常跟踪

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)

解决方法

您的比较者违反了 the contract要求的平等传递性：

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

假设您有三个具有相应值的ExpressionTrees o1,o2,o3
v1,v2,v3
和解决方案成本
s1,s2,s3
这样的
v1 == v2,
target – v1 == v3 – target(so abs(target-v1)== abs(target-v3))
和
s1< s2(因此比较(o1,o2)== -1,为简单起见,可以说o1 然后o1 == o3和o2 == o3但是o1< o2,即
比较(o1,o3)== 0
但
sgn(比较(o1,o2))！= sgn(比较(o3,o2))
以来
sgn(比较(o1,o2))== -1和sgn(比较(o3,o2))== 0.

我不确定你会如何解决这个问题,但这就是它的原因.

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

Fix is to replace
if (v1 == v2)
with
if (Math.abs(target-v1) == Math.abs(target-v2))

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!