Błąd Java: metoda porównawcza narusza jej umowę ogólną

86

Widziałem wiele pytań na ten temat i próbowałem rozwiązać problem, ale po godzinie googlowania i wielu prób i błędów nadal nie mogę tego naprawić. Mam nadzieję, że niektórzy z was złapią problem.

Oto, co otrzymuję:

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)
    ...

A to jest moja komparator:

@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;
    }
}

Dowolny pomysł?

java  compare  migration  java-7  comparator 
— Lakatos Gyula
źródło
Jaka linia kodu powoduje zgłoszenie tego wyjątku? Co znajduje się w liniach 835 i 453 strony ComparableTimSort.java?
— Poduszkowiec pełen węgorzy,
Wydaje mi się, że powinieneś mieć tę metodę delegowaną do Cardklasy: return card1.compareTo(card2)i zaimplementuj tam tę logikę.
— Hunter McMillen,
2
@HovercraftFullOfEels To klasa od Oracle, nie została przeze mnie zmartwiona. To rzuca wyjątek w tej linii. Metoda jest bardzo długa i wygląda na trudną do zrozumienia.
— Lakatos Gyula,
@HunterMcMillen Nie mogę tego zrobić. Karta zawiera tylko statyczne dane karty (nazwa, tekst itp.), Podczas gdy ta klasa zawiera zmienne zmieniające się, takie jak typ i kwota.
— Lakatos Gyula,
1
Po przeczytaniu książki Clean Code też nie wiem.
— Lakatos Gyula

Odpowiedzi:

99

Komunikat o wyjątku jest właściwie dość opisowy. Umowa wymienia jest przechodniości : jeśli A > Ba B > Cnastępnie dla każdego A, Bi C: A > C. Sprawdziłem to na papierze i ołówku i wydaje się, że twój kod ma kilka dziur:

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

nie wrócisz, -1jeśli card1.getRarity() > card2.getRarity().

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

Wrócisz -1jeśli identyfikatory nie są równe. Powinieneś wrócić -1lub w 1zależności od tego, który identyfikator był większy.

Popatrz na to. Oprócz tego, że jest znacznie bardziej czytelny, myślę, że powinien faktycznie działać:

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!
— Tomasz Nurkiewicz
źródło
15
Właściwie podany przez ciebie przykład nie narusza przechodniości, ale reguła sgn (porównaj (x, y)) == -sgn (porównaj (y, x)) zgodnie z docs.oracle.com/javase/7/docs/ api / java / util /… - matematycznie jest to antysymetria.
— Hans-Peter Störr
1
Proponuję użyć if (card1.getSet() != card2.getSet()) return card1.getSet() > card2.getSet() ? 1 : -1;dla większej szybkości, jeśli komuś to zależy.
— maaartinus
Napotkałem to i był to problem symetrii w moim komparatorze. Najtrudniejszą częścią do zdiagnozowania było to, że moja słabość była pierwszym polem (boolowskim sprawdzianem pola, a nie odpowiednim porównaniem), które nie sprawdzało, czy oba są prawdziwe. Zostało to jednak ujawnione dopiero po dodaniu kolejnego porównania podrzędnego, które musiało zakłócić porządek sortowania.
— Thomas W
1
@maaartinus dzięki za sugestię! To było dla mnie idealne :)
— Sonhja
46

Możesz użyć następującej klasy, aby wskazać błędy przechodniości w komparatorach:

