„Metoda porównawcza narusza ogólną umowę!”

187

Czy ktoś może mi wyjaśnić w prosty sposób, dlaczego ten kod generuje wyjątek „Metoda porównawcza narusza ogólną umowę!” I jak to naprawić?

private int compareParents(Foo s1, Foo s2) {
    if (s1.getParent() == s2) return -1;
    if (s2.getParent() == s1) return 1;
    return 0;
}
n00bster
źródło
1
Jaka jest nazwa i klasa wyjątku? Czy jest to wyjątek IllegalArgumentException? Gdybym musiał zgadywać, pomyślałbym, że powinieneś to robić s1.getParent().equals(s2)zamiast s1.getParent() == s2.
Freiheit
I zgłoszony wyjątek.
Matthew Farwell
2
Nie wiem dużo o Javie ani o interfejsach API do porównywania Java, ale ta metoda porównywania wydaje się zupełnie zła. Załóżmy, że s1jest rodzicem s2i s2nie jest rodzicem s1. Więc compareParents(s1, s2)jest 0, ale compareParents(s2, s1)jest 1. To nie ma sensu. (Ponadto nie jest przechodni, jak wspomniano poniżej aix.)
mqp
4
Ten błąd wydaje się być spowodowany tylko przez określoną bibliotekę cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/src/share/…
Peter Lawrey
w java możesz użyć równości (zwróć wartość logiczną) lub CompareTo (zwróć -1, 0 lub +1). Zastąp tę funkcję w swojej klasie Foo, a następnie możesz sprawdzić s1.getParent (). Equals (s2) ...
Mualig 30.11.11

Odpowiedzi:

261

Twój komparator nie jest przechodni.

Pozwól Abyć rodzicem Bi Bbyć rodzicem C. Odtąd A > Bi B > Cwtedy musi tak być A > C. Jednak jeśli twój komparator zostanie wywołany Ai Czwróci zero, co oznacza A == C. Narusza to umowę i dlatego zgłasza wyjątek.

Biblioteką jest raczej miło to wykryć i powiadomić, niż zachowywać się niepoprawnie.

Jednym ze sposobów spełnienia wymogu przechodniości compareParents()jest przejście getParent()łańcucha zamiast patrzenia tylko na bezpośredniego przodka.

NPE
źródło
3
Wprowadzono w java.util.Arrays.sort stackoverflow.com/questions/7849539/
leonbloy
46
Fakt, że biblioteka to wykrywa, jest niesamowity. Ktoś na słońcu zasługuje na wyrzucenie giganta. Nie ma za co .
Qix - MONICA MISTREATED
Czy możesz trochę uogólnić tę odpowiedź, aby uczynić to pytanie bardziej użytecznym jako post referencyjny?
Bernhard Barker,
1
@Qix - o ile kocham Sun, zostało dodane w Javie 7 pod sztandarem Oracle
isapir
1
@isapir Damn! Dobry chwyt
Qix - MONICA MISTREATED
38

Tylko dlatego, że właśnie to dostałem, kiedy przejrzałem ten błąd, mój problem polegał na tym, że go miałem

if (value < other.value)
  return -1;
else if (value >= other.value)
  return 1;
else
  return 0;

value >= other.valuepowinien (oczywiście) rzeczywiście być value > other.valuetak, że rzeczywiście można wrócić 0 z jednakowych przedmiotów.

ty786
źródło
7
Muszę dodać, że jeśli któryś z was valuejest NaN (jeśli valuejest a doublelub float), to również by się nie udało.
Matthieu,
22

Naruszenie umowy często oznacza, że ​​komparator nie zapewnia poprawnej lub spójnej wartości przy porównywaniu obiektów. Na przykład możesz chcieć wykonać porównanie ciągów i zmusić puste ciągi do sortowania do końca za pomocą:

if ( one.length() == 0 ) {
    return 1;                   // empty string sorts last
}
if ( two.length() == 0 ) {
    return -1;                  // empty string sorts last                  
}
return one.compareToIgnoreCase( two );

