英文:
"Comparison method violates general contract " while sorting multi dimensional array
问题
以下是翻译好的部分：
我正在使用自定义比较器对一个二维数组进行排序，在某些情况下出现以下错误：
java.lang.IllegalArgumentException: Comparison method violates its general contract!
at line 781, java.base/java.util.TimSort.mergeLo
at line 518, java.base/java.util.TimSort.mergeAt
at line 448, java.base/java.util.TimSort.mergeCollapse
at line 245, java.base/java.util.TimSort.sort
at line 1442, java.base/java.util.Arrays.sort
以下是抛出此错误的代码：
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, new SortComparator());
}
}
class SortComparator implements Comparator<int[]> {
public int compare(int[] a, int[] b) {
if (a[0] < b[0]) {
return -1;
} else if (a[0] > b[0]) {
return 1;
} else {
if (a[1] < b[1]) {
return -1;
} else {
return 1;
}
}
}
}
然而，当我使用以下实现的SortComparator类时，一切都正常：
class SortComparator implements Comparator<int[]> {
public int compare(int[] a, int[] b) {
if (a[0] < b[0]) {
return -1;
} else if (a[0] > b[0]) {
return 1;
} else {
if (a[1] < b[1]) {
return -1;
} else if (a[1] > b[1]) {
return 1;
} else {
return 0;
}
}
}
}
我能知道第一个SortComparator实现抛出错误的原因是什么吗？
英文:
I am sorting a 2-d array using custom comparator and getting the following error in some cases :
> java.lang.IllegalArgumentException: Comparison method violates its general contract!
at line 781, java.base/java.util.TimSort.mergeLo
at line 518, java.base/java.util.TimSort.mergeAt
at line 448, java.base/java.util.TimSort.mergeCollapse
at line 245, java.base/java.util.TimSort.sort
at line 1442, java.base/java.util.Arrays.sort
Below is the code that is throwing this error :
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, new SortComparator());
}
}
class SortComparator implements Comparator<int[]> {
public int compare(int []a, int []b) {
if(a[0] < b[0]) {
return -1;
} else if(a[0] > b[0]) {
return 1;
} else {
if(a[1] < b[1]) {
return -1;
} else {
return 1;
}
}
}
}
Although when I am using the below implementation of SortComparator class everything works fine :
class SortComparator implements Comparator<int[]> {
public int compare(int []a, int []b) {
if(a[0] < b[0]) {
return -1;
} else if(a[0] > b[0]) {
return 1;
} else {
if(a[1] < b[1]) {
return -1;
} else if(a[1]> b[1]) {
return 1;
} else {
return 0;
}
}
}
}
Can I know because of what reason first implementation of SortComparator is throwing error ?
答案1
得分: 2
问题在于你的第一个 SortComparator 实现永远无法返回 0。
因此，SortComparator.compare(a, a) 无法返回所需的 0，因为这是 Comparator 实现的“通用契约”。
实际上，SortComparator.compare(a, a) 将返回 1。
实际契约在 javadoc 中有说明。它说：
表达式
sgn(expression)表示数学符号函数，根据表达式的值是否为负、零或正，定义返回 -1、0 或 1 中的一个值。
实现者必须确保对于所有 x 和 y，sgn(compare(x, y)) == -sgn(compare(y, x))。 （这意味着，如果且仅如果 compare(y, x) 抛出异常，compare(x, y) 必须抛出异常。）
[...]
当 x 和 y 是相同对象时，sgn(compare(x, y)) == -sgn(compare(y, x)) 只有在对于所有 x 都是零时才能成立。
注解：
- 小问题：我认为他们应该在这里使用“denotes”而不是“designates”这个词。
英文:
The problem is that your first SortComparator implementation can never return 0.
Therefore SortComparator.compare(a, a) cannot ever return 0 as it is required to do by "the general contract" for Comparator implementations.
In fact, SortComparator.compare(a, a) will return 1.
The actual contract is in the javadoc. What it says is:
> The notation sgn(expression) designates<sup>1</sup> the mathematical signum function, which is defined to return one of -1, 0, or 1 according to whether the value of expression is negative, zero or positive.
>
> The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)
>
> [...]
The only way that sgn(compare(x, y)) == -sgn(compare(y, x)) can be true when x and y are the same object is if -sgn(compare(x, x)) is zero for all x.
<sup>1 - Nitpick: I think they should have used the word "denotes" rather than "designates" here.</sup>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论