/**
 * @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()
    {
    }
}

Po prostu wywołaj Comparators.verifyTransitivity(myComparator, myCollection)przed kodem, który się nie powiedzie.

— Gili
źródło
3
Ten kod weryfikuje porównanie (a, b) = - porównaj (b, c). Nie sprawdza, czy jeśli porównaj (a, b)> 0 && porównaj (b, c)> 0, to porównaj (a, c)> 0
— Olaf Achthoven
3
Naprawdę uważam, że twoja klasa jest bardzo, bardzo przydatna. Dzięki.
— crigore
Dziękuję, musiałem wrócić i zagłosować za odpowiedź, ponieważ ta klasa jest bardzo przydatna podczas debugowania komparatora, a nie tylko w celu wymienionym tutaj, ponieważ można ją zmienić, aby przetestować również inne okoliczności!
— Jaco-Ben Vosloo
37

Ma to również coś wspólnego z wersją JDK. Jeśli działa dobrze w JDK6, może będzie miał problem w JDK 7 opisany przez Ciebie, ponieważ metoda implementacji w jdk 7 została zmieniona.

Spójrz na to:

Opis: algorytm sortowania używany przez java.util.Arrays.sorti (pośrednio) java.util.Collections.sortzostał zastąpiony. Nowa implementacja sortowania może zgłosić, IllegalArgumentExceptionjeśli wykryje, Comparableże narusza Comparablekontrakt. Poprzednia implementacja po cichu ignorowała taką sytuację. Jeśli wymagane jest poprzednie zachowanie, można użyć nowej właściwości systemowej java.util.Arrays.useLegacyMergeSort, aby przywrócić poprzednie zachowanie scalania.

Nie znam dokładnego powodu. Jeśli jednak dodasz kod przed użyciem sort. Będzie dobrze.

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
— Justin Civi
źródło
1
Problem tkwił w logice, której użyłem do porównania. Głosuję za tym, mam nadzieję, że może to pomóc komuś, kto szuka tego typu problemu.
— Lakatos Gyula
10
Powinno to być używane tylko jako szybkie i brzydkie obejście, aby wszystko działało ponownie, dopóki nie naprawisz komparatora. Jeśli zdarzy się wyjątek, oznacza to, że komparator jest wadliwy, a kolejność sortowania będzie dziwna. Musisz wziąć pod uwagę wszystkie zasady podane w docs.oracle.com/javase/7/docs/api/java/util/… .
— Hans-Peter Störr
A jeśli to „dziwne” jest tym, o co mi chodzi? (a,b) -> { return (new int[]{-1,1})[(int)((Math.random()*2)%2)]}Wiem, że Collections.shuffleistnieje, ale nie lubię być nadmiernie chroniony.
— Jefferey Cave
Mam starą aplikację iz JDK8 mam ten błąd. Używając JDK6 działa poprawnie, więc po prostu obniżam wersję do 6, dzięki.
— Stefano Scarpanti
6

Rozważ następujący przypadek:

Najpierw o1.compareTo(o2)nazywa się. card1.getSet() == card2.getSet()tak się składa, że ​​tak jest card1.getRarity() < card2.getRarity(), więc zwracasz 1.

Następnie o2.compareTo(o1)nazywa się. To znowu card1.getSet() == card2.getSet()prawda. Następnie przechodzisz do następnego else, a card1.getId() == card2.getId()tak się składa, że ​​tak jest cardType > item.getCardType(). Zwracasz 1 ponownie.

Od tego o1 > o2, i o2 > o1. Zerwałeś kontrakt.

— eran
źródło
2 
        if (card1.getRarity() < card2.getRarity()) {
            return 1;

Jeśli jednak card2.getRarity()jest mniejsze niż, card1.getRarity()możesz nie zwrócić -1 .

Podobnie tęsknisz za innymi sprawami. Zrobiłbym to, możesz się zmienić w zależności od zamiarów:

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;

    }
}
— Joe
źródło
1

Może to być również błąd OpenJDK ... (nie w tym przypadku, ale jest to ten sam błąd)

Jeśli ktoś taki jak ja natknie się na tę odpowiedź dotyczącą

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

to może być również błąd w wersji Java. Mam porównanie do pracy od kilku lat w niektórych aplikacjach. Ale nagle przestał działać i zgłasza błąd po wykonaniu wszystkich porównań (porównuję 6 atrybutów przed zwróceniem „0”).

Teraz właśnie znalazłem ten raport o błędzie OpenJDK:

— leole
źródło
1

Miałem ten sam objaw. U mnie okazało się, że inny wątek modyfikował porównywane obiekty, podczas gdy sortowanie odbywało się w strumieniu. Aby rozwiązać ten problem, zamapowałem obiekty na niezmienne obiekty tymczasowe, zebrałem strumień do tymczasowej kolekcji i przeprowadziłem sortowanie.

— Carl Rosenberger
źródło
0

Musiałem posortować według kilku kryteriów (data i, jeśli ta sama data; inne rzeczy ...). To, co działało na Eclipse ze starszą wersją Javy, już nie działało na Androidzie: metoda porównawcza narusza kontrakt ...

Po przeczytaniu na StackOverflow napisałem osobną funkcję, którą wywołałem z compare (), jeśli daty są takie same. Ta funkcja oblicza priorytet zgodnie z kryteriami i zwraca wartość -1, 0 lub 1 w celu porównania (). Wydaje się, że teraz działa.

— Jean Burkhardt
źródło
0

Otrzymałem ten sam błąd z klasą taką jak poniżej StockPickBean. Zadzwoniono z tego kodu:

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);
    }
}

Po otrzymaniu tego samego błędu:

java.lang.IllegalArgumentException: Metoda porównawcza narusza jej ogólną umowę!

Zmieniłem tę linię:

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

do:

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

To naprawia błąd.

— pmkent
źródło
0

Napotkałem podobny problem, gdy próbowałem posortować n x 2 2D arraynazwaną conteststablicę dwuwymiarową prostych liczb całkowitych. To działało przez większość czasu, ale generowało błąd w czasie wykonywania dla jednego wejścia: -

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

Błąd:-

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)

Patrząc na powyższe odpowiedzi, próbowałem dodać warunek dla equalsi nie wiem dlaczego, ale zadziałało. Mamy nadzieję, że musimy wyraźnie określić, co powinno zostać zwrócone we wszystkich przypadkach (większe niż, równe i mniejsze niż):

        Arrays.sort(contests, (row1, row2) -> {
            if (row1[0] < row2[0]) {
                return 1;
            }
            if(row1[0] == row2[0]) return 0;
            return -1;
        });
— Prateek Bhuwania
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.