无法复制:“比较方法违反了它的一般约定！"

2022-01-25 00:00:00 sorting exception compare java comparator

我收到以下错误:比较方法违反了它的一般合同！"使用以下比较器时，但是我无法使用 jUnit 复制异常.我想知道是什么导致了这个问题以及如何复制它.有其他人有同样问题但不知道如何复制它的例子.

I receive the following error: "Comparison method violates its general contract!" when using the following comparator, however I am unable to replicate the exception using jUnit. I'd like to know what caused this issue and how to replicate it. There are examples of others having the same problem but not how to replicate it.

public class DtoComparator implements Comparator<Dto> {

    @Override
    public int compare(Dto r1, Dto r2) {

        int value = 0;

        value = r1.getOrder() - r2.getOrder();

        if (value == 0 && !isValueNull(r1.getDate(), r2.getDate()))
            value = r1.getDate().compareTo(r2.getDate());

        return value;
    }

    private boolean isValueNull(Date date, Date date2) {
        return date == null || date2 == null;
    }
}

代码调用使用:

Collections.sort(dtos, new DtoComparator());

感谢您的帮助.

额外信息:该错误似乎发生在 Java utils 中的 TimSort 类中以及来自名为 mergeLo 的方法中.链接:http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/TimSort.java#TimSort.mergeLo%28int%2Cint%2Cint%2Cint%29

Extra info: The error seemed to occur in the TimSort class inside Java utils and from within a method called mergeLo. Link: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/TimSort.java#TimSort.mergeLo%28int%2Cint%2Cint%2Cint%29

推荐答案

来自compare的文档.

实施者必须确保所有 x 和 y 的 sgn(x.compareTo(y)) == -sgn(y.compareTo(x))

The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y

基于减法的比较器不满足此条件.这是因为减法会溢出.例如

Subtraction-based comparators do not meet this condition. This is because the subtraction can overflow. For example

Integer.MIN_VALUE - 0
0 - Integer.MIN_VALUE

都是负数.

你处理Date的方式也有问题.来自compare的文档:

There is also a problem with the way you have dealt with Dates. From the documentation of compare:

最后，实现者必须确保 x.compareTo(y)==0 暗示 sgn(x.compareTo(z)) == sgn(y.compareTo(z))，适用于所有 z.

Finally, the implementor must ensure that x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.

您的 compare 方法打破了这一点.例如，如果 x 是 null，y 是 1970 年 1 月 1 日，z 是 1970 年 1 月 2 日，那么

Your compare method breaks this. For example, if x is null, y is January 1st 1970 and z is January 2nd 1970, then

compare(x, y) == 0  // x == null
compare(x, z) == 0  // x == null
compare(y, z) == -1 // January 1st is before January 2nd.

我会这样写方法:

@Override
public int compare(Dto r1, Dto r2) {

    int value = Integer.compare(r1.getOrder(), r2.getOrder());
    if (value != 0)
        return value;
    Date date1 = r1.getDate();
    Date date2 = r2.getDate();
    if (date1 == null && date2 == null)
        return 0;
    if (date1 == null)
        return -1;
    if (date2 == null)
        return 1;
    return date1.compareTo(date2);
}

我已设法重现该问题，但仅限于长度至少为 32 的 List.有关为什么需要大小至少为 32 的 List 的说明，请参阅此链接.为什么这个使用 Collections.sort 的程序只对大小为 32 或更大的列表失败?

I have managed to reproduce the problem, but only for Lists of length at least 32. See this link for an explanation of why a List of size at least 32 is required. Why does this program using Collections.sort only fail for lists of size 32 or more?

public class Main {

    private static final class NumAndDate {
        private final int num;
        private final Date date;

        NumAndDate(int num, Date date) {
            this.num = num;
            this.date = date;
        }
    }

    public static final class NumAndDateComparator implements Comparator<NumAndDate> {

        @Override
        public int compare(NumAndDate r1, NumAndDate r2) {

            int value = 0;

            value = r1.num - r2.num;

            if (value == 0 && !isValueNull(r1.date, r2.date))
                value = r1.date.compareTo(r2.date);

            return value;
        }

        private boolean isValueNull(Date date, Date date2) {
            return date == null || date2 == null;
        }
    }

    public static void main(String[] args) {
        NumAndDate[] array = {
                new NumAndDate(0, new Date(0)),
                new NumAndDate(0, new Date(1)), 
                new NumAndDate(0, null)
        };
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 10000; j++) {
                List<NumAndDate> list = new ArrayList<>();
                int[] arr = new int[i];
                for (int k = 0; k < i; k++) {
                    int rand = random.nextInt(3);
                    arr[k] = rand;
                    list.add(array[rand]);
                }
                try {
                    Collections.sort(list, new NumAndDateComparator());
                } catch (Exception e) {
                    System.out.println(arr.length + " " + Arrays.toString(arr));
                    return;
                }
            }
        }
    }
}

相关文章