Ошибка Java: метод сравнения нарушает общий договор

86

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

Вот что я получаю:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:835)
    at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:453)
    at java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:392)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:191)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:146)
    at java.util.Arrays.sort(Arrays.java:472)
    at java.util.Collections.sort(Collections.java:155)
    ...

А это мой компаратор:

@Override
public int compareTo(Object o) {
    if(this == o){
        return 0;
    }

    CollectionItem item = (CollectionItem) o;

    Card card1 = CardCache.getInstance().getCard(cardId);
    Card card2 = CardCache.getInstance().getCard(item.getCardId());

    if (card1.getSet() < card2.getSet()) {
        return -1;
    } else {
        if (card1.getSet() == card2.getSet()) {
            if (card1.getRarity() < card2.getRarity()) {
                return 1;
            } else {
                if (card1.getId() == card2.getId()) {
                    if (cardType > item.getCardType()) {
                        return 1;
                    } else {
                        if (cardType == item.getCardType()) {
                            return 0;
                        }
                        return -1;
                    }
                }
                return -1;
            }
        }
        return 1;
    }
}

Есть идеи?

Лакатош Дьюла
источник
Какая строка кода вызывает это исключение? Что находится в строках 835 и 453 файла ComparableTimSort.java?
Судно на воздушной подушке Full Of Eels
Мне кажется, что у вас должен быть этот метод делегировать Cardклассу: return card1.compareTo(card2)и реализовать там эту логику.
Хантер МакМиллен
2
@HovercraftFullOfEels Это класс Oracle, написанный не мной. Это исключение в этой строке. Метод очень долгий и сложный для понимания.
Lakatos Gyula
@HunterMcMillen Я не могу этого сделать. Карта содержит только статические данные карты (имя, текст и т. Д.), В то время как этот класс содержит некоторые изменяющиеся переменные, такие как тип и сумма.
Lakatos Gyula
1
После прочтения книги «Чистый код» я тоже не знаю.
Лакатош Дьюла

Ответы:

99

Сообщение об исключении на самом деле довольно информативно. В контракте он упоминает это транзитивность : если A > Bи B > Cто для любого A, Bи C: A > C. Я проверил это бумагой и карандашом, и в вашем коде, похоже, мало дыр:

if (card1.getRarity() < card2.getRarity()) {
  return 1;

вы не вернете , -1если card1.getRarity() > card2.getRarity().


if (card1.getId() == card2.getId()) {
  //...
}
return -1;

Вы вернетесь, -1если идентификаторы не равны. Вы должны вернуться -1или в 1зависимости от того, какой идентификатор был больше.


Взгляните на это. Помимо того, что он намного более читабелен, я думаю, он действительно должен работать:

if (card1.getSet() > card2.getSet()) {
    return 1;
}
if (card1.getSet() < card2.getSet()) {
    return -1;
};
if (card1.getRarity() < card2.getRarity()) {
    return 1;
}
if (card1.getRarity() > card2.getRarity()) {
    return -1;
}
if (card1.getId() > card2.getId()) {
    return 1;
}
if (card1.getId() < card2.getId()) {
    return -1;
}
return cardType - item.getCardType();  //watch out for overflow!
Томаш Нуркевич
источник
15
Фактически, приведенный вами пример не нарушает транзитивность, но правило sgn (compare (x, y)) == -sgn (compare (y, x)), как указано в docs.oracle.com/javase/7/docs/ api / java / util /… - это антисимметрия с математической точки зрения.
Hans-Peter Störr
1
Я бы посоветовал использовать if (card1.getSet() != card2.getSet()) return card1.getSet() > card2.getSet() ? 1 : -1;для большей скорости, если кому-то интересно.
maaartinus 01
Я столкнулся с этим, и это была проблема симметрии в моем компараторе. Трудно было диагностировать то, что моей слабостью было первое поле (проверка логического поля, а не правильное сравнение), которое не проверяло истинность обоих полей. Однако это было обнаружено только после того, как я добавил последующее подчиненное сравнение, которое должно было нарушить порядок сортировки.
Thomas W
1
@maaartinus спасибо за ваше предложение! Это было идеально для меня :)
Sonhja
46

Вы можете использовать следующий класс, чтобы выявить ошибки транзитивности в ваших компараторах:

/**
 * @author Gili Tzabari
 */
