[JAVA] ordinamento discendente di oggetti

[rayman2]

Ciao a tutti. Sto realizzando un programmino java che deve ordinare una lista di oggetti List<User> list in ordine discendente di un suo attributo di tipo float.
Avevo intenzione di usare il metotodo Collections.sort(list). Per farlo ho implementato, nella classe User il seguente metodo:


public class User implements Comparable<User>{

private String id;
private Float reputation;
private Long lastEditTime;
private Integer editCount;

[...]

public int compareTo(User user2) {
return user2.getReputation().compareTo(this.getReputation());
}



"Quasi" tutto l'ordinamento va a buon fine, eccetto alcuni casi che non vengono ordinati; ad esempio:


68,86
65,68
68
...
19
17,4
17,36
18


Onestamente non riesco a trovare una logica in tutto questo, forse ho capito male qualcosa io...ovviamente prima di stampare la "classifica" non faccio alcun tipo di modifica nè agli oggetti, nè alla lista.
Che ne pensate? Grazie.

[banryu79]

public int compareTo(User user2)
{
// return:
// -1 or less if this is smaller than user2;
// +1 or more if this is greater than user2;
// 0 if this and user2 are equals
int ascendingComparison = this.getReputation().compareTo(user2.getReputation());

int descendingComparison;
if (ascendingComparison > 0)
{
descendingComparison = -1;
}
else
if (ascendingComparison < 0)
{
descendingComparison = 1;
}
else
{
descendingComparison = 0;
}

return descendingComparison;
}

[rayman2]

Grazie tante, mi sembra sensata la soluzione che mi hai proposto e in effetti funziona!
Ma perché la mia non andava bene?

[banryu79]

Grazie tante, mi sembra sensata la soluzione che mi hai proposto e in effetti funziona!
Ma perché la mia non andava bene?

Perchè tu volevi un ordinamento discendente mentre il natural ordering per la classe Float stabilisce un ordine ascendente.

Non era corretto quindi, chiamare semplicemente il compareTo di Float tra i due oggetti Float nel tuo metodo semplicemente invertendo l'ordine con cui usi le istanze (hai chiamatao compareTo su user2 con argomento this, quando invece normalmente è il contrario): perchè bastasse allora sarebbe anche stato neccessario che internamente al compareTo di Float l'ordine delle istanze fosse invertito (descending order) quando invece non è affatto così.

[rayman2]

Ora ho capito, sono stato un po' superficiale :) grazie!

[mad_hhatter]

public int compareTo(User user2)
{
// return:
// -1 or less if this is smaller than user2;
// +1 or more if this is greater than user2;
// 0 if this and user2 are equals
int ascendingComparison = this.getReputation().compareTo(user2.getReputation());

int descendingComparison;
if (ascendingComparison > 0)
{
descendingComparison = -1;
}
else
if (ascendingComparison < 0)
{
descendingComparison = 1;
}
else
{
descendingComparison = 0;
}

return descendingComparison;
}


scusatemi, stamattina è una brutta giornata, ma io non capisco...

per rispettare il contratto di Comparable il codice qui sopra può essere semplificato così:


public int compareTo(User user2)
{
int ascendingComparison = this.getReputation().compareTo(user2.getReputation());

int descendingComparison = -ascendingComparison;

return descendingComparison;
}


ora, siccome il contratto di Comparable richiede anche che

sgn(x.compareTo(y)) == -sgn(y.compareTo(x))

consegue che

-ascendingComparison == user2.getReputation().compareTo(this.getReputation())

che è l'implementazione iniziale.

Cosa mi sfugge?

[rayman2]

In effetti il mio ragionamento iniziale è stato quello (in realtà prima avevo anche realizzato altre versioni simili che non funzionavano ugualmente). Al momento sto usando l'unica versione che funziona perché ho bisogno di andare avanti nel progetto, però capire meglio (magari un esempio sarebbe utile) quali sono i casi in cui il mio ordinamento fallisce.

Tra l'altro colgo l'occasione per segnalare la bellezza di questa sezione del forum perché è veramente istruttiva.

[mad_hhatter]

posto il mio codice di prova, scusate se è scritto coi piedi, ma avevo fretta :)

Ho usato i valori di prova mostrati nel prismo post. Se lo provate, vedrete che l'ordinamento discendente è corretto.

Quindi la domanda è: qual è la differenza tra questo codice e quello del primo post?


