JAVA_Runtime_Error: метод сравнения нарушает свой общий контракт.

Я получаю эту ошибку, когда пытаюсь отсортировать массив узлов. Я пробовал большинство решений, но ни одно из них не сработало в моем случае.

java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:866)
at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:483)
at java.util.ComparableTimSort.mergeCollapse(ComparableTimSort.java:406)
at java.util.ComparableTimSort.sort(ComparableTimSort.java:213)
at java.util.Arrays.sort(Arrays.java:1312)
at java.util.Arrays.sort(Arrays.java:1506)
at java.util.ArrayList.sort(ArrayList.java:1454)
at j...

Код для этого

static class Node implements Comparable<Node>
{
    int key;
    int value;
    int double_value;

    public Node(int key , int value , int double_value)
    {
        this.key = key;
        this.value = value;
        this.double_value = double_value;
    }

    public int compareTo(Node node)
    {
        if(double_value < node.double_value)
            return 1;
        else if(double_value > node.double_value)
            return -1;

        return -1;
    }
}

Это работает для небольших входов, но когда количество входов велико, выдает эту ошибку. Я также читал о правиле транзитивности в методе сравнения, но я не могу понять, как оно применяется в этом случае.

Заранее спасибо.


java collections comparable
person Sanjay Chandlekar    schedule 23.05.2017    source источник
comment
Вы возвращаете -1, если два узла имеют одинаковые значения, что означает, что узел может быть одновременно меньше и больше, чем какой-либо другой узел, в зависимости от того, в каком порядке вы сравниваете. Это действительно нарушает контракт Comparable.compareTo (и здравый смысл тоже нарушается, если уж на то пошло). Для простого случая сравнения двойников лучше использовать метод Double.compare.   -  person M. Prokhorov    schedule 23.05.2017
comment
Ваш compareTo никогда не возвращает 0, чтобы указать, что они одинаковы, и вы также должны переопределить equals(), чтобы два узла, содержащие одно и то же значение double_value n1.equals(n2), возвращали true. Когда вы переопределяете равенство, вы также должны переопределять hashcode()   -  person Stephen P    schedule 23.05.2017
comment
Пожалуйста, без подчеркивания! Следуйте соглашению об именах Java и замените double_value на doubleValue.   -  person MC Emperor    schedule 23.05.2017
comment
Идентификаторы должны представлять цель и роль, а не (неправильно) реализацию, и должны быть написаны в соответствии с соглашениями об именах Java.   -  person Lew Bloch    schedule 23.05.2017

Ответы (1)


arrow_upward
3
arrow_downward

Поскольку вы на самом деле сравниваете значения int (несмотря на то, что оно называется double_value), у вас может быть очень простой метод compareTo.

public int compareTo(Node node)
{
    return this.double_value - node.double_value;
}

Вам не нужно возвращать -1, 0 или +1 — подойдет любое отрицательное или положительное значение.
В документации для compareTo() говорится:

Сравнивает этот объект с указанным объектом для порядка. Возвращает отрицательное целое число, ноль или положительное целое число, поскольку этот объект меньше, равен или больше указанного объекта.

So

Node node1 = new Node(5, 5, 5);
Node node2 = new Node(7, 7, 7);
System.out.println( node1.compareTo(node2) );

даст -2, потому что 5 меньше 7.

Когда вы переопределяете compareTo, вы также должны переопределять .equals(Node other), а когда вы переопределяете equals, вы должны также переопределяет hashCode().

Обновление для повышения безопасности в соответствии с комментарием Криса Паркера, это восходит к использованию -1, 0, 1 для результатов:

public int compareTo(Node other)
{
    final long m = (long) this.double_value = (long) other.double_value;
    return m < 0 ? -1 :
           m > 0 ?  1 :
           0;
}
person Stephen P    schedule 23.05.2017
comment
Будьте осторожны, используя вычитание для сравнения. В зависимости от содержащихся чисел вы можете превысить значение 32-битного целого числа со знаком, и переполнение приведет к недопустимому возврату. - person Chris Parker; 23.05.2017
comment
Это правда, @Chris ... вы можете получить Integer.MIN_VALUE - Integer.MAX_VALUE, который неправильно выходит как 1. Вы можете использовать расширение, например long m = (long)a - (long)b;, чтобы сделать его более безопасным. - person Stephen P; 24.05.2017