[Java]Ordinare i valori di una hashtable

[neosephiroth86]

Salve!
Ho una hastable con chiavi univoche e valori double del tipo
{55555455=10152.48, 55556566=10129.049999999996, 45555555=10190.599999999999, 55655455=10151.2, 54565555=10190.599999999999, 55555545=10190.599999999999, 54555545=10190.599999999999, 55465565=10190.599999999999, 46555554=10115.449999999999, 65564554=10246.75, 55555555=10190.599999999999, 56656565=10190.599999999999, 55565455=10152.48, 55454564=10228.999999999998, 55655556=10120.799999999996, 65565555=10190.599999999999, 55655445=10151.2, 55565545=10271.299999999997, 64544655=10302.399999999996}

I numeri a sinistra sono le chiavi(tipo 55555455),sono univoche.

Ho bisogno di ordinare gli elementi secondo il valore, in questo caso il numero che è circa 10k. Dopo aver fatto questo ordinamento devo prendere i primi 10 risultati.......

Come posso fare?
Grazie

[neosephiroth86]

Sono riuscito a traslare i valori dalla hashtable ad un arraylist, e ad ordinarli in modo crescente(anche se avrei preferito decrescente, visto che devo selezionare i primi 10 valori).
Solo cosi perdo il riferimento alle chiavi associate ai valori che c'erano nella hastable....

if(ht.containsKey(firstelement)==false){
ht.put(firstelement,secondelement);}
ArrayList Al=new ArrayList(ht.values());
Collections.sort(Al);

[banryu79]

Ciao,
Hashtable (java.util.Hashtable) implementa Map, e fa quindi parte del Collection Framework del JDK.

Puoi quindi invocare entrySet sulla tua hashtable per ottenere il Set delle Map.Entry che contiene (una Map.Entry rappresenta una coppia chiave-valore).

Per ordinare questo set di coppie chiave-valore puoi usare il metodo Collection.sort che prende come argomenti una lista e un Comparator.

La lista la costruisci al volo passando il set di Map.Entry come parametro al costruttore di ArrayList; il Comparator per le MapEntry lo definisci tu: sarà un comparator che confronta l'elemento "valore" delle Map.Entry

In codice (non l'ho compilato, potrebbe contenere errori)

// il comparator
Comparator<Map.Entry<Integer,Double>> comp = 
    new Comparator<Map.Entry<Integer,Double>>() {
        public int compare(Entry<Integer,Double> e1, Entry<Integer,Double> e2) {
            return Double.compare(e1.getValue(), e2.getValue());
        }
    };

// mytable e' la tua Hashtable
// Integer e' il tipo chiave e Double e' il tipo valore
Set<Map.Entry<Integer,Double>> entries = mytable.entrySet();

// costruisce la lista di entries
List<Map.Entry<Integer,Double>> entrylist = 
    new ArrayList<Map.Entry<Integer,Double>>(entries);

// ordina la lista 
Collections.sort(entriylist, comp);

Potresti anche considerare di usare una java.util.TreeMap al posto della Hashtable, se possibile. TreeMap ti consentirebbe di stabilire da subito una relazione d'ordine tra gli elementi che verrebbe preservata ad ogni mutazione della mappa stessa.

[Gold]

Con una treeMap.

Ne istanzi una nuova col comparator che ti ha scritto banryu, gli passi la mappa che hai gia', poi cicli quante volte vuoi chiamando il metodo pollFirstEntry() (o pollLastEntry(), a seconda dell'ordine che gli dai) che restituisce e rimuove il primo (ultimo) elemento della mappa

Saluto

[banryu79]

Originariamente inviato da Gold

Con una treeMap.

Ne istanzi una nuova col comparator che ti ha scritto banryu, gli passi la mappa che hai gia', poi cicli quante volte vuoi chiamando il metodo pollFirstEntry() (o pollLastEntry(), a seconda dell'ordine che gli dai) che restituisce e rimuove il primo (ultimo) elemento della mappa

Saluto

Anche io pensavo a TreeMap (a parte le considerazioni circa le performance) ma la cosa non è proprio "immediata", perchè TreeMap vuole un comparatore per le chiavi, lui invece ordina in base ai valori... se conoscesse/usasse Guava (ex Google Collections) potrebbe usare una BiMap...

@Edit: però BiMap richiede che le chiavi e i valori siano univoci.

