[C] Funzione di hashing da 16bit

[zacca94]

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]

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]

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]

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]

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]

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]

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]

Anche un trie potrebbe essere una soluzione plausibile a seconda anche della lunghezza delle stringhe

[MItaly]

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]

Ok, ho fatto qualche prova io in C++ con un programma di test di questo tipo:

#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <iostream>
#include <unordered_map>
#include <map>

const int comb_n = 233;
const int tot_count = 172400;

int main() {
    std::string sz = "abcdefghijklm";
    std::vector<std::string> combs;
    for(int i=0; i<comb_n; ++i) {
        std::random_shuffle(sz.begin(), sz.end());
        combs.push_back(sz);
    }

    {
        std::cout<<"Lineare\n";
        std::vector<std::pair<std::string, unsigned>> count_v;
        for(auto &sz: combs) {
            count_v.push_back(std::make_pair(sz, 0U));
        }
        for(int i=0; i<tot_count*comb_n; ++i) {
            const std::string &key = combs[rand()%comb_n];
            for(auto &it: count_v) {
                if(it.first == key) {
                    it.second++;
                    break;
                }
            }
        }
        std::cout<<"Fine lineare!\n";

        std::cout<<"Dicotomica\n";
        std::sort(count_v.begin(), count_v.end());
        for(int i=0; i<tot_count*comb_n; ++i) {
            const std::string &key = combs[rand()%comb_n];
            auto it = std::lower_bound(count_v.begin(), count_v.end(), key,
                    [](const std::pair<std::string, int> &a, const std::string &b) {
                        return a.first < b;
                    });
            it->second++;
        }
        std::cout<<"Fine dicotomica\n";
    }

    {
        std::cout<<"Hashtable\n";
        std::unordered_map<std::string, unsigned> count_h;
        for(int i=0; i<tot_count*comb_n; ++i) {
            const std::string &key = combs[rand()%comb_n];
            count_h[key]++;
        }
        std::cout<<"Fine hashtable\n";
    }

    {
        std::cout<<"Map\n";
        std::map<std::string, unsigned> count_h;
        for(int i=0; i<tot_count*comb_n; ++i) {
            const std::string &key = combs[rand()%comb_n];
            count_h[key]++;
        }
        std::cout<<"Fine map\n";
    }
    return 0;
}

I risultati:

[mitalia@mitalia ~/scratch/lookup]$ stdbuf -o0 ./lookup.x | ts -i '%.s'
0.000017 Lineare
34.237293 Fine lineare!
0.000084 Dicotomica
6.239760 Fine dicotomica
0.000086 Hashtable
1.640778 Fine hashtable
0.000086 Map
3.793371 Fine map

(i valori che contano sono quelli delle righe "Fine xxx", e si riferiscono a 233*172400 lookup fatti in ordine casuale)

Vince la hashtable di default fornita con libstdc++, che sembra usare murmurhash2 come funzione di hashing.