Как мой метод компаратора нарушает его общий контракт? - PullRequest
Новая
       23

Как мой метод компаратора нарушает его общий контракт?

2 голосов
/ 13 марта 2020

Сторонние пакеты 

import java.util.Collections;
import java.util.Comparator;
import org.joda.time.DateTime;

Мой компаратор 

public static Comparator<Task> TASK_PRIORITY = new Comparator<Task>() {
    public int compare(Task task1, Task task2) {
        if (task1 == null && task2 == null) return 0;
        if (task1 == null) return +1; //null last
        if (task2 == null) return -1; //null last

        // Only consider retries after a task is retried 5+ times
        if (task1.getRetries() >= 5 || task2.getRetries() >= 5) {
            // Primary sort: retry count (ascending)
            int retriesCompare = Integer.compare(task1.getRetries(), task2.getRetries());
            if (retriesCompare != 0) return retriesCompare;
        }

        // Secondary sort: creation time (ascending, null first)
        int creationCompare = compareTimeNullFirst(task1.getCreationTime(), task2.getCreationTime());
        if (creationCompare != 0) return creationCompare;

        // Tertiary sort: load time (ascending, null last)
        int loadCompare = compareTimeNullLast(task1.getLoadTime(), task2.getLoadTime());
        if (loadCompare != 0) return loadCompare;

        return 0;
    }
};

private static int compareTimeNullLast(DateTime time1, DateTime time2) {
    if (time1 == null && time2 == null) return 0;
    if (time1 == null) return +1;
    if (time2 == null) return -1;
    if (time1.isBefore(time2) return -1;
    if (time1.isAfter(time2)) return +1;
    return 0;
}

private static int compareTimeNullFirst(DateTime time1, DateTime time2) {
    if (time1 == null && time2 == null) return 0;
    if (time1 == null) return -1;
    if (time2 == null) return +1;
    if (time1.isBefore(time2) return -1;
    if (time1.isAfter(time2)) return +1;
    return 0;
}

Использование моего компаратора 

//tasks is a List<Task>
Collections.sort(tasks, TASK_PRIORITY);

Моя проблема

Я иногда получаю IllegalArgumentException для Comparison method violates its general contract!. Я могу постоянно выдавать это исключение, если текущие данные работают достаточно долго, но я не уверен, как устранить истинную причину проблемы.

Мой вопрос

Что не так с моим компаратором ? (В частности, какую часть договора я нарушаю?) Как мне исправить это, не скрывая исключение?

Примечания

  • Я использую Java 7 и не могу обновить без существенной перезаписи.
  • Я мог бы скрыть Исключение, установив java.util.Arrays.useLegacyMergeSort в true, но это нежелательное решение.
  • Я пытался создать тесты для случайным образом генерировать данные и проверять каждое из условий договора . Я не смог получить исключение.
  • Я пытался удалить условие при сравнении повторных попыток, но все равно в итоге получил исключение.
  • Эта строка выдает исключение: Collections.sort(tasks, TASK_PRIORITY);

1 Ответ

4 голосов
/ 13 марта 2020

Давайте начнем с самого начала. Я прочел ваш код так, что логика вашего компаратора c исправна. (Я бы не использовал нулевые значения Task и DateTime, но это не относится к вашей проблеме.)

Другая причина, которая может вызвать это исключение, - это если метод compare дает несогласованные результаты, потому что Task объекты меняются. Действительно, похоже, что это семантически значимо для (по крайней мере) количества попыток измениться. Если есть другой поток, который изменяет Task поля, которые могут повлиять на порядок ... в то время как текущий поток сортирует ..., это может IllegalArgumentException.

(Часть договора сравнения заключается в том, что попарное упорядочение не изменяется при сортировке коллекции.)

Затем вы говорите следующее:

Я использую ImmutableSet.copyOf, чтобы скопировать список перед сортировкой, и я делаю это под блокировкой чтения в java.util.concurrent.locks.ReadWriteLock.

Копирование коллекции не приводит к копированию элементов коллекции. Это мелкая копия. Таким образом, вы получите две коллекции, которые содержат одинаковые объекты. Если другой поток мутирует какой-либо из объектов (например, путем увеличения числа повторов), это может изменить порядок объектов.

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

Какое решение? Я могу вспомнить пару:

  1. Вы можете заблокировать что-либо, чтобы заблокировать все обновления коллекций И ​​объекты-элементы во время копирования и сортировки.

  2. Вы можете глубоко скопировать коллекцию; т.е. создать новую коллекцию, содержащую копии элементов исходной коллекции.

  3. Вы можете создавать легковесные объекты, которые содержат снимки полей Task соответствующих объектов на сортировку; например, 

    public class Key implements Comparable<Key> {
    private int retries;
    private DateTime creation;
    private DateTime load;
    private Task task;

    public Key(Task task) {
        this.task = task;
        this.retries = task.getRetryCount();
        ...
    }

    public int compareTo(Key other) {
        // compare using retries, creation, load
    }
}

    . Это дает потенциальные преимущества, поскольку вы копируете меньше информации, и вы можете go из отсортированной коллекции Key объектов в исходные Task объекты.

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

...