Java，使用自定义比较器对大型ArrayList进行排序有时会引发iIllegalArgumentException [英] Java, Sorting a massive ArrayList using a custom comparator sometimes throws iIllegalArgumentException
问题描述
我正在使用以下算法对8k +元素列表进行排序.
I am sorting an 8k+ elements List using the following algorithms.
//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坐标(第一个比较器)排序不会带来任何问题(我现在不知道这是否只是运气问题)，
The problem is that, while sorting by Y coordinates (the first comparator) does not give any problem (I don't know at this point if it is only a matter of luck),
按X坐标排序(第二个比较器)会产生此异常:
sorting by X coordinates (the second comparator) yelds this exception:
java.lang.IllegalArgumentException: Comparison method violates its general contract!
.我修改了算法，添加了以下内容以打印调试信息:
. I modified the algorithm adding what follows to print debug info:
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个条目:
, these are the last 10 entries before the exception occours:
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)
我从来没有遇到过这样的问题，有人可以同时提供解释和解决方案以使这些算法可靠吗?
I've never incurred in a problem like this, could someone provide both an explanation and a solution to make these algos reliable?
非常感谢您的努力
里卡多
Edit1:我添加了调试信息，如下所示:
I've added the debug info as it follows:
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;
}
};
推荐答案
您的第二个比较器不是可传递的.考虑三个要素
Your second comparator is not transitive. Consider the three elements
- a =(1,4)
- b =(1,5)
- c =(1,6)
(x，y)表示其边界矩形的尺寸.
(x,y) denotes the dimensions of their bounding rectangles.
根据比较器a < b和b < c但a = c.从那里可以推断出a=c < b，但同时可以推断出a=c > b.您不能按这样的顺序排序，因此是例外.
According to your comparator a < b and b < c but a = c. From there you could deduce that a=c < b but at the same time a=c > b. You cannot sort with such an order, therefore the exception.
这篇关于Java，使用自定义比较器对大型ArrayList进行排序有时会引发iIllegalArgumentException的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
