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

[Anonymous]

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

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

java.lang.IllegalArgumentException: Comparison method violates its general contract!

выбрасывается 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.
• Повторное воспроизведение с точным порядком списка (вызвавшим ошибку) при новом запуске не выдает ошибку. В то время как порядок триггеров в том же запуске надежно воспроизводит ошибку.
• Даже дальнейшее перетасовывание, похоже, после этого не помогает.

Происходит ли TimSort какую-то внутреннюю магию с запусками, расположением памяти или слиянием, которая зависит не только от порядка ввода?

Есть ли способ надежно построить порядок ввода, который всегда вызывает исключение?
Объяснения/Эффективность:

• Почему результат сортировки кажется недетерминированным относительно этого. порядок ввода?
• Что мне следует знать о внутренней механике TimSort, из-за которой ошибка появляется и исчезает вот так?

Заранее благодарим за любую информацию!

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