Pagina 1 di 6 1 2 3 ... ultimoultimo
Visualizzazione dei risultati da 1 a 10 su 55
  1. #1
    Utente di HTML.it
    Registrato dal
    Jun 2008
    Messaggi
    1,316

    [C] Funzione di hashing da 16bit

    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?

  2. #2
    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.
    Amaro C++, il gusto pieno dell'undefined behavior.

  3. #3
    Utente di HTML.it
    Registrato dal
    Jun 2008
    Messaggi
    1,316
    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.

  4. #4
    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?
    Amaro C++, il gusto pieno dell'undefined behavior.

  5. #5
    Utente di HTML.it
    Registrato dal
    Jun 2008
    Messaggi
    1,316
    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

  6. #6
    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).
    Amaro C++, il gusto pieno dell'undefined behavior.

  7. #7
    Utente di HTML.it
    Registrato dal
    Jun 2008
    Messaggi
    1,316
    Volevo segnalare anche questa soluzione da un utente di un famoso forum di linux:

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

  8. #8
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,590
    Anche un trie potrebbe essere una soluzione plausibile a seconda anche della lunghezza delle stringhe
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  9. #9
    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.
    Quote Originariamente inviata da Scara95 Visualizza il messaggio
    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).
    Ultima modifica di MItaly; 30-08-2017 a 11:36
    Amaro C++, il gusto pieno dell'undefined behavior.

  10. #10
    Comunque, in fatto di performance le chiacchiere stanno a zero hai fatto qualche prova? Come sono le performance relative di ricerca lineare, dicotomica e hashing?
    Amaro C++, il gusto pieno dell'undefined behavior.

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.