Могу ли я использовать Collections.sort с квазипорядком?

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

Теперь предположим, что у нас есть список строк, и мы хотим отсортировать его по длине (сначала самые короткие). Если две строки имеют одинаковую длину, нам все равно, что будет первым. На первый взгляд кажется разумным написать

Collections.sort(list, (s, t) -> s.length() - t.length());

К сожалению, это незаконно. Javadoc интерфейса Comparator недвусмысленно требует, чтобы сравнение осуществляло полное упорядочение. Это нарушается, потому что "a".length() - "b".length() равно 0, но "a".equals("b") ложно.

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


java sorting comparator preorder
person user1935570    schedule 13.10.2015    source источник
comment
Возможный дубликат Sort ArrayList строк по длине   -  person azurefrog    schedule 14.10.2015
comment
Javadoc интерфейса Comparator недвусмысленно требует, чтобы сравнение осуществляло полное упорядочение. Что дает вам такое впечатление? Это полный порядок; просто элементы, не равные по .equals, могут быть равны по компаратору. Это не только законно, но и совершенно нормально. Это просто несовместимо с равными.   -  person Louis Wasserman    schedule 14.10.2015
comment
Я думаю, вы путаете общий порядок и строгий общий порядок   -  person Jonah Graham    schedule 14.10.2015
comment
На самом деле это не связано с вашим вопросом, но нам следует избегать использования s.length() - t.length() в результате сравнения. Это правда, что мы в безопасности при работе с положительными значениями (как в этом случае), но для отрицательных результат может перетекать из отрицательного в положительное, что может быть проблемой. Вместо этого лучше использовать Integer.compare(s.length(), t.length()). Кстати, вместо (s, t) -> Integer.compare(s.length(), t.length()) мы можем использовать, возможно, немного более четкое Comparator.comparingInt(String::length).   -  person Pshemo    schedule 14.10.2015
comment
@Джон Грэм: общий порядок должен удовлетворять аксиоме антисимметрии: если a ‹= b и b ‹= a, то a = b. См. статью в Википедии об общем порядке. Итак, упорядочение строк по длине — это не тотальный порядок (он тотальный, но не порядок).   -  person user1935570    schedule 14.10.2015

Ответы (2)


arrow_upward
1
arrow_downward

Вы неправильно интерпретируете документы. Когда они говорят

Функция сравнения, которая упорядочивает некоторый набор объектов.

это определение, а не требование. Для заданных Comparator, c, если c.compare(o1, o2) == 0, то для целей порядка, определенного c, o1 и o2 равны.

Документы продолжают говорить о том, что означает для Comparator быть «совместимым с равными», что в основном означает, что чувство равенства, присущее Comparator, как описано выше, такое же, как и чувство, присущее разрешенным объектам. equals() методы. Это обсуждение основано на возможности того, что некоторые Comparator не будут иметь той характеристики, которой нет у предложенного вами. Использование такого Comparator для заказа SortedSet или SortedMap может привести к поведению, нарушающему контракты этих интерфейсов, но нет ничего плохого в использовании такого Comparator с Collections.sort().

person John Bollinger    schedule 13.10.2015
comment
Спасибо, я уже начал это подозревать. Я думаю, вы правы. - person user1935570; 14.10.2015

arrow_upward
1
arrow_downward

Ваше решение, использующее длину, обеспечивает общее упорядочение.

То, что вы имеете в виду под "a".length() - "b".length() == 0, но "a".equals("b") == false, не является полным порядком. Это связано с тем, что совместимо с равными. В этом отношении документация для интерфейса Comparable говорит:

Говорят, что порядок, налагаемый компаратором c на набор элементов S, согласуется с равенством тогда и только тогда, когда c.compare(e1, e2)==0 имеет то же логическое значение, что и e1.equals(e2) для каждого e1 и e2 в С.

Это не означает, что вы должны предоставить компаратор, который будет совместим с равными.

person Rodrigue    schedule 13.10.2015
comment
Хорошо, я не обязан предоставлять компаратор, который будет согласовываться с равными. Но если я этого не сделаю, то мне угрожает осторожность при использовании компаратора, способного навязывать порядок, несовместимый с равными, для упорядочения отсортированного набора (или отсортированной карты). Если порядок, налагаемый c на S, несовместим с равными, отсортированное множество (или отсортированная карта) будет вести себя странно. В частности, отсортированный набор (или отсортированная карта) будет нарушать общий контракт для набора (или карты), который определен в терминах равенства. Так что мне он кажется грязным. - person user1935570; 14.10.2015