"比较方法违反了其总合同!" - 查找小样本数据集

Question

可能重复:
"比较方法违反了其总合同!"

我有一个更大的部分排序数据样本(> 700项)我想用Java 7排序并得到以下异常:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeLo(TimSort.java:747)
    at java.util.TimSort.mergeAt(TimSort.java:483)
    at java.util.TimSort.mergeCollapse(TimSort.java:410)
    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)

现在我正在尝试降低数据集的大小,以便找到更简单的原因.我写了一个小应用程序,它从较大的集合中挑选一个随机子集来重现异常.

private static final int SUBSET_SIZE = 32;

public void testSorting() {
    ...
    final Random random = new Random();
    for (int i = 10000000; i-- > 0; ) {
        testFew(strings, random);
    }
}

private void testFew(List<String> strings, Random random) {
    final List<String> list = new ArrayList<String>();
    int index = 0;
    for (int i = 0; i < SUBSET_SIZE; i++) {
        final int rnd = random.nextInt(strings.size() / 100) + 1;
        index = (index + rnd) % strings.size();
        list.add(strings.get(index));
    }

    try {
        Collections.sort(list, MY_COMPARATOR);
    }
    catch (RuntimeException ex) {
        for (String s : list) {
            System.err.println(s);
        }
        throw ex;
    }
}

奇怪的是,如果子集包含至少32个项目,那么找到要重现的样本非常简单,但是我没有成功找到一个较小的集合.恕我直言,这有点像排序算法中的错误而不是我们的比较器.

Answer 1

这意味着您的Comparator有一个错误 compareTo(a, b) != -compareTo(b, a)

Answer 2

恕我直言,这有点像排序算法中的错误而不是我们的比较器.

对我来说,这有点像根据输入集的大小使用2种不同的排序算法.

虽然排序实现中存在错误并非不可能,但问题出现在您的比较器中的可能性要大得多......就像异常消息所说的那样.建议您将精力集中在代码上,而不是在库代码中查找(可能不存在的)错误.