public final class Comparators
{
    /**
     * Verify that a comparator is transitive.
     *
     * @param <T>        the type being compared
     * @param comparator the comparator to test
     * @param elements   the elements to test against
     * @throws AssertionError if the comparator is not transitive
     */
    public static <T> void verifyTransitivity(Comparator<T> comparator, Collection<T> elements)
    {
        for (T first: elements)
        {
            for (T second: elements)
            {
                int result1 = comparator.compare(first, second);
                int result2 = comparator.compare(second, first);
                if (result1 != -result2)
                {
                    // Uncomment the following line to step through the failed case
                    //comparator.compare(first, second);
                    throw new AssertionError("compare(" + first + ", " + second + ") == " + result1 +
                        " but swapping the parameters returns " + result2);
                }
            }
        }
        for (T first: elements)
        {
            for (T second: elements)
            {
                int firstGreaterThanSecond = comparator.compare(first, second);
                if (firstGreaterThanSecond <= 0)
                    continue;
                for (T third: elements)
                {
                    int secondGreaterThanThird = comparator.compare(second, third);
                    if (secondGreaterThanThird <= 0)
                        continue;
                    int firstGreaterThanThird = comparator.compare(first, third);
                    if (firstGreaterThanThird <= 0)
                    {
                        // Uncomment the following line to step through the failed case
                        //comparator.compare(first, third);
                        throw new AssertionError("compare(" + first + ", " + second + ") > 0, " +
                            "compare(" + second + ", " + third + ") > 0, but compare(" + first + ", " + third + ") == " +
                            firstGreaterThanThird);
                    }
                }
            }
        }
    }

    /**
     * Prevent construction.
     */
    private Comparators()
    {
    }
}

Просто вызовите Comparators.verifyTransitivity(myComparator, myCollection)код, который не работает.

Гили
источник
3
Этот код проверяет compare (a, b) = - compare (b, c). Он не проверяет, что если compare (a, b)> 0 && compare (b, c)> 0, то compare (a, c)> 0
Олаф Ахтховен
3
Я действительно нашел ваш класс очень и очень полезным. Благодарю.
crigore
Спасибо, мне пришлось вернуться и проголосовать за ответ, так как этот класс очень полезен при отладке компаратора, а не только для упомянутой здесь цели, так как его можно изменить и для проверки других обстоятельств!
Jaco-Ben
37

Это также как-то связано с версией JDK. Если он хорошо работает в JDK6, возможно, у него будет проблема в JDK 7, описанная вами, потому что метод реализации в jdk 7 был изменен.

Посмотри на это:

Описание: алгоритм сортировки, используемый java.util.Arrays.sortи (косвенно), java.util.Collections.sortбыл заменен. Новая реализация сортировки может выдать ошибку, IllegalArgumentExceptionесли обнаружит, Comparableчто нарушает Comparableконтракт. Предыдущая реализация молча игнорировала такую ​​ситуацию. Если требуется предыдущее поведение, вы можете использовать новое системное свойство java.util.Arrays.useLegacyMergeSort,, для восстановления предыдущего поведения сортировки слиянием.

Я не знаю точной причины. Однако, если вы добавите код до использования sort. Все будет хорошо.

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
Джастин Сиви
источник
1
Проблема заключалась в логике, которую я использовал для сравнения. Я поддержу это, надеюсь, это поможет тем, кто ищет такого рода проблемы.
Lakatos Gyula
10
Это следует использовать только в качестве быстрого и уродливого обходного пути, чтобы заставить все работать снова, пока вы не исправите компаратор. Если происходит исключение, это означает, что ваш компаратор неисправен, и порядок сортировки будет странным. Вы должны учитывать все правила, приведенные в docs.oracle.com/javase/7/docs/api/java/util/… .
Hans-Peter Störr
Что, если я хотел «странно»? (a,b) -> { return (new int[]{-1,1})[(int)((Math.random()*2)%2)]}Я знаю, что Collections.shuffleсуществует, но мне не нравится, когда меня слишком защищают.
Jefferey Cave
У меня старое приложение, и с JDK8 я получил эту ошибку. При использовании JDK6 он работает правильно, поэтому я просто понизил его до 6, спасибо.
Стефано Скарпанти
6

Рассмотрим следующий случай:

Во-первых, o1.compareTo(o2)называется. card1.getSet() == card2.getSet()оказывается правдой, и так оно и есть card1.getRarity() < card2.getRarity(), поэтому вы возвращаете 1.

Затем o2.compareTo(o1)называется. Опять же, card1.getSet() == card2.getSet()верно. Затем вы переходите к следующему else, тогда card1.getId() == card2.getId()оказывается, что это правда, и так оно и есть cardType > item.getCardType(). Вы снова возвращаете 1.

Исходя из этого o1 > o2, и o2 > o1. Вы нарушили контракт.

