Java， 使用自定义比较器对庞大的 ArrayList 进行排序有时会抛出 iIllegalArgumentException [重复]

Question

我使用以下算法对 8k 元素列表进行排序。

//sort by y coordinates using the topleft point of every contour's bounding box
Collections.sort(contourList, new Comparator<MatOfPoint>() {
    @Override
    public int compare(MatOfPoint o1, MatOfPoint o2) {
        Rect rect1 = Imgproc.boundingRect(o1);
        Rect rect2 = Imgproc.boundingRect(o2);
        int result = Double.compare(rect1.tl().y, rect2.tl().y);
        return result;
    }
} );


//sort by x coordinates
Collections.sort(contourList, new Comparator<MatOfPoint>() {
    @Override
    public int compare(MatOfPoint o1, MatOfPoint o2) {
        Rect rect1 = Imgproc.boundingRect(o1);
        Rect rect2 = Imgproc.boundingRect(o2);
        int result = 0;
        double total = rect1.tl().y/rect2.tl().y;
        if (total>=0.9 && total<=1.4 ){
            result = Double.compare(rect1.tl().x, rect2.tl().x);
        }
        return result;
    }
});

问题是，虽然按Y坐标排序（第一个比较器）不会产生任何问题（我不知道这是否只是运气问题），

按X坐标（第二个比较器）排序会提示此异常：

java.lang.IllegalArgumentException: Comparison method violates its general contract!

.我修改了算法，添加了以下内容来打印调试信息：

DecimalFormat df = new DecimalFormat();
df.setMaximumFractionDigits(2);
log.debug("tot: {}; p1.x: {}, p1.y: {}; p2.x {}, p2.y {}",
        df.format(total),
        rect1.tl().x,
        rect1.tl().y,
        rect2.tl().x,
        rect2.tl().y);

，这些是异常发生前的最后10个条目:

tot: 0,85; p1.x: 81.0, p1.y: 1415.0; p2.x 429.0, p2.y 1657.0
tot: 0,78; p1.x: 81.0, p1.y: 1415.0; p2.x 677.0, p2.y 1820.0
tot: 0,75; p1.x: 81.0, p1.y: 1415.0; p2.x 703.0, p2.y 1879.0
tot: 0,78; p1.x: 81.0, p1.y: 1415.0; p2.x 1010.0, p2.y 1820.0
tot: 0,83; p1.x: 81.0, p1.y: 1415.0; p2.x 1250.0, p2.y 1708.0
tot: 0,85; p1.x: 81.0, p1.y: 1415.0; p2.x 1260.0, p2.y 1657.0
tot: 0,76; p1.x: 81.0, p1.y: 1415.0; p2.x 1282.0, p2.y 1867.0
tot: 0,82; p1.x: 81.0, p1.y: 1415.0; p2.x 1282.0, p2.y 1736.0
tot: 0,86; p1.x: 81.0, p1.y: 1415.0; p2.x 1282.0, p2.y 1649.0
tot: 0,76; p1.x: 81.0, p1.y: 1415.0; p2.x 1507.0, p2.y 1864.0
Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeLo(TimSort.java:777)
    at java.util.TimSort.mergeAt(TimSort.java:514)
    at java.util.TimSort.mergeCollapse(TimSort.java:441)
    at java.util.TimSort.sort(TimSort.java:245)
    at java.util.Arrays.sort(Arrays.java:1512)
    at java.util.ArrayList.sort(ArrayList.java:1462)
    at java.util.Collections.sort(Collections.java:175)

我从来没有遇到过这样的问题，有人能提供一个解释和解决方案，让这些算法变得可靠吗？

预先非常感谢你的努力

里卡尔多

编辑1：我添加了如下调试信息：

static Comparator<MatOfPoint> contourXComparator() {

    return new Comparator<MatOfPoint>() {
        @Override
        public int compare(MatOfPoint o1, MatOfPoint o2) {
            Rect rect1 = boundingRect(o1);
            Rect rect2 = boundingRect(o2);
            int result = 0;
            double total = rect1.tl().y / rect2.tl().y;
            /* debug purpose */
            DecimalFormat df = new DecimalFormat();
            df.setMaximumFractionDigits(2);
            log.debug("tot: {}; p1.x: {}, p1.y: {}; p2.x {}, p2.y {}",
                    df.format(total),
                    rect1.tl().x,
                    rect1.tl().y,
                    rect2.tl().x,
                    rect2.tl().y);
            /* endof debug purpose */
            if (total >= 0.9 && total <= 1.4) {
                result = Double.compare(rect1.tl().x, rect2.tl().x);
            }
            return result;
        }
    };

Answer 1

您一致地返回一个值进行比较。例如，如果您为两个A返回-1

这段代码的主要问题是，您引入了一个if块，这违反了比较，因为您可能有一组坐标，即使它们不相等，您也可以通过返回0来调用它们。

您可以先尝试排序，就像对 y 所做的那样，然后再过滤掉。

Answer 2

您的第二个比较器不是传递的。考虑三个要素

< li>a = (1，4) < li>b = (1，5) < li>c = (1，6)

(x，y)表示它们的边界矩形的尺寸。

根据您的比较器a