PDA

Visualizza la versione completa : [C] Funzione di hashing da 16bit


zacca94
26-08-2017, 18:59
Devo catalogare 13 caratteri disposti casualmente per un totale di 233 combinazioni, vorrei evitare di dover scorrere la lista più di una volta quindi ho pensato di creare una array da 65536, hashare e richiamare l'indice dell'array.

Ovviamente il problema è che con 16 bit ho troppe collisioni contando poi che le combinazioni sono simili.

Come posso risolvere?

MItaly
27-08-2017, 14:13
233 combinazioni è veramente poca roba, probabilmente addirittura una ricerca lineare sulle CPU correnti è più veloce rispetto a fare il lookup in una hashtable così inutilmente grossa (le CPU attuali sono brave ad eseguire codice stupido, e viceversa il collo di bottiglia più frequente è l'accesso alla RAM, per cui se l'hashtable casca fuori dalla cache addio).

Dovresti comunque chiarire un po' meglio la situazione; in particolare:
- di che linguaggio si sta parlando (se è un linguaggio di altissimo livello - ad esempio Python) vuoi usare semplicemente un dict, qualunque altra soluzione implementata direttamente in Python sarà spaventosamente più lenta, indipendentemente dalla complessità asintotica;
- se le chiavi da catalogare sono note in anticipo, se sono note solo a runtime e, in quest'ultimo caso, quanto spesso accade di aggiungere o rimuovere chiavi; nel primo caso si possono usare tool per generare una funzione di hash perfetta (come gperf), nel secondo può convenire ordinare la lista delle coppie chiave-valore e usare una ricerca dicotomica, nell'ultimo dipende.

zacca94
27-08-2017, 17:01
Linguaggio C


233 combinazioni è veramente poca roba, probabilmente addirittura una ricerca lineare sulle CPU correnti è più veloce rispetto a fare il lookup in una hashtable così inutilmente grossa (le CPU attuali sono brave ad eseguire codice stupido, e viceversa il collo di bottiglia più frequente è l'accesso alla RAM, per cui se l'hashtable casca fuori dalla cache addio).

...

nel secondo può convenire ordinare la lista delle coppie chiave-valore e usare una ricerca dicotomica, nell'ultimo dipende


Sono d'accordo, ed è il metodo attualemtne utilizzato, peccato che devo aggiornare il valore di queste chiavi circa 172400 per chiave.
Quindi scorrere un'array per trovare l'indice allunga di molto i tempi di esecuzione.

MItaly
27-08-2017, 17:08
Ribadisco: a seconda del numero di elementi, una ricerca lineare può essere più veloce di una dicotomica o di un lookup in hashtable, per cui cambiare l'attuale ricerca lineare potrebbe rendere i tempi di ricerca ancora più lunghi. In ogni caso, ~200 elementi è poco ma non pochissimo, per cui direi che l'unica è provare.

Chiedo di nuovo: le chiavi da catalogare sono note in anticipo? sono note solo a runtime? in tal caso, accade di aggiungere o rimuovere chiavi?

zacca94
27-08-2017, 18:22
Chiedo di nuovo: le chiavi da catalogare sono note in anticipo? sono note solo a runtime? in tal caso, accade di aggiungere o rimuovere chiavi?

In runtime

MItaly
27-08-2017, 18:34
In tal caso, accade di aggiungere o rimuovere chiavi?
(nello specifico: accade con frequenza paragonabile al lookup?
Se la risposta è no (o comunque, raramente), tenterei una dicotomica, ordinando la lista quando sono note le chiavi. Per delle stringhe potrebbe essere anche più veloce di una funzione di hash non perfetta, dato che per la maggior parte dei match "sbagliati" il confronto si ferma subito (=senza arrivare in fondo alla stringa).

zacca94
30-08-2017, 04:22
Volevo segnalare anche questa soluzione da un utente di un famoso forum di linux:


Fai un vettore di liste, così devi cercare l'elemento in una più stretta cerchia data esclusivamente dalle collisioni

Scara95
30-08-2017, 10:00
Anche un trie potrebbe essere una soluzione plausibile a seconda anche della lunghezza delle stringhe

MItaly
30-08-2017, 11:26
Sì, la lista di trabocco è un approccio classico alle collisioni nelle hashtable, ma se hai una funzione di hashing decente le collisioni comunque dovrebbero essere poca roba fino ad un fattore di carico sensato. Inoltre uno svantaggio della lista linkata è che ha località di cache peggiore, per cui spesso si preferisce usare approcci alle collisioni che rimangono all'interno della hashtable.

Anche un trie potrebbe essere una soluzione plausibile a seconda anche della lunghezza delle stringhe
Anche, vale anche lì il discorso della località di cache se le si allocano indipendentemente (anche se volendo uno può comunque tenere tutto in un "piattone" - i nodi vengono allocati in un vettorone con un sistema ad allocatore lineare e al posto dei puntatori - inutilmente grossi - si usano degli indici).

MItaly
30-08-2017, 11:39
Comunque, in fatto di performance le chiacchiere stanno a zero :D hai fatto qualche prova? Come sono le performance relative di ricerca lineare, dicotomica e hashing?

Loading