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

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

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.

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.

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

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

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;

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

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.

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!!!

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.

Edycja konfiguracji VM działała dla mnie.

-Djava.util.Arrays.useLegacyMergeSort=true

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)