эран
источник
2
        if (card1.getRarity() < card2.getRarity()) {
            return 1;

Однако, если card2.getRarity()меньше, card1.getRarity()вы не можете вернуть -1 .

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

public int compareTo(Object o) {    
    if(this == o){
        return 0;
    }

    CollectionItem item = (CollectionItem) o;

    Card card1 = CardCache.getInstance().getCard(cardId);
    Card card2 = CardCache.getInstance().getCard(item.getCardId());
    int comp=card1.getSet() - card2.getSet();
    if (comp!=0){
        return comp;
    }
    comp=card1.getRarity() - card2.getRarity();
    if (comp!=0){
        return comp;
    }
    comp=card1.getSet() - card2.getSet();
    if (comp!=0){
        return comp;
    }   
    comp=card1.getId() - card2.getId();
    if (comp!=0){
        return comp;
    }   
    comp=card1.getCardType() - card2.getCardType();

    return comp;

    }
}
Джо
источник
1

Это также может быть ошибка OpenJDK ... (не в этом случае, но это та же ошибка)

Если кто-то вроде меня наткнется на этот ответ относительно

java.lang.IllegalArgumentException: Comparison method violates its general contract!

тогда это также может быть ошибка в Java-версии. У меня уже несколько лет работает compareTo в некоторых приложениях. Но внезапно он перестал работать и выдает ошибку после того, как все сравнения были выполнены (я сравниваю 6 атрибутов, прежде чем вернуть «0»).

Я только что нашел этот отчет об ошибке OpenJDK:

Леоле
источник
1

У меня был такой же симптом. Для меня оказалось, что другой поток изменял сравниваемые объекты, пока сортировка происходила в Stream. Чтобы решить эту проблему, я сопоставил объекты с неизменяемыми временными объектами, собрал поток во временную коллекцию и произвел сортировку.

Карл Розенбергер
источник
0

Пришлось сортировать по нескольким критериям (дата и, если такая же дата; прочее ...). То, что работало над Eclipse со старой версией Java, больше не работало на Android: метод сравнения нарушает контракт ...

Прочитав StackOverflow, я написал отдельную функцию, которую я вызвал из compare (), если даты совпадают. Эта функция вычисляет приоритет в соответствии с критериями и возвращает -1, 0 или 1 для compare (). Вроде работает сейчас.

Жан Буркхардт
источник
0

У меня такая же ошибка с классом, подобным следующему StockPickBean. Вызывается из этого кода:

List<StockPickBean> beansListcatMap.getValue();
beansList.sort(StockPickBean.Comparators.VALUE);

public class StockPickBean implements Comparable<StockPickBean> {
    private double value;
    public double getValue() { return value; }
    public void setValue(double value) { this.value = value; }

    @Override
    public int compareTo(StockPickBean view) {
        return Comparators.VALUE.compare(this,view); //return 
        Comparators.SYMBOL.compare(this,view);
    }

    public static class Comparators {
        public static Comparator<StockPickBean> VALUE = (val1, val2) -> 
(int) 
         (val1.value - val2.value);
    }
}

После получения той же ошибки:

java.lang.IllegalArgumentException: метод сравнения нарушает его общий договор!

Я изменил эту строку:

public static Comparator<StockPickBean> VALUE = (val1, val2) -> (int) 
         (val1.value - val2.value);

кому:

public static Comparator<StockPickBean> VALUE = (StockPickBean spb1, 
StockPickBean spb2) -> Double.compare(spb2.value,spb1.value);

Это исправляет ошибку.

пмкент
источник
0

Я столкнулся с аналогичной проблемой, когда пытался отсортировать n x 2 2D arrayименованный contests2D-массив простых целых чисел. Это работало в большинстве случаев, но вызывало ошибку времени выполнения для одного ввода: -

Arrays.sort(contests, (row1, row2) -> {
            if (row1[0] < row2[0]) {
                return 1;
            } else return -1;
        });

Ошибка:-

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.base/java.util.TimSort.mergeHi(TimSort.java:903)
    at java.base/java.util.TimSort.mergeAt(TimSort.java:520)
    at java.base/java.util.TimSort.mergeForceCollapse(TimSort.java:461)
    at java.base/java.util.TimSort.sort(TimSort.java:254)
    at java.base/java.util.Arrays.sort(Arrays.java:1441)
    at com.hackerrank.Solution.luckBalance(Solution.java:15)
    at com.hackerrank.Solution.main(Solution.java:49)

Глядя на ответы выше, я попытался добавить условие equalsи не знаю почему, но оно сработало. Надеюсь, мы должны явно указать, что должно возвращаться для всех случаев (больше, равно и меньше):

        Arrays.sort(contests, (row1, row2) -> {
            if (row1[0] < row2[0]) {
                return 1;
            }
            if(row1[0] == row2[0]) return 0;
            return -1;
        });
Пратик Бхувания
источник