Warum ist mein einfacher Komparator gebrochen?

Question

Ich habe eine Klasse, die ich dies vereinfacht:

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

Ich möchte eine Reihe von dieser Sache sortieren. So habe ich eine einfache copmarator erstellt:

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

ich dann verwenden, um die zwei Argumente Form Arrays.sort.

Dies funktioniert gut für meine Testfälle, aber manchmal geht es alles falsch mit dem Array in einer fremden, aber wiederholbaren Reihenfolge enden. Wie kann das sein?

Answer 1

Integer Überlauf ... oder genauer gesagt: Unterschreitung.

Stattdessen tut einen expliziten Vergleich:

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

Subtraktion zu verwenden ist in Ordnung, wenn Sie sicher sind, dass die Differenz „Wrap-around“ nicht. Zum Beispiel, wenn die Werte in Frage gezwungen sind, als nicht-negativ ist.

Answer 2

Sie können nicht minus verwenden Sie den Vergleich zu erzeugen. Sie werden überlaufen, wenn die absolute Differenz Integer.MAX_VALUE überschreitet.

Verwenden Sie stattdessen diesen Algorithmus:

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

Ich mag diese Funktion für solche Zwecke in einer Bibliothek haben.

Answer 3

Versuch

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

Dies muss eine positive Zahl als MAX_VALUE> MIN_VALUE zurückzukehren, sondern druckt -1

Answer 4

Wenn Java Primitive zu vergleichen, ist es ratsam, sie zu ihrem Objekt Pendants zu konvertieren und auf ihren compareTo() Methoden verlassen.

In diesem Fall können Sie tun:

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

Im Zweifelsfall verwenden Sie eine gut getestete Bibliothek.

Answer 5

Welche Zahlen werfen Sie da drin? Wenn Ihre Zahlen groß genug sind, könnten Sie die MIN / MAX-Werte für ganze Zahlen wickeln durch und in einem Chaos enden.

Answer 6

Wenn ein Wert des sehr negativ und b der Wert ist sehr positiv Ihre Antwort sehr falsch sein wird.

IIRC, Überlauf Int still umschlingt in der JVM

- MarkusQ