[Gold]

Originariamente inviato da banryu79

Anche io pensavo a TreeMap (a parte le considerazioni circa le performance) ma la cosa non è proprio "immediata", perchè TreeMap vuole un comparatore per le chiavi, lui invece ordina in base ai valori... se conoscesse/usasse Guava (ex Google Collections) potrebbe usare una BiMap...

@Edit: però BiMap richiede che le chiavi e i valori siano univoci.

Hai ragionissima.

Non conosco quella BiMap (dopo me la vado a vedere), pero' a naso direi che potrebbe assomigliare alla BidiMap di commons collection, che dovrebbe fare al caso suo.
Quindi direi una TreeBidiMap

Saluto

[banryu79]

Originariamente inviato da Gold

Hai ragionissima.

Non conosco quella BiMap (dopo me la vado a vedere), pero' a naso direi che potrebbe assomigliare alla BidiMap di commons collection, che dovrebbe fare al caso suo.
Quindi direi una TreeBidiMap

Saluto

Vero, si somigliano.
Ma se uno adotta una libreria per una feature particolare, considerato che parliamo di librerie di strutture dati, c'è il "rischio" che con il tempo (insomma, è probabile) tenda a usare sempre più feature di quella libreria.

In questo caso consiglio Guava (Google) rispetto a Common Collection (Apache) principalmente per questi motivi:
- Guava supporta i Generics, ComColl no
- Guava è stata sviluppata sforzandosi di aderire il più possibile ai contratti delle collezioni così come espressi dal Java Collection Framework (Josh Bloch ha fatto da consulente)
- il progetto Guava è bello vispo, Common Collection è un po' "fermo"...

Per chi volesse ulteriori info:
- intervista ai due prinicipali responsabili di Guava
- talk di presentazione della Google Collection Library (ora Guava)

[neosephiroth86]

Non riesco a capire come funziona il vostro codice...
ho cercato di andare avanti da me con un codice di questo tipo

1)Si costruisce la ht con dimensione massima di 3 (in questo caso l'ho messa semplice)
2)Per tutti i valori che arrivano dopo che si è riempita la ht si scansiona la ht e se c'è un valore inferiore, viene sostituito
3) in questo modo la ht contiene sempre i primi 3 valori,i 3 risultati migliori

if (dimension < 3) {
				ht.put(firstelement, secondelement);
				dimension++;
				output.println("Ciao mamma");
			} else {
				
				Enumeration elements = ht.elements();
				while (elements.hasMoreElements()) {
					
					int performance = (Integer) elements.nextElement();
					output.println(performance);
					
					if (performance < Integer.parseInt(secondelement)) {
						ht.put(firstelement, secondelement);
						
					}
				}
			}

Purtroppo non va...ci deve essere qualche errore

[banryu79]

@neosephiroth86:
Ciao, dopo aver letto il tuo post #1 e il tuo ultimo post #8 non riesco a capire quale è il problema che devi risolvere e quali sono i tuoi requisiti (a parte il fatto che, sembra, *devi* usare Hashtable).

Puoi chiarire la situazione?

[neosephiroth86]

ho un generatore di valori del tipo "chiave","valore"
Voglio mantenere una lista, in questo caso usando la struttura hashtable, con i primi 10 valori, anche non in ordine crescente.

del tipo "chiave 1" "10270"
"chiave 2" "10370"
"chiave 3" "10170"

etc

Siccome non sono riuscito bene a capire la vostra soluzione, ho pensato di implementarne io una + semplice, di cui di seguito lo pseudocodice

\\riempio la hastable con le prime dieci coppie chiave valore che mi arrivano (tanto sono per forza buone)
\\ per ogni altra coppia scandisco la hastable, se trovo un coppia chiave valore con valore inferiore, sovrascrivo

In questo modo ho una hastable di 10 elementi che sono i "migliori" di tutti quelli che mi sono arrivati

[banryu79]

Originariamente inviato da neosephiroth86

ho un generatore di valori del tipo "chiave","valore"
Voglio mantenere una lista, in questo caso usando la struttura hashtable, con i primi 10 valori, anche non in ordine crescente.

In pratica vorresti una sorta di cache in cui tenere i 10 risultati più alti generati dal generatore man mano che li genera (cache nel generatore) oppure del generatore non te ne frega una mazza, tu hai solo una valanga di risultati dalla quale estrarre una volta e per sempre i primi 10 valori?

