Java неожиданное исключение IllegalArgumentException при сортировке с помощью Math.abs (diff)

Question

У меня есть поведение, которого я не ожидал при сортировке списка двойников. Цель, которую я имею, состоит в том, чтобы отсортировать список двойных чисел, но когда два двойных близки друг к другу, мне наплевать на их порядок (на самом деле я использую Entry <> с Double в качестве значения, и когда два значения Double близки, я сортирую что-то еще.

Вот пример, который вызовет исключение IllegalArgumentException:

public static void main(String[] args) {
    final float probabilitySortMargin = 0.2f;
    Comparator<Double> comp = new Comparator<Double>() {
        @Override
        public int compare(Double o1, Double o2) {
            // sort on probability first
            double diff = Math.abs(o1 - o2);
            if(diff > probabilitySortMargin)
                // difference is more than desired range, sort descending
                return Double.compare(o2 , o1);
            return 0;
        }
    };

    ArrayList<Double> vals = new ArrayList<>();
    Random r = new Random(0);
    for(int i=0;i<1000;i++)
        vals.add(r.nextDouble());

    for(int i=0;i<vals.size();i++)
        for(int j=0;j<vals.size();j++)
            if(comp.compare(vals.get(i), vals.get(j)) != -1 * comp.compare(vals.get(j), vals.get(i)))
                System.out.println("Comparison failed");

    Collections.sort(vals, comp);
}

, что приводит к

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeHi(TimSort.java:899)
    at java.util.TimSort.mergeAt(TimSort.java:516)
    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)
    at some.package.Sample.main(Sample.java:10)

Почему это происходит? Еще более странно, что сообщение об ошибке «Сравнение не удалось» напечатано НЕ .

Answer 1

Ваш метод compare нарушает контракт интерфейса Comparator.

разработчик должен убедиться, что сравнение (x, y) == 0 подразумевает, что sgn (сравнение (x, z)) == sgn (сравнение (y, z)) для всех z.

compare(0.1,0.2) == 0, but sgn(compare(0.1,0.35)) != sgn(compare (0.2,0.35))

«Ошибка сравнения» никогда не печатается, поскольку ваш метод не нарушает требование sgn(compare(x, y)) ==-sgn(compare(y, x)).