Newsgroup: it.comp.lang.c++
Titolo: STL e hash table

Ho una serie di punti 3d che vorrei mettere in una hash table.
Se uso una Map (con chiave il risultato di una funzione hash()) mi muovo 
nella direzione giusta?
Traduco (quanto sono contorto!):
1) esiste in STL una stuttura hash table?
2) la std::map č una hash table?
3) quale č l'oggetto piů performante per risolvere il problema di cui 
sopra (usandl STL)?
Tks,
matteo!

"matteo.desimone" <matteo.desimone@NO_SPAMfastwebnet.it> ha scritto nel
messaggio news:QCabc.20642$jY1....@tornado.fastwebnet.it...

esiste hash_map che perň non č nello standard, ma č un'estensione allo
stesso
la std::map non dovrebbe essere una hash table, ma piuttosto una struttura
ad albero
--
Pela

 ad albero
Usando hash_map ho un peggioramento, rispetto a map, del 400% delle 
prestazioni :(
Lascio la map, anche se mi aspettavo un progresso...
matteo!

 sopra (usandl STL)?
Quale problema?
In pratica cosa ci vuoi fare con questi punti 3d?

 oppure no.
Io ho usato std::map così
typedef std::map <size_t, Voxel*> VisitedVoxelType;
typedef std::map <size_t, Voxel*> ToCheckVoxelType;
con chiave tipo size_t che riempio con il risultato di una funzione che 
mi da un valore intero ('abbastanza') unico a seconda delle coordinate 
dei punti.
Usare un std:set potrebbe essere meglio dal punto di vista delle 
performance di inserimento/estrazione/verifica esistenza elemento?
Nel frattempo ho provato ad usare hash_map e ho ottenuto risultati 
peggiori rispetto alla normale map (e non me l'aspettavo).
Spero di essere stato un po' piu' chiaro... :-?
Grazie,
matteo!

 1) esiste in STL una stuttura hash table?
se ti prendi lo Stroustrup tratteggia come fare una hash_table...
anche se imho conviene guardare su un libro di algoritmi...
[ in pratica nella stl non c'e`, afair ]
-- 
Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it.
    - Brian W. Kernighan

 
Fai un std::vector<Voxel> e inserisci tutti i punti (li hai gia' tutti 
all'inizio ?)
Poi fai un std::set<size_t> in cui tieni gli indici (per il vector) 
corrispondenti ai punti gia' elaborati.
O ci sono altri problemi che mi sfuggono ?

 peggiori rispetto alla normale map (e non me l'aspettavo).
Il comportamento di una hash table dipende tutto dalla funzione di
hash e dalla politica di gestione delle collisioni. Sei sicuro di aver
compiuto le scelte migliori? (tieni presente che non so come funzioni
la tua hash_map).
Ciao,
Nicola

 la tua hash_map).
In realtà non so quale policy usa la classe hash_map che mi ha 
cosigliato Pela in una risposta precedente.
Ho trovato la classe nella libreria STL di Visual C++: Pela mi ha detto 
che non è parte dello standard mentre questo Visual truffaldino la 
spaccia per tale... :-)
Ciao,
matteo!

 spaccia per tale... :-)
Non è così truffaldino tanto più che non la inserisce nel namespace std 
ma in stdext.
In ogni caso evita di fare confronti per uguaglianza fra numeri "reali" 
quindi fra double o float e quindi fra punti.
Se hai due double A e B, o li hai generati per copia, con una qualche 
istruzione A = B allora dovresti sapere che l'hai fatto e sapere a 
priori che sono uguali. Se invece li hai generati con due algoritmi 
diversi e vuoi confrontare se sono uguali, dai per scontato che il 
confronto ti dirà sempre che sono diversi (per arrotondamenti 
eventualmente diversi).
Inoltre un confronto per uguaglianza fra double è anche più costoso in 
termini di tempo.
-- 
Daniele Zelante
-- 

 peggiore)...
No. Se il vettore e' ordinato puoi effettuare una ricerca dicotomica,
come ad esempio fanno std::lower_bound e std::upper_bound.
Ciao,
Nicola

 quindi fra double o float e quindi fra punti.
Ok. Grazie, non avevo pensato a questo...
matteo!

 come ad esempio fanno std::lower_bound e std::upper_bound.
Guardo le funzioni che mi hai indicato.
Io devo verificare che l'elemento *non* esista: è come se mi trovassi 
sempre nel caso peggiore, insomma, durante una ricerca.
Non ricordo se una ricerca su un albero colorato è più rapida di una 
dicotomica (e dovrei riordinare il vettore ad ogni inserimento...), o no?
Ciao,
matteo!

 
Ovviamente evita anche l'uso di >= e <= tra double (usa solo > o < )
Questa norma è ritenuta talmente valida che in gcc si può attivare un 
warning nel caso venga effettuato un == o != da double o float.
-- 
Daniele Zelante
-- 

 warning nel caso venga effettuato un == o != da double o float.
Altra preziosa nota.
[mini OT]
Inizialmente volevo usare proprio gcc per fare il mio lavoro ma per 
compatibilità con il vecchio materiale (e sportattutto perche' il mio un 
supervisore che usa il Visual). Sto cercando di mantenere il codice 
quanto più pulito posso per provare a compilare tutto con gcc e fare 
qualche test di profiling...vedremo.
[/mini-OT]
matteo!