«Метод сравнения нарушает его общий договор!»

188

Может кто-нибудь объяснить мне простыми словами, почему этот код выдает исключение «Метод сравнения нарушает свой общий контракт!» И как мне это исправить?

private int compareParents(Foo s1, Foo s2) {
    if (s1.getParent() == s2) return -1;
    if (s2.getParent() == s1) return 1;
    return 0;
}
n00bster
источник
1
Как называется и класс исключения? Это IllegalArgumentException? Если бы мне пришлось угадывать, я бы подумал, что вы должны делать s1.getParent().equals(s2)вместо s1.getParent() == s2.
Freiheit
И исключение, которое выбрасывается также.
Мэтью Фарвелл
2
Я не знаю много о Java или об API сравнения Java, но этот метод сравнения кажется совершенно неправильным. Предположим s1, что родитель s2, а s2не родитель s1. Тогда compareParents(s1, s2)есть 0, но compareParents(s2, s1)есть 1. Это не имеет смысла. (Кроме того, он не транзитивен, как aix, упомянутый ниже.)
mqp
4
Эта ошибка, по-видимому, создается только определенной библиотекой cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/src/share/…
Питер Лори
в Java вы можете использовать равно (вернуть логическое значение) или сравнить (вернуть -1, 0 или +1). Переопределите эти функции в своем классе Foo, и после этого вы можете проверить s1.getParent (). Equals (s2) ...
Mualig

Ответы:

261

Ваш компаратор не является переходным.

Позвольте Aбыть родителем B, и Bбыть родителем C. Так как A > Bи B > C, то это должно быть так , что A > C. Однако, если ваш компаратор вызывается Aи C, он будет возвращать ноль, что означает A == C. Это нарушает договор и, следовательно, создает исключение.

Библиотеке довольно приятно обнаружить это и дать вам знать, а не вести себя беспорядочно.

Один из способов удовлетворить требование транзитивности compareParents()состоит в том, чтобы обходить getParent()цепь, а не смотреть только на непосредственного предка.

NPE
источник
3
Введенный в Java 7 java.util.Arrays.sort stackoverflow.com/questions/7849539/…
leonbloy
46
Тот факт, что библиотека обнаруживает это, потрясающий. Кто-то на солнце заслуживает того, чтобы выбросить гиганта. Пожалуйста .
Qix - МОНИКА БЫЛА ПОВРЕЖДЕНА
Можете ли вы обобщить этот ответ немного, чтобы сделать этот вопрос более полезным в качестве справочного поста?
Бернхард Баркер
1
@Qix - насколько я люблю Sun, это было добавлено в Java 7 под баннером Oracle
isapir
1
@isapir Черт! Хороший улов.
Qix - МОНИКА БЫЛА ПОВРЕЖДЕНА
38

Просто потому, что это то, что я получил, когда я погуглил эту ошибку, моя проблема заключалась в том, что я имел

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

value >= other.valueдолжен (очевидно) на самом деле быть value > other.valueтак , что вы можете вернуть 0 с равными объектами.

you786
источник
7
Я должен добавить, что если кто-то из вас valueявляется NaN (если valueэто doubleили float), он также потерпит неудачу.
Матье
23

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

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

Но это упускает из виду случай, когда ОБА один и два пусты, и в этом случае возвращается неправильное значение (1 вместо 0, чтобы показать совпадение), и компаратор сообщает об этом как о нарушении. Это должно было быть написано как:

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
источник
13

Даже если ваш метод CompareTo поддерживает транзитивность в теории, иногда тонкие ошибки приводят в порядок… такие как арифметическая ошибка с плавающей запятой. Это случилось со мной. это был мой код:

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;

}   

Транзитивное свойство явно выполняется, но по какой-то причине я получил исключение IllegalArgumentException. И оказывается, что из-за крошечных ошибок в арифметике с плавающей точкой ошибки округления приводят к тому, что переходное свойство нарушается там, где не должно! Поэтому я переписал код, чтобы учесть действительно крошечные различия 0, и это сработало:

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;
}   
Али Мизан
источник
2
Это было полезно! Мой код был логически в порядке, но произошла ошибка из-за проблемы точности.
JSong
6

В нашем случае мы получали эту ошибку, потому что мы случайно переключили порядок сравнения s1 и s2. Так что следите за этим. Это было очевидно намного сложнее, чем следующее, но это иллюстрация:

s1 == s2   
    return 0;
s2 > s1 
    return 1;
s1 < s2 
    return -1;
Дядя ирох
источник
4

В моем случае я делал что-то вроде следующего:

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

Что я забыл проверить, так это то, что a.someField и b.someField равны нулю.

jc12
источник
3

Java не проверяет согласованность в строгом смысле, а только уведомляет вас, если возникнут серьезные проблемы. Также это не дает вам много информации об ошибке.

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

/**
 * @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));
    }
  }
}
Мартин
источник
Просто вызовите метод checkConsitency со списком параметров и компаратором.
Мартин
Ваш код не компилируется. Классы Compare, Convert(и потенциально другие) не определены. Пожалуйста, обновите фрагмент кода с помощью отдельного примера.
Гили
Вы должны исправить опечатку checkConsi(s)tencyи удалить все избыточные @paramобъявления, чтобы сделать код более читабельным.
Роланд Иллиг
3

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

if(( A==null ) && ( B==null )
  return +1;//WRONG: two null values should return 0!!!
keesp
источник
2

Если compareParents(s1, s2) == -1тогдаcompareParents(s2, s1) == 1 ожидается. С вашим кодом это не всегда так.

Конкретно если s1.getParent() == s2 && s2.getParent() == s1. Это всего лишь одна из возможных проблем.

Андрей Караиванский
источник
1

Редактирование конфигурации VM работало для меня.

-Djava.util.Arrays.useLegacyMergeSort=true
Ришав Рой
источник
Пожалуйста, проверьте, чтобы моя попытка помочь вам с форматированием ничего не сломала. Я не уверен относительно -начала предложенного решения. Возможно, вы намеревались создать что-то вроде списка из одного пункта.
Юннощ
2
Также, пожалуйста, объясните, как это помогает с описанной проблемой. В настоящее время это практически только кодовый ответ.
Юннощ
0

Вы не можете сравнивать данные объекта следующим образом: s1.getParent() == s2- это будет сравнивать ссылки на объекты. Вы должны переопределить equals functionкласс Foo, а затем сравнить их следующим образомs1.getParent().equals(s2)

erimerturk
источник
Нет, на самом деле, я думаю, что OP пытается отсортировать какой-то список и хочет на самом деле сравнить ссылки.
Эдвард Фальк,