[C++] Liste Linkate, Alberi Bilanciati o Hashed Tables?

[daniele_dll]

Salve a todos

dunque...avrei una domandina
quali tra di queste sono le liste + performanti?

mi spiego meglio


Io avrò una struttura dove mi serve pescare il più velocemente possibile un'utente dalla lista degli utenti...ma mi serve poterlo pescare sia in base al nick usato ma anche in base al suo ip (ovviamente queste due informazioni sono contenute nella struct)

pensavo alle hashed tables ma volevo dei pareri
Non mi importa moltissimo delle prestazioni di inserimento e eliminazione dato che le ricerche saranno superiori di 7\8 volte ^^

idee?

[internet]

Dunque visto che le ricerche saranno molto frequenti, scartiamo immediatamente le liste linkate (perchè l'operazione di ricerca su questa ha complessità computazionale pari a O(N), occorre scandire tutta la lista nel caso peggiore, frequente quando la ricerca da esito negativo).

1° metodo:
Se per alberi bilanciati, intendi alberi auto-bilancianti, tipo i red black allora la complessità della ricerca è
O(2*log2(N+1)).
La classe map implementata nelle libreria std accompagnata al gcc e quella del visual c è basata su questi alberi.

Per le tabelle hash, dipende se:

2° metodo:
implementate con il metodo di concatenazione (usano liste), allora la complessità della ricerca è O(1 + alfa)

3° metodo:
implementate con il metodo dell'indirizzamento aperto allora la complessità della ricerca con successo è
O( (1/alfa) * ln( 1/(1-alfa) ) )

con alfa <= 1 cioè n <= m

la complessità della ricerca senza successo è
O( 1/(1-alfa) )

con alfa <= 1 cioè n <= m

alfa è pari a n/m

n = numero di elementi nella tabella
m = dimensione della tabella hash

quindi alfa è il numero medio di elementi memmorizzati in ogni lista concatenata.


Quale è più veloce?
Facciamo un esempio:

N = 1000000

1° metodo:
O(log2(1000000)= 40 test nel caso peggiore


2° metodo:
ipotesi: m = 32749, alfa = 1000000 / 32749 = 30,53
O(1+alfa) = 31 test nel caso peggiore

3° metodo:
ipotesi: m = 1428571, alfa = 1000000 / 1428571 = 0.70
ricerca con successo: (1/alfa) * ln( 1/(1-alfa) ) = 2 test
ricerca senza successo: 1/(1-alfa) = 4 test

3 metodo:
ipotesi: m = 3333331, alfa = 1000000 / 3333331 = 0.30
ricerca con successo: (1/alfa) * ln( 1/(1-alfa) ) = 2 test
ricerca senza successo: 1/(1-alfa) = 2 test

La libreria std c++ che viene distribuita con gcc, fornisce una classe hash_map che usa la tecnica a indirizzamento aperto (3° metodo). Si tratta comunque di una estensione non standard. (lo standard non prevede hash_map solo map e non da indicazioni sulla struttura da utilizzare per questa classe).

Di solito i sorgenti della libc++ sono sotto
/usr/include/c++/versione/

le estensioni, tra cui hash_map, qui
/usr/include/c++/versione/ext

Siccome devi fare spesso ricerche sia per nickname che per ip, la soluzione più efficiente IMHO è creare due indici simili a quelli usati dai DBMS, quindi due alberi/tabelle hash o una soluzione ibrida.

Cioè in un DB creo nickname come chiave primaria su cui di solito i DBMS creano automaticamente un indice (frequentemente vengono usati i btrees che sono diversi dagli alberi binari normali e dai red-black, perchè contengono in un solo nodo più chiavi e utilizzano per cui anche la ricerca binaria, ma sono adatti per lo più ai database).

Poi sul campo IP, mettendo come vincolo UNIQUE di solito i DB creano un indice per questi campi. Al limite si usa CREATE INDEX.

Se la portabilità è obbligatoria allora hash_map ti può dare rogne, quindi solo in questo caso userei 2 map.

Se usi gcc, allora 2 hash_map, sarebbe ottimo.

Punto a sfavore di hash_map è il consumo di memoria.

map (nell'ipotesi che sia implementata con alberi) usa un quantitativo di memoria proporzionale al numero degli elementi in essa memorizzati.

hash_map alloca prima un array di x posizioni (non byte) poi quando è riempito diventa di x+y posizioni, poi x+y+z, ecc...
quindi spreca un pò di memoria.


Comunque, spesso, per aumentare il tempo di esecuzione si decide di sacrificare il consumo di memoria.

[internet]

Originariamente inviato da internet

1° metodo:
O(2*log2(1000001)) = 40 test nel caso peggiore

Correzione

[daniele_dll]

azz

grazzissime
non importa che usi + memoria...e tanto deve rullare solo su linuz ^^ o comunque compilato con GCC per finire su win lo butto su con le cygwin quindi non dovrebberò esserci problemi

grazie ancora