Частичный упорядоченный компаратор

Как реализовать java.util.Comparator, который упорядочивает свои элементы в соответствии с отношением частичного заказа?

Например, если задано отношение частичного порядка a ≺ c, b ≺ c; порядок a и b равен undefined.

Поскольку Comparator требует полного упорядочения, элементы ордеров реализации, для которых частичное упорядочение undefined произвольно, но последовательно.

Будет ли следующая работа?

interface Item {
    boolean before(Item other);
}

class ItemPartialOrderComperator implements Comparator<Item> {
    @Override
    public int compare(Item o1, Item o2) {
        if(o1.equals(o2)) {  // Comparator returns 0 if and only if o1 and o2 are equal;
            return 0;
        }
        if(o1.before(o2)) {
            return -1;
        }
        if(o2.before(o1)) {
            return +1;
        }
        return o1.hashCode() - o2.hashCode(); // Arbitrary order on hashcode
    }
}
  • Является ли этот компаратор упорядочивающим транзитивным?
    (Я боюсь, что это не так)
  • Требуется ли Comparators быть транзитивным?
    (при использовании в TreeMap)
  • Как правильно его реализовать?
    (если реализация выше не работает)
    (Hashcodes могут столкнуться, для простоты столкновений пример игнорирует столкновения, см. Ответ Damien B на Наложение полного заказа на все экземпляры * любой * класс в Java для отказоустойчивого упорядочения на хэш-кодах.)

Ответы

Ответ 1

Проблема заключается в том, что когда у вас есть несравнимые элементы, вам нужно вернуться к чему-то умному, чем сравнивать хэш-коды. Например, учитывая частичный порядок {a < b, c < d}, хэш-коды могли бы удовлетворять h (d) h (b) h (c) h (a), что означает, что a < b < c < d < a ( жирный обозначает привязку по хеш-коду), что вызовет проблемы с TreeMap.

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

Ответ 2

Кажется, это скорее ответ, чем комментарий, поэтому я отправлю его

В документации говорится:

Из контекста непосредственно следует, что фактор является отношением эквивалентности на S и что наложенный порядок является полным порядком на S. "

Итак, нет, компаратору требуется полное упорядочение. Если вы реализуете это с частичным заказом, вы нарушаете контракт на интерфейс.

Даже если это может сработать в каком-то сценарии, вы не должны пытаться решить вашу проблему таким образом, чтобы нарушить контракт интерфейса.

См. этот вопрос о структурах данных, которые соответствуют частичному порядку.

Ответ 3

В любое время, когда я пытался использовать хэш-коды для такого рода вещей, я пришел, чтобы пожалеть об этом. Вы будете намного счастливее, если ваш заказ будет детерминированным - для отладки, если ничего другого. Достигнув этого, создав новый индекс для любого ранее не встречавшегося Item и используя эти индексы для сравнения, если все остальное не получится.

Обратите внимание, что упорядочение по-прежнему не гарантируется транзитивным.

class ItemPartialOrderComperator implements Comparator<Item> {
    @Override
    public int compare(Item o1, Item o2) {
        if(o1.equals(o2)) {
            return 0;
        }
        if(o1.before(o2)) {
            return -1;
        }
        if(o2.before(o1)) {
            return +1;
        }
        return getIndex(o1) - getIndex(o2);
    }

    private int getIndex(Item i) {
        Integer result = indexMap.get(i);
        if (result == null) {
            indexMap.put(i, result = indexMap.size());
        }
        return result;
    }

    private Map<Item,Integer> indexMap = new HashMap<Item, Integer>();
}

Ответ 4

В jdk7 ваш объект будет вызывать исключение во время выполнения:

Область: API: Утилиты     Синопсис: обновленное поведение сортировки для массивов и коллекций может вызвать исключение IllegalArgumentException     Описание: Алгоритм сортировки, используемый java.util.Arrays.sort и (косвенно) на java.util.Collections.sort, был заменен.
реализация нового типа может вызвать исключение IllegalArgumentException, если оно обнаруживает сравнимое, которое нарушает договор Сопоставимости. предыдущая реализация молча игнорировала такую ​​ситуацию.     Если требуется предыдущее поведение, вы можете использовать новое системное свойство java.util.Arrays.useLegacyMergeSort для восстановления предыдущего слияния.

    Характер несовместимости: поведенческий
    RFE: 6804124

Ответ 5

Если a < b и b < c подразумевает a < c, вы сделали полный порядок с помощью хэш-кодов. Возьмите a < d, d < c. Частичный порядок говорит о том, что b и d не обязательно упорядочены. Представляя хэш-коды, вы предоставляете заказ.

Пример: is-a-потомок (человека, человека).

Adam (hash 42) < Moses (hash 17), Adam < Joe (hash 9)

Подразумевается

Adam < Joe < Moses

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

Ответ 6

Когда один элемент не является "до" или "после" другого, вместо того, чтобы возвращать сравнение хэш-кода, просто верните 0. Результатом будет "полное упорядочение" и "произвольное" упорядочение совпадающих элементов.