Как воспроизвести метод сравнения, нарушающий его общий контракт IllegalArgumentException

Одно из моих приложений однажды выдало исключение IllegalArgumentException, в котором говорилось, что метод Comparison нарушает его общий контракт. Я нашел несколько источников с подробным описанием проблемы, таких как http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124 и http://www.oracle.com/technetwork/java/javase/compatibility-417013.html#source и хотел исправить это в своем приложении.

Но я не могу воспроизвести проблему, поэтому не могу знать, правильно ли мое исправление.

Пытаясь воспроизвести, я попытался максимально упростить задачу и придумал небольшой класс, который выглядит так:

public class Sortee implements Comparable<Sortee>
{
  /** a value to sort by */
  public final int _x;

  public Sortee(int x)
  {
    _x = x;
  }

  public int compareTo(Sortee o)
  {
    return 1;
  }
}

Я также создал эквивалент в качестве компаратора:

public class SorteeIncorrectComparator implements Comparator<Sortee>
{
  public int compare(Sortee a, Sortee b)
  {
    return 1;
  }
}

В другом классе я создал объекты List of Sortee и вызвал варианты Collections.sort(), чтобы спровоцировать исключение IllegalStateException:

private static void sort()
{
   List<Sortee> sortees = createSortees();

   Collections.shuffle( sortees );
   Collections.sort( sortees, new SorteeIncorrectComparator() );

   Collections.shuffle( sortees );
   Collections.sort( sortees );
}

Но исключение IllegalStateException никогда не возникает.

Я пробовал это в Linux и Windows, а также в eclipse в Windows с Java 1.7.0_21, 23.21-b01 и проверил, что свойство java.util.Arrays.useLegacyMergeSort не установлено.

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

Почему я никогда не получаю исключение IllegalStateException?


java illegalstateexception comparable comparator
person sys64738    schedule 07.06.2013    source источник
comment
Я не уверен, что вижу выгоду в написании полностью нового кода для воспроизведения проблемы, возникшей в другом коде. Почему бы не опубликовать код, вызвавший исключение, и позволить нам выявить ошибки?   -  person Duncan Jones    schedule 07.06.2013

Ответы (3)


arrow_upward
1
arrow_downward

Я смог воспроизвести это, когда компаратор нарушает a=b и b=c -> a=c, тогда кажется, что timsort жалуется. Мой тест был:

List<Integer> timSortTestList = new ArrayList<Integer>();
{
    for(int i=0; i<100; ++i) {
        timSortTestList.add(i);
        timSortTestList.add(i);
        timSortTestList.add(i);
    }
    Collections.shuffle(timSortTestList, new Random(42));
}
Comparator<Integer> broken = new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        if (Math.abs(o1-o2) < 10) {
            return Compare.EQUAL; // WRONG
        }
        return Ordering.natural().compare(o1, o2);
    }
};
Collections.sort(timSortTestList, broken); // throws up

Сравните этот вопрос - возможно, есть общее правило, когда это происходит.

person Hans-Peter Störr    schedule 25.07.2014
comment
Анализ ответа на этот вопрос показал (если я правильно его интерпретирую), что метод сортировки никогда не будет выдавать исключение при сортировке коротких последовательностей. Итак, ключевой частью вашего ответа является то, что ваш список состоит из 300 элементов. - person Raedwald; 25.07.2014
comment
Оптимизированная сортировка слиянием (Comparable)TimSort будет использовать минимизированную версию (с использованием бинарной сортировки), если в массиве меньше MIN_MERGE=32 записей. Если вы укажете еще несколько элементов, это зависит от распределения кандидатов на сортировку, если они соответствуют условию (i‹10 никогда, а i‹20 всегда выдает приведенный выше код)... - person eckes; 30.03.2016

arrow_upward
0
arrow_downward

Моя реализация на самом деле была транзитивной.

Я изменил метод сравнения, чтобы он возвращал случайные значения, и это вызывает исключение.

person sys64738    schedule 10.06.2013

arrow_upward

arrow_downward

person    schedule
comment
Ахмед, не могли бы вы объяснить свое осознание? result[] - это случайные значения или здесь представлена ​​какая-то логика? Спасибо. - person dnim; 10.10.2013