[C] Funzione di hashing da 16bit

[zacca94]

Sempre queste

[Scara95]

Mi sembra di capire che ab e choices rappresentino la stessa cosa, la sua lunghezza è fissa? E' 5 o 7?

[zacca94]

Mi sembra di capire che ab e choices rappresentino la stessa cosa

Si, rappresentano la stessa cosa. Se noti il codice dell'hashtable faccio 3 combinazioni nel main (era per semplificare il codice e non aggiungere l'algoritmo che estrae casualmente gli indici, in quanto poi nella pratica sono anche due file differenti).

Sempre 5, altrimenti sarebbero più di 232 combinazioni.

[zacca94]

Questo è il sunto:

 *    HASHTABLE     real    1m4.228s
 *                  user    1m4.164s
 *                  sys     0m0.000s
 * ----------------------------------------------------
 *    LINEAR        real    1m14.310s
 *                  user    1m14.256s
 *                  sys     0m0.024s
 * ----------------------------------------------------
 *    TRIE          real    0m51.717s
 *                  user    0m51.596s
 *                  sys     0m0.080s

La lineare però è passata da 1.60 a 1.14 nel momento in cui ho eliminato la verifica dell'esistenza del valore, inserendo nell'init le possibili combinazioni, quindi sono sicuro che se riuscissi a definire tutte le leaf in precedenza (nel giusto ordine) e poi nell'algoritmo di update aggiornare semplicemente il valore otterrei un grande incremento di prestazioni.

[Scara95]

Puoi utilizzare un array statico scrivendo le combinazioni come 3 bitmap di 5 elementi ciascuno. Ovvero 15 bit. Questo solo perché azbd equivale bdaz.
Quindi puoi rappresentare le righe in questo modo:

/* |r1   |r2      |r3
#|012 34|01  234|0 1234
0|111 00|00  001|0 0010

Massimo indice possibile:
0|111 00|00  011|0 0000 = 2^14+2^13+2^12+2^6+2^5 = 28768
*/

Ho preso il tuo codice da pastebin e ho fatto un'implementazione d'esempio: https://ideone.com/LeGG1K
I valori sono spostati di 1 rispetto al tuo campo data in quanto lo 0 marca un valore non inserito e 1 come inserito.
Nota comunque che ti basta l'operazione di update supponendo come default il valore 0: https://ideone.com/vnnASo

Questa invece è un'altra soluzione che utilizza una tire. Per come è costruita la tua funzione di generazione delle combinazioni ogni riga sarà sempre ordinata in ordine crescente quindi non c'è bisogno di ulteriori check.
Ogni chiave è lunga esattamente 7: i 5 valori più i 2 separatori, perciò è possibile utilizzare una union dato che a contenere dati saranno solamente i nodi foglia.
Anche qui si applicano le stesse constatazione dell'esempio precedente: valori spostati di 1 e basta update. Ho tuttavia lasciato exists per far vedere che non è necessario arrivare in fondo per verificare l'esistenza.
https://ideone.com/oZ5sqU

Scusa se è scritto un po' male "a copia e incolla"

Edit: ah, dimenticavo una cosa, io come dimensione iniziale del vettore della trie ho messo 1, ma sarebbe più ragionevole preallocare con una dimensione stimata.

[zacca94]

Scusa se è scritto un po' male "a copia e incolla"

Ah vai tranquillo.

Ho tuttavia lasciato exists per far vedere che non è necessario arrivare in fondo per verificare l'esistenza.

Si nella mia trie ho fatto più o meno lo stesso (ma io da povero comune mortale che non scorre i bit [riferito all'esempio precedente] ho semplicemente ciclato i valori fermandomi quando erano stati inseriti 5 elementi).

Avrei voglia di implementarlo e vedere che prestazioni ottengono le tua ma, sfortunatamente, devo svegliarmi presto, perciò domani posto i tuoi results.

[Scara95]

Neanche io sulle tre ho utilizzato un bit

[Scara95]

ho semplicemente ciclato i valori fermandomi quando erano stati inseriti 5 elementi

è sbagliato: 12|34|5 = 123|45| = 1|2345| = ||12345

[Scara95]

Un altra nota di cui mi ero dimenticato:
tu calcoli l'hash con qualcosa del tipo:

int i = 0;
unsigned long hash = 0;
while(hash < ULONG_MAX && i < 7) {
   hash += key[i];
   hash = hash << 8;
  ++i;
}

Ora, non riesco a ricordare il codice esatto ma era un qualcosa di simile. Vorrei farti notare che in questo modo il ciclo while si fermerebbe solo quando è arrivato in fondo alla stringa o se dovesse per coincidenza trovarsi uguale a ULONG_MAX (impossibile.). Infatti 0 <= hash <= ULONG_MAX per definizione. Perciò quella tecnica prende in considerazione solo gli ultimi 4/8 byte di una stringa (32/64 bit). Tuttavia tu successivamente effettui un %2^16 (sempre se non ricordo male) ciò implica che stai considerando solo gli ultimi 2 byte di questi ultimi 4/8 byte. Ovvero stai utilizzando solo 10 slot della hashtable e poi facendo una ricerca lineare: 5 per ogni scelta di 2 lettere più 5 nel caso l'ultimo carattere sia un separatore preceduto da una combinazione (e le seconde lettere siano tutte diverse, cosa che non ricordo) (non possono esserci 2 separatori come ultimi caratteri per costruzione in quanto la prima riga può contenere solamente 3 valori quindi o la seconda o la terza ne conterranno sempre almeno 1)

[zacca94]

Perdona una domande, perchè usi 15 bit e non 13?
Oltre al fatto che gli indici, errore mio sono stato poco chiaro, possono assumere un valore fino a 52/53 (ora non ricordo di preciso).

EDIT: Potrei modificare questo post nel proseguimento della lettura delle tue implementazioni.

Comunque vadano anche i soli indici 1-2-3-4-5, in fondo posso aggiungere un "hook" che converta e riconverta fra IO

p.s. permettimi di dirti che sei molto talentuoso