Почему мой простой компаратор сломан?

У меня есть класс, который я упростил для этого:

final class Thing {
    private final int value;
    public Thing(int value) {
        this.value = value;
    }
    public int getValue() {
        return value;
    }
    @Override public String toString() {
        return Integer.toString(value);
    }
}

Я хочу отсортировать массив этой вещи. Поэтому я создал простой комаратор:

private static final Comparator<Thing> reverse = new Comparator<Thing>() {
    public int compare(Thing a, Thing b) {
        return a.getValue() - b.getValue();
    }
};

Затем я использую две формы аргумента Arrays.sort.

Это отлично работает для моих тестовых случаев, но иногда все идет не так, когда массив заканчивается странным, но повторяемым порядком. Как это может быть?

Ответы

Ответ 1

Integer overflow & hellip; или, точнее, нижнее течение.

Вместо этого сделайте явное сравнение:

private static final Comparator<Thing> reverse = new Comparator<Thing>() {
    public int compare(Thing a, Thing b) {
      int av = a.getValue(), bv = b.getValue();
      return (av == bv) ? 0 : ((av < bv) ? -1 : +1);
    }
};

Использование вычитания отлично, если вы уверены, что разница не будет "обернуться". Например, когда значения, о которых идет речь, ограничены неотрицательными.

Ответ 2

Вы не можете использовать минус для создания сравнения. Вы переполнитесь, когда абсолютная разница превысит Integer.MAX_VALUE.

Вместо этого используйте этот алгоритм:

int compareInts( int x, int y ) {
  if ( x < y ) return -1;
  if ( x > y ) return 1;
  return 0;
}

Мне нравится иметь эту функцию в библиотеке для таких целей.

Ответ 3

попробовать

System.out.println(Integer.MAX_Value - Integer.MIN_VALUE);

Это должно возвращать положительное число как MAX_VALUE > MIN_VALUE, но вместо этого печатает -1

Ответ 4

При сравнении Java-примитивов рекомендуется преобразовать их в их сопоставления с объектом и полагаться на их методы compareTo().

В этом случае вы можете сделать:

return Integer.valueOf(a.getValue()).compareTo(b.getValue())

Если у вас есть сомнения, используйте хорошо протестированную библиотеку.

Ответ 5

Какие цифры вы там бросаете? Если ваши номера достаточно велики, вы можете обернуть значения MIN/MAX для целых чисел и оказаться в беспорядке.

Ответ 6

Если значение очень отрицательное и значение b очень положительно, ваш ответ будет очень неправильным.

IIRC, Int переполнения безмолвно обертываются в JVM

- MarkusQ