Почему найденный в случайном порядке порядок триггера для нарушения контракта компаратора TimSort *не* надежно воспроизв ⇐ JAVA

[Anonymous]

Справочная информация:
Я отлаживаю настройку сортировки Java, где уже обнаружил неисправный компаратор (нарушает контракт).
Моя цель — реализовать тестовый пример, который вызывает хорошо известное

java.lang.IllegalArgumentException: метод сравнения нарушает его общий контракт!

выбрасывается TimSort для таких компараторов.
Как спровоцировать ошибку?

Я постоянно перемешиваю и сортирую список со многими «проблемными» значениями (например, множеством элементов с одинаковым значением поля). Это очень надежно и воспроизводимо: после пары запусков выдается ожидаемая ошибка.

Код: Выделить всё

for (int i = 0; i < 10_000; i++) {
List shuffled = new ArrayList(input);
Collections.shuffle(shuffled);
try {
List sorted = new ArrayList(shuffled);
Collections.sort(sorted, faultyComparator);
} catch (Exception e) {
// Store the list that triggered the exception!
triggerOrder = new ArrayList(shuffled);
break;
}
}

Мое замешательство:
После успешного захвата списка (

Код: Выделить всё

triggerOrder

), вызвавшую ошибку нарушения контракта, я ожидаю, что воспроизведение сортировки с точно таким же порядком и компаратором каждый раз будет выдавать одну и ту же ошибку.
Но когда я переключаю входные данные на найденный триггерный ордер для следующего выполнения, сортировка работает нормально! Даже дальнейшее перетасовывание TriggerOrder и ввода никогда больше не вызывает ошибку.
Генератор ввода:

Код: Выделить всё

List input = IntStream
// starting order to find a trigger order
.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40)
// a found trigger order
//        .of(10, 7, 27, 24, 33, 13, 23, 19, 37, 25, 22, 31, 1, 35, 18, 28, 29, 3, 9, 8, 15, 39, 14, 10, 10, 34, 17, 26, 2, 12, 4, 32, 5, 11, 16, 36, 38, 21, 10, 6)
.mapToObj(i -> new Pojo(null, i % 10 == 0 ? 10 : i, i + ".pdf"))
.collect(Collectors.toCollection(ArrayList::new));

class Pojo {
private String name;
private Integer date;
private String file;

public Pojo(String name, int date, String file) {
this.name = name;
this.date = date;
this.file = file;
}

// Getter
}

Просто если вам интересно, неисправный компаратор (я знаю, что это чушь;)):

Код: Выделить всё

Comparator faultyComparator = (b1, b2) -> {
if (b1 == null && b2 == null) return 0;
if (b1 == null) return -1;
if (b2 == null) return 1;
final int result = compareToNullSave(b1.getName(), (b2.getName()));
if (result != 0) return result;
final int dateResult = b1.getDate().compareTo(b2.getDate());
if (dateResult != 0) return result; // this should be "return dateResult;"
return compareToNullSave(b1.getFile(), b2.getFile());
}

public static int compareToNullSave(String s1, String s2) {
if (s1 == null) return s2 == null ? 0 : -1;
if (s2 == null) return 1;
return s1.compareTo(s2);
}

Почему триггерный порядок, найденный в случайном порядке, который надежно вызывает нарушение контракта компаратора TimSort в одном запуске, не может воспроизвести исключение в другом запуске?

• Компаратор по-прежнему нарушается таким же образом.
• Ошибка легко провоцируется в цикле shuffle-for.
• Воспроизведение с помощью точный порядок списка (вызвавший ошибку) при новом запуске не выдает ошибку. В то время как порядок триггеров в том же запуске надежно воспроизводит ошибку.
• После этого даже дальнейшее перетасовывание не помогает.

Подробнее здесь: https://stackoverflow.com/questions/798 ... ract-viola