Ale pomija się przypadek, w którym ZARÓWNO jeden i dwa są puste - w takim przypadku zwracana jest niewłaściwa wartość (1 zamiast 0, aby pokazać dopasowanie), a komparator zgłasza to jako naruszenie. Powinien być napisany jako:

if ( one.length() == 0 ) {
    if ( two.length() == 0 ) {
        return 0;               // BOth empty - so indicate
    }
    return 1;                   // empty string sorts last
}
if ( two.length() == 0 ) {
    return -1;                  // empty string sorts last                  
}
return one.compareToIgnoreCase( two );
CESDewar
źródło
13

Nawet jeśli twoje porównanie ma teoretycznie charakter przechodni, czasami subtelne błędy psują rzeczy ... na przykład błąd arytmetyczny zmiennoprzecinkowy. Zdarzyło mi się. to był mój kod:

public int compareTo(tfidfContainer compareTfidf) {
    //descending order
    if (this.tfidf > compareTfidf.tfidf)
        return -1;
    else if (this.tfidf < compareTfidf.tfidf)
        return 1;
    else
        return 0;

}   

Właściwość przechodnia wyraźnie zachowuje się, ale z jakiegoś powodu otrzymywałem IllegalArgumentException. I okazuje się, że z powodu drobnych błędów w arytmetyki zmiennoprzecinkowej błędy zaokrąglania powodowały, że właściwość przechodnia pękała tam, gdzie nie powinna! Przepisałem więc kod, aby uwzględnić naprawdę małe różnice 0 i zadziałało:

public int compareTo(tfidfContainer compareTfidf) {
    //descending order
    if ((this.tfidf - compareTfidf.tfidf) < .000000001)
        return 0;
    if (this.tfidf > compareTfidf.tfidf)
        return -1;
    else if (this.tfidf < compareTfidf.tfidf)
        return 1;
    return 0;
}   
Ali Mizan
źródło
2
To było pomocne! Mój kod był logicznie poprawny, ale wystąpił błąd z powodu problemu z precyzją.
JSong
6

W naszym przypadku otrzymywaliśmy ten błąd, ponieważ przypadkowo odwróciliśmy kolejność porównywania s1 i s2. Więc uważaj na to. Było to oczywiście o wiele bardziej skomplikowane niż poniższe, ale to jest ilustracja:

s1 == s2   
    return 0;
s2 > s1 
    return 1;
s1 < s2 
    return -1;
Wujek Iroh
źródło
3

Java nie sprawdza spójności w ścisłym znaczeniu, tylko powiadamia cię, jeśli napotka poważne kłopoty. Również nie daje dużo informacji o błędzie.

Zaskoczyło mnie to, co dzieje się w moim sortowniku i zachowałem ścisłą spójność Checker, może to ci pomoże:

/**
 * @param dailyReports
 * @param comparator
 */
public static <T> void checkConsitency(final List<T> dailyReports, final Comparator<T> comparator) {
  final Map<T, List<T>> objectMapSmallerOnes = new HashMap<T, List<T>>();

  iterateDistinctPairs(dailyReports.iterator(), new IPairIteratorCallback<T>() {
    /**
     * @param o1
     * @param o2
     */
    @Override
    public void pair(T o1, T o2) {
      final int diff = comparator.compare(o1, o2);
      if (diff < Compare.EQUAL) {
        checkConsistency(objectMapSmallerOnes, o1, o2);
        getListSafely(objectMapSmallerOnes, o2).add(o1);
      } else if (Compare.EQUAL < diff) {
        checkConsistency(objectMapSmallerOnes, o2, o1);
        getListSafely(objectMapSmallerOnes, o1).add(o2);
      } else {
        throw new IllegalStateException("Equals not expected?");
      }
    }
  });
}

/**
 * @param objectMapSmallerOnes
 * @param o1
 * @param o2
 */
static <T> void checkConsistency(final Map<T, List<T>> objectMapSmallerOnes, T o1, T o2) {
  final List<T> smallerThan = objectMapSmallerOnes.get(o1);

  if (smallerThan != null) {
    for (final T o : smallerThan) {
      if (o == o2) {
        throw new IllegalStateException(o2 + "  cannot be smaller than " + o1 + " if it's supposed to be vice versa.");
      }
      checkConsistency(objectMapSmallerOnes, o, o2);
    }
  }
}

