.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [SERALE] - Quicksort (http://www.dsy.it/forum/showthread.php?threadid=42466)
Posted by xSharKMaNx on 11-11-2011 12:10:
[SERALE] - Quicksort
Ciao ragazzi,
qualcuno ha capito qualcosa della lezione di ieri 10.10.2011 ?
L'ultima parte... quando ha cominciato a parlare di varianza, probabilità etc... io mi son perso alla grande.
Ciao a tutti
Daniele
__________________
Perché, mentre il manganello può sostituire il dialogo, le parole non perderanno mai il loro potere; perché esse sono il mezzo per giungere al significato, e per coloro che vorranno ascoltare, all'affermazione della verità. E la verità è che c'è qualcosa di terribilmente marcio in questo paese. (V)
I popoli non dovrebbero aver paura dei propri governi, sono i governi che dovrebbero aver paura dei popoli. (T.J)
Posted by zack1988 on 11-11-2011 12:32:
Io ero a bocca aperta.
Posted by lektronar on 23-11-2011 04:03:
speechless
Posted by xSharKMaNx on 24-11-2011 12:05:
Chiedo l'aiuto del pubblico...
Hash Table
Oltre ad aver capito che è un array di liste quando ha cominciato a parlare di formule io mi sono perso....
__________________
Perché, mentre il manganello può sostituire il dialogo, le parole non perderanno mai il loro potere; perché esse sono il mezzo per giungere al significato, e per coloro che vorranno ascoltare, all'affermazione della verità. E la verità è che c'è qualcosa di terribilmente marcio in questo paese. (V)
I popoli non dovrebbero aver paura dei propri governi, sono i governi che dovrebbero aver paura dei popoli. (T.J)
Posted by panzone on 07-01-2012 21:57:
Originally posted by xSharKMaNx
Chiedo l'aiuto del pubblico...
Hash Table
Oltre ad aver capito che è un array di liste quando ha cominciato a parlare di formule io mi sono perso....
E' il problema di far spiegare ad un matematico certe cose 
Per carità, sicuramente interessante ed utile, ma se sei ad algoritmi significa che un idea di quello fatto a continuo e discreta ce l' hai ed è inutile esser cosi prolissi.
Un hash table è, per l' appunto, un array di liste gestite tramite hash. Per hash si intende il risultato di una funzione che, dato in input un elemento, questa genera un codice, un qualcosa che identifica il mio oggetto ( solitamente nelle implementazioni si utilizza un numero, per tutta una serie di motivi ).
Esempio semplicissimo di funzione hash: ho una stringa. Il suo valore di hash è dato dalla somma del valore ASCII dei suoi caratteri. Quindi, usando questa funzione, posso ottenere un valore che mi permette di identificare la stringa.
Ora, le hash table. Come abbiamo visto dalla mia funzione hash precedente, ottengo un numero. E se usassi questo numero come ( ad esempio ) l' indice di un array per salvare la mia stringa ? Se ci pensi sarebbe molto comodo in fase di ricerca: difatti, visto che la stringa verrà salvata solo in quella posizione, indicata dal mio hash, per la ricerca non dovrò scorrere tutto il vettore, ma semplicemente controllare l' indice ( ricavabile usando la funzione di hash ) per vedere se è presente ! Come vedi, dunque, il tempo di ricerca di un vettore tende ad essere costante.
Ora, gli svantaggi dell' hashing: il primo punto è che le hash table si prendono un casino di memoria: non è detto difatti che userai tutti gli indici in maniera ordinata e dunque potresti trovarti vettori immensi con immense aree vuote.
Esempio: ho la stringa "ciao", che è, usando la funzione di hashing detta prima, il valore 412. Questo significa che devo allocare almeno 412 posizioni, ma le 411 posizioni precedenti ( al momento e molto probabilmente ) resteranno vuote
Poi, altro svantaggio ( ed è il motivo per cui si usano array di liste ): le funzioni hash posson generare lo stesso valore con input diversi. Basta vedere l' esempio precedente: e se dopo "ciao" volessi salvare la parola "bibo", che anche lei con la funzione precedente ha valore 412 ? Semplicemente, usando un array di liste, posso salvare entrambe le stringe in una lista presente all' indirizzo 412 del vettore. In fase di ricerca vado direttamente in quella posizione e scorro la lista ( che sarà sicuramente più veloce che scorrere l' intero vettore per vedere se le mie stringhe son presenti).
Questo cosa significa ? Che la hash table avranno pure tempo costante di ricerca, tuttavia il loro utilizzo deve essere ben giustificato dalla mole di dati che si andranno ad inserire e dalla stabilità della funzione hash ( se questa genera facilmente output uguali, se questa genera output il più possibile distribuiti ecc. ecc. ).
