"比较方法违反其一般合同"仅在某些情况下被抛出

Question

首先,我知道许多其他线程都描述了这个问题.但是我无法找到并回答这个问题,为什么不总是抛出这个错误？

让我来描述一下我的意思.我写了一些示例代码来说明这一点:

public class Mushroom {

    public int size;

    public Mushroom(int size) {
        this.size = size;
    }

    @Override
    public boolean equals(Object obj) {
        //this is intentionally false - read in description
        return false;
    }
}

DSA

public class MushroomComparator implements Comparator<Mushroom> {

    @Override
    public int compare(Mushroom o1, Mushroom o2) {
        // here is the code which breaks the contract
         if (o1.size < o2.size){
             return 1;
         }else if(o1.size >o2.size){
             return -1;
         }
         return 1;
    }

}

最后测试比较:

public class ComparisonTest {
    public static void main(String[] args) {
//      System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
    List<Mushroom> forest = new ArrayList<>();

        for(int i =0; i<18; i++){
            Mushroom mushroom1 = new Mushroom(1);
            Mushroom mushroom2 = new Mushroom(3);
            Mushroom mushroom3 = new Mushroom(2);

            forest.add(mushroom1);
            forest.add(mushroom2);
            forest.add(mushroom3);

        }
        Collections.sort(forest, new MushroomComparator());
    }
}

在运行时,我们将收到此描述的问题

java.lang.IllegalArgumentException:比较方法违反了它的一般合同!

根据Collections.sort方法的文档:

(可选)如果实现检测到列表元素的自然顺序被发现违反了Comparable合同

那么让我们回答一下这个问题在Comparable的文档中是什么(在我的例子中我使用Comparator,但是从文档中它应该满足相同的要求)

对于所有x和y,实现者必须确保sgn(x.compareTo(y))== -sgn(y.compareTo(x))

这个规则我故意打破以获得我正在写的错误.这是compareTo方法的实现应该遵循的规则之一.其余的都在文档中描述,但一般来说,据我所知,文档的等价关系应该得到满足

它紧接着来自compareTo的契约,即商是C上的等价关系,并且自然顺序是C上的总顺序

现在真正困扰我的是我的测试方法中迭代次数变化的结果.如果您将数字从18更改为22,那么将不会抛出异常.此异常被描述为Optional,因此它确实意味着有时会抛出此异常,有时则不会.我没有深入研究排序算法(TimSort)的新实现(自Java 7以来改变排序算法).我明白,为了打破比较器合同,检查每组数据可能会耗费一些CPU消耗,但是有时候会有什么意图表明,有时甚至没有.这可能真的很有误导性.

Morover我可以将比较方法的实现更改为简单..返回1.根据文档,它应该违反合同.但事实并非如此.在文档中也保留了与equals方法的合同,但实际上并不需要

强烈建议,但并非严格要求(x.compareTo(y)== 0)==(x.equals(y))

并且在我的示例中检查它我已经实现了equals方法以返回始终为false.有了这个,我确信equals方法不会强制破坏比较器合同.

现在我的问题是:比较器的真正合同是什么(在破坏它的背景下)？为什么对于某些数据集会引发此异常,而对于其他数据则不会？也许我错过了什么？最后但并非最不重要的是 - 需要打破哪些规则才能抛出此异常？

需要注意的是,对此的解决方案可能会关闭此排列算法的新实现,此处所述并在我的示例代码中进行了评论.

Answer 1

为什么不总是抛出这个错误

因为这不是Collections.sort验证比较方法的工作.它的工作只是实现排序.但这样做的逻辑可以揭示无效的比较方法作为其在某些条件分支中的逻辑的副产品.在这种情况下,抛出而不是尝试继续使用无效的比较方法进行排序是有意义的.

什么是比较器的真正契约(在打破它的背景下)？

如果你违反合同,排序可能无法正常运行,或者根本没有.(并不是说它会验证你的比较方法.)

为什么对于某些数据集会引发此异常,而对于其他数据则不会？

如果排序没有遵循导致排序代码可以检测到的逻辑缺陷的路径,则它将不知道要抛出.但TimSort正在使用的确发生了一个逻辑分支,它揭示了无效的比较方法,所以它确实抛出.