транзитивность свойство сравнения строк в Java

Question

посмотрите на этот код

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); 
     } 
    } 
} 

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

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

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 (AB). I

Answer 1

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

Это Comparator.compare(a,b) contract см смелой части относительно транзитивности:

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

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

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

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

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

Update:

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

Answer 2

Предположим, что мы имеем три числа в строчном формате 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 является самым большим.