import java.util.*;

public class Compare {
public static void main(String[] args) {

Float[] fa = new Float[] {17.4f, 18f, 17.36f, 19f, 68f, 68.86f, 65.68f};

ArrayList<X> l = new ArrayList<X>();
for(int i = 0; i < fa.length; i++) {
l.add(new X(fa[i]));
}

Collections.sort(l);
for(int i = 0; i < l.size(); i++) {
System.out.println(l.get(i).getX());
}
}
}

class X implements Comparable<X> {
private Float x;

X(Float x) {
this.x = x;
}

Float getX() {
return x;
}

public int compareTo(X another) {
//return getX().compareTo(another.getX());
//return -getX().compareTo(another.getX());
return another.getX().compareTo(getX());
}
}

[banryu79]

Mmm... rileggendo le vostre obiezioni e rileggendo i Javadoc sono sorti dei dubbi anche a me.

Sarò franco: la soluzione che ho postato e la successiva spiegazione che ho fornito sono più frutto di un'intuizione che altro.
Infatti di primo acchitto la soluzione iniziale di rayman2 mi sembrava a posto, poi a furia di guardarla ho cominciato a storcere il naso come se qualcosa non andasse, ma senza riuscire ad afferrare cosa (sì, lo so, non è un approccio al codice molto razionale :asd: ).

Dopo aver riletto per l'ennesima volta la documentazione dell'interfaccia Comparable e di Comparator sono giunto a una [mia personale] conclusione.

Vi posto gli estratti che mi hanno fatto riflettere, alla luce della consideraizone che se esiste sia una interface Comparable che una interface Comparator ci deve essere un motivo ben specifico.

[Tenete conto che andando a guardare i sorgenti del JDK per vedere cosa succede alla invocazione Collections.sort(List<T> list) e Collections.sort(List<T> list, Comparator<? super T> c) si nota che ci sono due path di esecuzione diversi che a valle conducono a due diverse implementazioni del metodo mergeSort() nella classe Arrays: una che al suo interno si aspetta di avere a che fare con oggetti Comparable e l'altra che invece fa uso del Comparator per confrontare gli elementi]

Tenedo conto di come descrivono Comparable e l'uso che ne fa la Collections.sort() relativa:

public interface Comparable<T>

This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method.

Lists (and arrays) of objects that implement this interface can be sorted automatically by Collections.sort (and Arrays.sort).

...

For the mathematically inclined, the relation that defines the natural ordering on a given class C is:

{(x, y) such that x.compareTo(y) <= 0}.


Collections.sort per oggetti Comparable:

public static <T extends Comparable<? super T>> void sort(List<T> list)

Sorts the specified list into ascending order, according to the natural ordering of its elements. All elements in the list must implement the Comparable interface.

Array.sort per oggetti Comparable, viene anche invocato da Collections.sort:

public static void sort(Object[] a)

Sorts the specified array of objects into ascending order, according to the natural ordering of its elements. All elements in the array must implement the Comparable interface.


Alla luce di queste indicazioni mi pare di capire che la documentazione ci stia dicendo più o meno esplicitamente che il natural ordering che tu utente puoi implementare nelle tue classi che implementano l'interfaccia Comparable debba essere in ascending order.

Se vuoi altri ordering a parte l'ascending (che è quello naturale), allora ti devi implementare degli altri Comparator; se invece vuoi che l'unico ordering dei tuoi oggetti sia comunque diverso dall'ascending order devi rinunciare a implementarlo tramite l'interfaccia Comparable: i tuoi oggetti non avranno quindi un natural ordering, ma li potrai sempre ordinare tramite apposito Comparator.


Secondo voi mi sono fatto un pippone mentale?

[rayman2]

inizio a sospettare di aver fatto un po' casino con la gestione dei thread (vedi http://www.hwupgrade.it/forum/showthread.php?t=1916983 ) e quindi forse "qualcuno" stava modificando la mia lista durante l'ordinamento. E' l'unica spiegazione possibile, ma nel frattempo sono passato alla versione ad unico thread e probabilmente la mia primissima versione funzionerebbe. Sarei molto curioso di provare, ma dovendo trattare migliaia di file sarebbe un po' una perdita di tempo. La mia versione ipercompatta in effetti è esaltante ;)

[banryu79]

Pefetto, mi sono fatto un segone memorabile :ops2:
Forse è il caso staccare un po'... :uh: