[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]

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) (http://code.google.com/p/guava-libraries/) potrebbe usare una BiMap...

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

[Gold]

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) (http://code.google.com/p/guava-libraries/) 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]

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 (http://www.javalobby.org/articles/google-collections/)
- talk di presentazione della Google Collection Library (ora Guava) (http://www.youtube.com/watch?v=ZeO_J2OcHYM)

[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]

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]

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]

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]

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).

[neosephiroth86]

lol già c'è se guardi il mio codice...

[banryu79]

lol già c'è se guardi il mio codice...
lol non ho capito a cosa ti riferisci con "già c'è"... c'è il remove dalla hashtable o c'è l'astrazione della Cache e delle entry?
Scusami ma a me non sembra ne la prima ne la seconda...

[neosephiroth86]

hai ragione avevo letto solo il codice...scusami
Ti ringrazio per ora!

[banryu79]

hai ragione avevo letto solo il codice...scusami
Ti ringrazio per ora!
Adesso vado a mangiare, poi, se ho tempo, ti posto un'idea di massima di quello che intendevo circa le astrazioni...

[banryu79]

La mia idea è di astrarre sia la Cache del generatore che la singola Entry generata.

Nel codice qui sotto ho implmentato una Enrty come un'accoppiata id-valore . Entry definisce la sua relazione di uguaglianza/identità con un'altra Entry in termini di [I]valore [double]. Entry è Comparable, ed è Immutable.

La Cache invece è implementata come un SortedSet (ho usato TreeSet) di entries. Uso un SortedSet perchè:
1) essendo un Set mantiene solo elementi univoci evitando duplicati, siccome gli elementi sono di tipo Entry e Entry è comparabile e identificabile in termini di valore la cache non permetterà inserimento di valori duplicati.
2) un SorteSet ordina gli elementi dal più piccolo al più grande in base (in qesto caso) al natural ordering degli elementi: gli elementi sono di tipo Entry e Entry definisce il suo natural ordering implementando Comparable, dunque in termini di valore, non di id.

Ecco il codice, alcune note:
- il metodo main in Generator serve solo come test
- si può rendere il tutto molto più generico (usando i Generics)
- non ho preso in considerazione l'aspetto thread-safe, ma Entry è immutabile di suo, quindi è thread-safe, per Cache invece basterebbe sincronizzare il metodo storeValueIfHighest
- vuole essere un esempio concettuale, a prescindere dal tuo specifico scenario (io di Jade non so una ceppa).


import java.util.SortedSet;
import java.util.TreeSet;

/**
* A Generator of Double values that mark each value produced
* with an integer ID that rapresents its cardinality.<b>
* The Generator cache the first 10 highest values ever produced.
*
* @author Francesco Baro
*/
public class Generator
{
// For Test Only
public static void main(String[] args) {
Generator g = new Generator();

System.out.println("generated values:");
for (int i=0; i<100; i++)
System.out.println(g.newValue());

System.out.println();

System.out.println("highest values:");
for (Entry e : g.cache.highest)
System.out.println(e);
}


private int idCounter = 0;
private Generator.Cache cache = Generator.Cache.of(10);

//
// PUBLIC INTERFACE
//

public double newValue() {
Generator.Entry entry = generateNewEntry();
return entry.val;
}

//
// IMPLEMENTATION
//

private Generator.Entry generateNewEntry() {
idCounter = idCounter + 1;
double newVal = generateNewValue();
Generator.Entry entry =
new Generator.Entry(idCounter, newVal);
cache.storeValueIfHighest(entry);
return entry;
}

private double generateNewValue() {
// do your computation for new double values
// here -- this is only a dummy example
return Math.random();
}

/**
* Generator.Entry has got an id and a value and is
* identified and compared by value, not by id<br>
* Generator.Entry is immutable
*/
private static class Entry implements Comparable<Entry>
{
public final int id;
public final double val;

Entry(int id, double val) {
this.id = id;
this.val = val;
}

@Override public int hashCode() {
return (int)
(Double.doubleToLongBits(this.val) ^
(Double.doubleToLongBits(this.val) >>> 32));
}

@Override public boolean equals(Object obj) {
if (obj == this) return true;

if (obj instanceof Entry) {
Entry e = (Entry) obj;
return this.val == e.val;
}

return false;
}

@Override public int compareTo(Entry e) {
return Double.compare(val, e.val);
}

@Override public String toString() {
return "id:"+id+" - value:"+val;
}
}

/**
* Generator.Cache store the 10 highest entries produced
*/
private static class Cache
{
// Using SortedSet: first element is the lowest,
// of the set, last is the highest
private final SortedSet<Generator.Entry> highest;
private final int maxSize;

//
// PUBLIC INTERFACE
//
/** Factory method for Cache instances */
public static Generator.Cache of(final int N) {
return new Cache(N);
}

void storeValueIfHighest(Entry candidate) {
highest.add(candidate);
if (highest.size() >= maxSize)
highest.remove(highest.first());
}

//
// IMPLEMENTATION
//

private Cache(final int N) {
highest = new TreeSet<Generator.Entry>();
maxSize = N;
}

private boolean isOneOfTheHighest(Entry candidate) {
for (Entry e : highest)
if (candidate.compareTo(e) > 0)
return true;
return false;
}

}
}



Disclaimer: scritto di getto, può contenere errori e serve tutt'alpiù come ispirazione (alemeno nelle mie intenzioni :asd:)

[neosephiroth86]

