5

Java 7更改了排序算法，使其抛出

java.lang.IllegalArgumentException：“比较方法违反了它的一般约定！”

在某些情况下，当使用的比较器有问题时。是否可以判断比较器中的哪种错误导致了这种情况？在我的实验中，如果 x != x 无关紧要，如果 x < y 和 y < z 但 z < x 也无关紧要，但对于某些值，如果 x = y 和 y = z 但 x < z x，y，z。一般是这样吗？

（如果有一个通用规则，在比较器中查找错误可能会更容易。但当然最好修复所有错误。:-)）

特别是，以下两个比较器并没有让 TimSort 抱怨：

    final Random rnd = new Random(52);

    Comparator<Integer> brokenButNoProblem1 = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            if (o1 < o2) {
                return Compare.LESSER;
            } else if (o1 > o2) {
                return Compare.GREATER;
            }
            return rnd.nextBoolean() ? Compare.LESSER : Compare.GREATER;
        }
    };

    Comparator<Integer> brokenButNoProblem2 = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            if (o1 == o2) {
                return Compare.EQUAL;
            }
            return rnd.nextBoolean() ? Compare.LESSER : Compare.GREATER;
        }
    };

但是下面的比较器确实让它抛出了：

    Comparator<Integer> brokenAndThrowsUp = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            if (Math.abs(o1 - o2) < 10) {
                return Compare.EQUAL; // WRONG and does matter
            }
            return Ordering.natural().compare(o1, o2);
        }
    };

更新：在一些现实生活中的数据中，我们遇到了一个失败，其中没有 x,y,z 且 x = y 和 y = z 但 x < z 。所以看来我的猜测是错误的，而且似乎不仅仅是这种特定的失败。有更好的想法吗？

4

2 回答 2

6

看了ComparableTimSort我不太确定的代码后。我们来分析一下。这是抛出它的唯一方法（有一个类似的方法只对交换的角色执行相同的操作，因此分析其中一个就足够了）。

private void mergeLo(int base1, int len1, int base2, int len2) {
        assert len1 > 0 && len2 > 0 && base1 + len1 == base2;

        // Copy first run into temp array
        Object[] a = this.a; // For performance
        Object[] tmp = ensureCapacity(len1);

        int cursor1 = tmpBase; // Indexes into tmp array
        int cursor2 = base2;   // Indexes int a
        int dest = base1;      // Indexes int a
        System.arraycopy(a, base1, tmp, cursor1, len1);

        // Move first element of second run and deal with degenerate cases
        a[dest++] = a[cursor2++];
        if (--len2 == 0) {
            System.arraycopy(tmp, cursor1, a, dest, len1);
            return;
        }
        if (len1 == 1) {
            System.arraycopy(a, cursor2, a, dest, len2);
            a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
            return;
        }

        int minGallop = this.minGallop;  // Use local variable for performance
    outer:
        while (true) {
            int count1 = 0; // Number of times in a row that first run won
            int count2 = 0; // Number of times in a row that second run won

            /*
             * Do the straightforward thing until (if ever) one run starts
             * winning consistently.
             */
// ------------------ USUAL MERGE
            do {
                assert len1 > 1 && len2 > 0;
                if (((Comparable) a[cursor2]).compareTo(tmp[cursor1]) < 0) {
                    a[dest++] = a[cursor2++];
                    count2++;
                    count1 = 0;
                    if (--len2 == 0)
                        break outer;
                } else {
                    a[dest++] = tmp[cursor1++];
                    count1++;
                    count2 = 0;
                    if (--len1 == 1)
                        break outer;
                }
            } while ((count1 | count2) < minGallop);

// ------------------ GALLOP
            /*
             * One run is winning so consistently that galloping may be a
             * huge win. So try that, and continue galloping until (if ever)
             * neither run appears to be winning consistently anymore.
             */
            do {
                assert len1 > 1 && len2 > 0;
                count1 = gallopRight((Comparable) a[cursor2], tmp, cursor1, len1, 0);
                if (count1 != 0) {
                    System.arraycopy(tmp, cursor1, a, dest, count1);
                    dest += count1;
                    cursor1 += count1;
                    len1 -= count1;
// -->>>>>>>> HERE IS WHERE GALLOPPING TOO FAR WILL TRIGGER THE EXCEPTION
                    if (len1 <= 1)  // len1 == 1 || len1 == 0
                        break outer;
                }
                a[dest++] = a[cursor2++];
                if (--len2 == 0)
                    break outer;

                count2 = gallopLeft((Comparable) tmp[cursor1], a, cursor2, len2, 0);
                if (count2 != 0) {
                    System.arraycopy(a, cursor2, a, dest, count2);
                    dest += count2;
                    cursor2 += count2;
                    len2 -= count2;
                    if (len2 == 0)
                        break outer;
                }
                a[dest++] = tmp[cursor1++];
                if (--len1 == 1)
                    break outer;
                minGallop--;
            } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
            if (minGallop < 0)
                minGallop = 0;
            minGallop += 2;  // Penalize for leaving gallop mode
        }  // End of "outer" loop
        this.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to field

        if (len1 == 1) {
            assert len2 > 0;
            System.arraycopy(a, cursor2, a, dest, len2);
            a[dest + len2] = tmp[cursor1]; //  Last elt of run 1 to end of merge
        } else if (len1 == 0) {
            throw new IllegalArgumentException(
                "Comparison method violates its general contract!");
        } else {
            assert len2 == 0;
            assert len1 > 1;
            System.arraycopy(tmp, cursor1, a, dest, len1);
        }
    }

该方法执行两个排序运行的合并。它会进行通常的合并，但一旦遇到一方总是开始“获胜”（即，总是比另一方少），它就会开始“疾驰”。Gallopping 试图通过向前看更多元素而不是一次比较一个元素来使事情变得更快。由于应该对运行进行排序，因此向前看就可以了。

len1您会看到异常仅0在结束时才抛出。第一个观察结果如下：在通常的合并期间，永远不会抛出异常，因为一旦lenthis循环直接中止1。因此，异常只能作为 glop 的结果抛出。

这已经强烈暗示异常行为是不可靠的：只要您有小数据集（如此之小以至于生成的运行可能永远不会像MIN_GALLOP现在一样疾驰7）或者生成的运行总是巧合地生成从不疾驰的合并，您将永远不会收到异常。因此，如果不进一步检查该gallopRight方法，我们可以得出结论，您不能依赖异常：无论您的比较器有多错误，它都可能永远不会被抛出。

于 2014-07-25T08:48:17.893 回答
-1

从文档中：

IllegalArgumentException -（可选）如果发现数组元素的自然顺序违反了 Comparable 协定

我在提到的合同上没有找到太多，但恕我直言，它应该代表一个总订单（即compareTo方法定义的关系必须是传递的、反对称的和总的）。如果不满足该要求，sort可能会抛出IllegalArgumentException. （我说可能是因为未能满足此要求可能会被忽视。）

编辑：添加了使关系成为总订单的属性的链接。

于 2014-07-25T08:53:08.593 回答