Perché il mio comparatore semplice è rotto?

Question

Ho una classe, che ho semplificato a questo:

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

Voglio ordinare un array di questa cosa. Quindi ho creato un semplice copmarator:

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

Uso quindi la forma a due argomenti di Arrays.sort .

Questo funziona bene per i miei casi di test, ma a volte va tutto storto con l'array che finisce in un ordine strano ma ripetibile. Come può essere?

Answer 1

Overflow di interi & # 8230; o più precisamente, underflow.

Invece, fai un confronto esplicito:

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

L'uso della sottrazione va bene se sei sicuro che la differenza non andrà a capo ". Ad esempio, quando i valori in questione sono vincolati a essere non negativi.

Answer 2

Non è possibile utilizzare meno per creare il confronto. Overflow quando la differenza assoluta supera Integer.MAX_VALUE .

Utilizza invece questo algoritmo:

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

Mi piace avere questa funzione in una libreria per tali scopi.

Answer 3

try

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

Questo deve restituire un numero positivo come MAX_VALUE > MIN_VALUE ma stampa invece -1

Answer 4

Quando si confrontano le primitive Java, è consigliabile convertirle nelle loro controparti Object e fare affidamento sui loro metodi compareTo () .

In questo caso puoi fare:

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

In caso di dubbi, utilizzare una libreria ben testata.

Answer 5

Che tipo di numeri ci lanci? Se i tuoi numeri sono abbastanza grandi, potresti racchiudere i valori MIN / MAX per gli interi e finire in un pasticcio.

Answer 6

Se il valore di a è molto negativo e il valore di b è molto positivo, la tua risposta sarà molto sbagliata.

IIRC, Int overflow si avvolge silenziosamente nella JVM

- MarkusQ