grazieee!!
Stò facendo altri aggiustamenti al programma...entro domani ti faccio sapere!

[banryu79]

grazieee!!
Stò facendo altri aggiustamenti al programma...entro domani ti faccio sapere!
Ok, spero ti sia utile più come "ispirazione" o "suggerimento di idea" che altro; se lo usi à la singe (Ctrl+C, Ctrl+V) è un po' riduttivo, imo.

[banryu79]

Siccome c'era un erroretto (una iterazione ridondante) ho preso in mano il codice e mi son trovato, già che c'ero, a rendere Generator "generico": accetta tipi parametrici che estendono Number (quindi tutti i wrapper dei tipi primitivi numerici in Java).
Inoltre si può specificare la "gandezza" della cache per i valori più alti prodotti durante l'istanzazione del Generator.

package generator;

import java.util.Collection;
import java.util.Collections;
import java.util.SortedSet;
import java.util.TreeSet;

/**
* A Generator of Number values that mark each value produced with an integer ID
* that rapresents its cardinality.<b>
* The Generator has got an internal cache to store highest values produced.
*
* @author Francesco Baro
*/
public abstract class Generator<T extends Number>
{

//
// INTERFACE
//

/**
* Build a new Generator with an internal
* cache of maxSize size
*
* @param maxSize the size of the internal
* cache for storing highest values produced
*/
public Generator(int maxSize) {
cache = Generator.Cache.of(maxSize);
}

/** @return a new generated value */
public T newValue() {
Generator.Entry<T> entry = generateNewEntry();
return entry.val;
}

/** @return an immodifiable view of the highest
* value entries */
public Collection<Generator.Entry> getHighestValues() {
return Collections.unmodifiableSortedSet(cache.highest);
}

/** @return reset the internal cache of highest
* values */
public void resetHighestValues() {
cache.reset();
}

/** @return a new value of type T, the main service
* offered by this Generator */
protected abstract T generateNewValue();

//
// IMPLEMENTATION
//
private int idCounter = 0;
private final Generator.Cache cache;

private Generator.Entry<T> generateNewEntry() {
idCounter = idCounter + 1;
T newVal = generateNewValue();
Generator.Entry<T> entry =
new Generator.Entry<T>(idCounter, newVal);
cache.storeValueIfHighest(entry);
return entry;
}


/**
* Generator.Entry has got an id and a value and is
* identified and compared by value, not by id<br>
* Generator.Entry is immutable
*/
protected static class Entry<T extends Number> implements Comparable<Entry>
{
public final int id;
public final T val;

Entry(int id, T val) {
this.id = id;
this.val = val;
}

@Override public int hashCode() {
return (int) val.doubleValue();
}

@Override public boolean equals(Object obj) {
if (obj == this) return true;

if (obj instanceof Entry) {
Entry e = (Entry) obj;
return val.doubleValue() == e.val.doubleValue();
}

return false;
}

@Override public int compareTo(Entry e) {
return Double.compare(val.doubleValue(), e.val.doubleValue());
}

@Override public String toString() {
return "id:"+id+" - value:"+val;
}
}


/**
* An internal cache that store the highest value entries
* produced by the Generator<br>
*/
private static class Cache
{

//
// INTERFACE
//
/** Factory method for Cache instances */
static Generator.Cache of(final int N) {
return new Cache(N);
}

/**
* Store candidate entry into the cache (if it has value
* that is unique in the cache), removing the lowest
* value, if the cache maximum size is violated
*
* @param candidate entry to be stored in the cache
*/
void storeValueIfHighest(Entry candidate) {
highest.add(candidate);

if (highest.size() > maxSize)
highest.remove(highest.first());
}

/** reset the cache */
void reset() {
highest.clear();
}

//
// IMPLEMENTATION
//
private final SortedSet<Generator.Entry> highest;
private final int maxSize;

private Cache(final int N) {
highest = new TreeSet<Generator.Entry>();
maxSize = N;
}
}
}




Generator ora è una classe astratta, per usarla bisogna estenderla e definire il metodo che calcola i nuovi valori con la logica che si desidera, ecco un test:

package generator;

/**
* define and use a generator that produce integer values between 1 to 100 inclusive
* and a generator that produce double values between 0.0 to 1.0 inclusive
*
* @author Francesco Baro
*/
public class GeneratorTest
{
public static void main(String[] args) {
// define a Generator of Integer values
// that cache the 25 highest results
Generator<Integer> intGen = new Generator<Integer>(25) {
@Override protected Integer generateNewValue() {
float value = (float) (Math.random() * 100);
return Math.round(value);
}
};

generateAndPrintValues(intGen, 100);

System.out.println();
System.out.println();
System.out.println();

// define a Generator of Double values
// that cache the 10 highest results
Generator<Double> dblGen = new Generator<Double>(10) {
@Override protected Double generateNewValue() {
return Math.random();
}
};

generateAndPrintValues(dblGen, 10000);
}

public static void generateAndPrintValues(Generator gen, int num) {
System.out.println("generated values:");
for (int i=0; i<num; i++)
System.out.println(gen.newValue());

System.out.println();

System.out.println("highest values:");
for (Object entry : gen.getHighestValues())
System.out.println(entry);
}
}

[neosephiroth86]

scusami ma non potresti costruire il metodo partendo da quello che ho io...
cosi nn è che ci capisca molto... :(
String firstelement = new String(st.nextToken());
String secondelement = new String(st.nextToken());

Diciamo che ti trovi in un while(true) e hai firstelement e secondelement,che ad ogni ciclo cambiano