/**
 * @param keyMapValues 
 * @param key 
 * @param <Key> 
 * @param <Value> 
 * @return List<Value>
 */ 
public static <Key, Value> List<Value> getListSafely(Map<Key, List<Value>> keyMapValues, Key key) {
  List<Value> values = keyMapValues.get(key);

  if (values == null) {
    keyMapValues.put(key, values = new LinkedList<Value>());
  }

  return values;
}

/**
 * @author Oku
 *
 * @param <T>
 */
public interface IPairIteratorCallback<T> {
  /**
   * @param o1
   * @param o2
   */
  void pair(T o1, T o2);
}

/**
 * 
 * Iterates through each distinct unordered pair formed by the elements of a given iterator
 *
 * @param it
 * @param callback
 */
public static <T> void iterateDistinctPairs(final Iterator<T> it, IPairIteratorCallback<T> callback) {
  List<T> list = Convert.toMinimumArrayList(new Iterable<T>() {

    @Override
    public Iterator<T> iterator() {
      return it;
    }

  });

  for (int outerIndex = 0; outerIndex < list.size() - 1; outerIndex++) {
    for (int innerIndex = outerIndex + 1; innerIndex < list.size(); innerIndex++) {
      callback.pair(list.get(outerIndex), list.get(innerIndex));
    }
  }
}
Jaskółka oknówka
źródło
Po prostu wywołaj metodę checkConsitency z listą parametrów i komparatorem.
Martin
Twój kod się nie kompiluje. Ćwiczenia Compare, Convert(i potencjalnie inne) nie są zdefiniowane. Zaktualizuj fragment kodu samodzielnym przykładem.
Gili,
Powinieneś naprawić literówkę checkConsi(s)tency i usunąć wszystkie zbędne @paramdeklaracje, aby kod był bardziej czytelny.
Roland Illig,
3

W moim przypadku robiłem coś takiego:

if (a.someField == null) {
    return 1;
}

if (b.someField == null) {
    return -1;
}

if (a.someField.equals(b.someField)) {
    return a.someOtherField.compareTo(b.someOtherField);
}

return a.someField.compareTo(b.someField);

Zapomniałem sprawdzić, kiedy zarówno a.someField, jak i b.someField są zerowe.

jc12
źródło
3

Widziałem, jak to się dzieje w kodzie, w którym przeprowadzano często powtarzające się sprawdzanie wartości pustych:

if(( A==null ) && ( B==null )
  return +1;//WRONG: two null values should return 0!!!
keesp
źródło
2

Jeśli compareParents(s1, s2) == -1takcompareParents(s2, s1) == 1 jest oczekiwane. W twoim kodzie nie zawsze jest to prawda.

Szczególnie jeśli s1.getParent() == s2 && s2.getParent() == s1. To tylko jeden z możliwych problemów.

Andrii Karaivanskyi
źródło
1

Edycja konfiguracji VM działała dla mnie.

-Djava.util.Arrays.useLegacyMergeSort=true
Rishav Roy
źródło
Proszę dokładnie sprawdzić, czy moja próba pomocy w formatowaniu niczego nie zepsuła. Nie jestem pewien co -do początku proponowanego rozwiązania. Być może zamiast tego zamierzałeś stworzyć jedną punktowaną listę punktowaną.
Yunnosch,
2
Proszę również wyjaśnić, w jaki sposób pomaga to w opisanym problemie. Obecnie jest to praktycznie tylko odpowiedź na kod.
Yunnosch,
0

Nie można porównywać danych obiektu w następujący sposób: s1.getParent() == s2- spowoduje to porównanie odniesień do obiektu. Powinieneś przesłonić equals functionklasę Foo, a następnie porównać je w ten sposóbs1.getParent().equals(s2)

erimerturk
źródło
Nie, właściwie myślę, że OP próbuje posortować jakąś listę i chce faktycznie porównać referencje.
Edward Falk