[neosephiroth86]

no ho bisogno di una cache...

[banryu79]

Originariamente inviato da neosephiroth86

no ho bisogno di una cache...

Ah, ok, bene.
Prossima domanda: quando il generatore genera una nuova entry [key,value] dove viene memorizzata la entry (in che tipo di collezione)?
@EDIT: ammesso che il generatore memorizzi le entry, in effetti immagino che non lo faccia, ma semplicemente la restituisca ad un qualche chiamante?

[neosephiroth86]

beh non memorizzo le entry...
io faccio ogni volta hashtable.put(firstelement,secondelement);
Dove firstelement è la key e secondelement il valore..

[banryu79]

Originariamente inviato da neosephiroth86

beh non memorizzo le entry...
io faccio ogni volta hashtable.put(firstelement,secondelement);
Dove firstelement è la key e secondelement il valore..

Ottimo, ultima domanda: devi assolutamente usare una Hastable per implementare la tua cache oppure sei libero di scegliere l'implementazione che preferisci?
Generator deve essere thread-safe?

[neosephiroth86]

no, non deve per forza essere una hastable
Uso hashtable perchè si sposa col concetto di chiave-valore, ed inoltre perchè se aggiungo un elemento alla hashtable che già c'è (coppia chiave-valore) viene ignorato,o sbaglio?
Ah una coppia chiave-valore è univoca, non possono esistere due coppie con chiavi uguali e valori differenti..

Per quanto riguarda thread-safe... si è meglio thread safe.

[neosephiroth86]

Per cercare di aiutarti ti posto un blocco + ampio di codice

	while (true) {

			m0 = getMessageSynch();
			Vector<String> vector = (Vector) m0.getObject();
			StringTokenizer st = new StringTokenizer(vector.elementAt(0)
					.toString());
			String firstelement = new String(st.nextToken());
			String secondelement = new String(st.nextToken());
			
			
			if (dimension < 10) {
				ht.put(firstelement, secondelement);
				dimension++;
				
			} else {
				
				Enumeration elements = ht.elements();
				while (elements.hasMoreElements()) {
					
					double performance = (Double) elements.nextElement();
					output.println(performance);
					
					if (performance < Double.parseDouble(secondelement)) {
						ht.put(firstelement, secondelement);
						
					}
				}
			}
			output.println(ht.toString());

		}
	}
}

Si trova in while(true) perchè è un agente di servizio di un software multiagente, e aspetta i messaggi di centinaia di agenti utenti che effettuano dei calcoli e fanno report a questo agente qui...

[banryu79]

...
if (dimension < 10) {
    ht.put(firstelement, secondelement);
    dimension++;	
} else {
    Enumeration elements = ht.elements();
    while (elements.hasMoreElements()) {
        double performance = (Double) elements.nextElement();
        output.println(performance);
					
    if (performance < Double.parseDouble(secondelement)) {
        ht.put(firstelement, secondelement);	
    }
}
...

Così però stai inserendo le prime 10 entry, e poi se ti arriva una entry maggiore di una qualsiasi altra entry già presente la inserisci (senza però eliminarne nessuna), ecco perchè non ti va.

[neosephiroth86]

un possibile fix?

[banryu79]

Originariamente inviato da neosephiroth86

un possibile fix?

Beh, avendo trovato il valore da sostiutire (performance):

...
if (performance < Double.parseDouble(secondelement)) {
        ht.put(firstelement, secondelement);	
    }
...

devi trovare la chiave associata a performance (il che implica iterare tutte le chiavi), invocare remove sulla hastable con quella chiave (il che rimuove anche il valore, performance) quindi inserire la nuova chiave (firstelement) con il nuovo valore (secondoelement).

Questo se non puoi/vuoi astrarre un po' di più le cose (ad esempio creando una classe apposita per rappresentare la tua Entry di interi-double, e un'altra tipo Cache che gestisca sto meccanismo di tenere in memoria solo le 10 Entry con i valori più alti generati -- dietro le quinte può usare quello che vuole per implementare la cache, non sei più per forza legato ad Hashtable perchè non ti serve neccessariamente una mappa/dizionario ne neccessariamente una struttura dati thread-safe, dato che sarà solo l'accesso a Cache a dover essere thread-safe).