Perché il mio semplice comparatore è 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. Così 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(); 
    } 
}; 

Ho quindi utilizzare la forma a due argomenti di Arrays.sort.

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

Answer 1

Intero overflow & hellip; o più precisamente, underflow.

Invece, fare 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); 
    } 
}; 

Utilizzando sottrazione va bene se si è certi che la differenza non sarà "wrap around". Ad esempio, quando i valori in questione sono vincolati per essere non negativi.

Answer 2

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

Invece, utilizzare 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

Che tipo di numeri ci passi dentro? Se i tuoi numeri sono abbastanza grandi, puoi avvolgere i valori MIN/MAX per i numeri interi e finire in disordine.

Answer 4

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

IIRC, Int troppo pieno avvolge in silenzio attorno nella JVM

- MarkusQ

Answer 5

provare

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

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

Answer 6

Quando si confrontano i primitivi Java, è consigliabile convertirli nelle loro controparti oggetto e fare affidamento sui loro metodi compareTo().

In questo caso si può fare:

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

In caso di dubbio, utilizzare una libreria ben collaudato.