Свойство транзитивности сравнения строк в java

Взгляните на этот код 

   class StringComparator implements Comparator<String> {

     @Override
     public int compare(String a, String b) {
         if (a.length() == b.length()) {
             return b.compareTo(a);
         } else {
             String ab = a + b;
             String ba = b + a;
             return ba.compareTo(ab);
         }
     }
 }

Ба.compareTo (ab) работает, но ab.compareTo (ba) терпит неудачу. Он выдает незаконное исключение, ссылаясь на нарушение контракта компаратора. Я считаю, что это связано с тем, что свойство транзитивности не было удовлетворено. Может кто-нибудь объяснить, как Java использует свойство транзитивности в случае строк ? Это как-то связано с тем, как работает Тимсорт ?

EDIT: вот ошибка, которую я получаю на Leetcode online судья 

Runtime Error Message:
                Line 32: java.lang.IllegalArgumentException: Comparison method violates its general contract!




              Last executed input:
                [7286,155,351,6059,9686,2668,9551,5410,7182,170,3746,3095,8139,2587,2351,2341,2038,3956,6034,4071,9473,281,9306,8746,7954,8937,7855,3938,9737,2455,4344,2986,8968,1072,2442,7191,9106,4236,2768,5214,7541,329,7530,9068,9644,3539,5177,5332,2065,8245,7494,8454,604,4632,1745,301,3412,1569,8637,7840,7752,9536,1023,4841,1286,6489,8459,2725,8021,5026,7058,4540,9892,5344,1205,4363,959,9729,9225,9733,8417,9873,3721,1434,5136,6111,6189,780,4741,2670,2457,5424,1040,3746,1229,8568,3636,1546,2553,575]

Опять же, я не получаю эту ошибку, когда использую ba.метод compareto(АБ). I

2 2
string comparator compareto

2 ответа:

Да, ваш compare, похоже, не уважает транзитивное свойство, если a и b имеют разные длины.

Это компаратор .сравните (a,b) contract , смотрите жирную часть относительно транзитивности:

Сравнивает свои два аргумента для порядка. Возвращает отрицательное целое число, ноль, или положительное целое число, так как первый аргумент меньше, равен до, или больше, чем второй. В приведенном выше описании обозначение sgn (выражение) обозначает математическая функция signum, который определяется для возврата одного из -1, 0 или 1 в зависимости от того, является ли значение выражения отрицательное, нулевое или положительное.

Исполнитель должен гарантировать, что sgn (compare (x, y)) = = - sgn (compare (y, x)) для всех x и y. (из этого следует, что compare (x, y) должна выбрасывать исключение тогда и только тогда, когда compare(y, x) создает исключение.)

Исполнитель также должен убедиться, что отношение является транзитивным: ((сравнить (x, y)>0) & & (сравнить (y, z)>0)) подразумевает сравнение (x, z)>0.

Наконец, исполнитель должен убедиться, что compare (x, y)==0 подразумевает что sgn (compare (x, z))==sgn (compare (y, z)) для всех z.

Обычно это так, но не строго требуется, чтобы (сравните (x, y)==0) = = (x.равно (y)). Вообще говоря, любой компаратор, который нарушающее это условие должно четко указывать на данный факт. То рекомендуемый язык: "Примечание: этот компаратор налагает порядки, которые несовместимы с равными."

обновление:

Просто чтобы добавить интересную заметку, вы ссылаетесь на сортировку Tim как на алгоритм сортировки, применяемый коллекциями.сортировать () и т. д... , для меньших массивов (размер ниже жестко заданного порога) вместо этого выполняется простая сортировка слиянием. Выбор производится в начале метода сортировки, смотрите источники openJDK для получения дополнительной информации.

1

Предположим, что у нас есть три числа в строковом формате a, b и c, и a | b | c - это самый большой результат, который можно получить.

Тогда мы знаем, (a | b) > (b | a) и (b | c) > (c | b).

Предположим (c | a) > (a | c) (нет транзитивности), тогда мы имеем:

(c | a | b) > (a | c | b) > (a | b | c). Это противоречит a | b | c является самым большим.

0