[C] Funzione di hashing da 16bit

[Scara95]

Perdona una domande, perchè usi 15 bit e non 13?

Utilizzo 15 bit perché per vedere quali elementi sono presenti in una riga servono almeno n bit dove n = |valori_fra_cui_scegliere| = 5 nel nostro caso e ci sono 3 righe per cui n*3=5*3=15.

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).

Non ha importanza, fintanto che ne utilizzi al massimo 5 per volta puoi sempre numerarli da 0 a 4.

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

Attenzione: [0,4] o[0,5) se preferisci

Comunque calcolando tutte le esatte combinazioni possibili in python ne risultano 224 e con un piccolo aiuto sempre di python puoi rappresentare il tutto in 226 celle

Script in python (scritto gran male ma chi ha voglia di scrivere bene codice usa e getta): https://ideone.com/ked4iV
Sempre il tuo esempio modificato: https://ideone.com/SQjy5X
Run dello script in python per generare una dimensione che sia una potenza di 2 in modo che l'operazione di resto possa essere ottimizzata: https://ideone.com/EFULyC
(con la tecnica che ho usato mi salta il 256 ma probabilmente c'è una qualche altra tecnica che ti permette di starci dentro)

(Commento inutile: io proprio non so scrivere in python)

[zacca94]

Comunque calcolando tutte le esatte combinazioni possibili in python ne risultano 224 e con un piccolo aiuto sempre di python puoi rappresentare il tutto in 226 celle

Scusa ma se stiamo parlando della stessa cosa, le combinazioni sono 232

from random import randint

choices  = [0, 1, 2, 3, 4];
combos   = [[], [], []]
elements = {}

for i in range(100000):
    for x in range(5):
        rndRow = randint(0, 2)
        rndIdx = randint(0, len(choices)-1)
        rndEl  = choices[rndIdx]

        del choices[rndIdx]

        if rndRow == 0:
            if len(combos[0]) < 3:
                combos[0].append(str(rndEl))
            elif randint(0, 1) == 0:
                combos[1].append(str(rndEl))
            else:
                combos[2].append(str(rndEl))

        elif rndRow == 1:
            combos[1].append(str(rndEl))
        elif rndRow == 2:
            combos[2].append(str(rndEl))


    key = str(sorted(combos[0])) + \
          str(sorted(combos[1])) + \
          str(sorted(combos[2]))

    if key not in elements:
        elements[key] = 0;

    choices  = [0, 1, 2, 3, 4];
    combos   = [[], [], []]

print len(elements)
#for e in elements:
#    print e

matias@matias-desktop:~/Desktop$ python test.py
232



Comunque ho implementato la tua lineare, con qualche piccola modifica (avevo bisogno di verificare la combinazione che avesse il maggior punteggio).
https://pastebin.com/w301ADdi

Direi che per il momento è la migliore:

real    0m48.190s
user    0m48.048s
sys    0m0.004s

Utilizzo 15 bit perché per vedere quali elementi sono presenti in una riga servono almeno n bit dove n = |valori_fra_cui_scegliere| = 5 nel nostro caso e ci sono 3 righe per cui n*3=5*3=15.

Continuo a non capire perchè la prima riga ha massimo 3 valori.

[Scara95]

Hai ragione, quindi mi sono perso qualche combinazione, devo solo capire quali

[Scara95]

Poco male, se non sai dove hai sbagliato riscrivi e.e
Python aggiornato:
pow2: https://ideone.com/7mFcof
min: https://ideone.com/2BuPTs
Il tuo esempio (dove l'unica cosa che ho modificato è mettere i valori per l'hashtable giusti così non ci sono clash xD): https://ideone.com/Kaif3G

[zacca94]

Aggiornato il codice con:

    INT32 htKey = HT_lookup( key );

    HT_TABLE[ htKey ][ 0 ]++;
    HT_TABLE[ htKey ][ 1 ] += points;

    //FLOAT32 avg = ( FLOAT32 )combs[ key ][ 1 ] / ( FLOAT32 )combs[ key ][ 0 ];
    FLOAT32 avg = ( FLOAT32 )HT_TABLE[ htKey ][ 1 ] / ( FLOAT32 )HT_TABLE[ htKey ][ 0 ];

al posto di

    combs[ key ][ 0 ]++;
    combs[ key ][ 1 ] += points;
 
    FLOAT32 avg = ( FLOAT32 )combs[ key ][ 1 ] / ( FLOAT32 )combs[ key ][ 0 ];

Ma in definitiva le prestazioni sono quasi identiche:
matias@matias-desktop:~/Desktop/Delilah.AI/sources$ time ./make/a.out
Best solution: 4 5 6 7 8

real 0m48.625s
user 0m48.604s
sys 0m0.000s

[Scara95]

edit vari
uhm, hai cambiato anche la definizione di HT_lookup spero >_>

Se non hai aggiornato la definizione di HT_lookup avresti dovuto fare qualcosa del tipo

HT_lookup(key)[ 0 ]++; 
HT_lookup(key)[ 1 ] += points;

FLOAT32 avg = ( FLOAT32) HT_lookup(key)[ 1 ] / ( FLOAT32 )HT_lookup(key)[ 0 ];

Altrimenti se vuoi solo calcolare la chiave (una volta sola ma il compilatore dovrebbe essere in grado di ottimizzare comunque) puoi aggiungere una macro:

#define HT_key(i) (((i)+HT_SHIFTS[(i)/HT_SIZE])%HT_SIZE)

Attento a chiamare quelle macro con come parametro ad esempio una chiamata a una funzione con side_effects o con un tempo di calcolo imponente perché i viene ripetuto e quindi calcolato 2 volte. Soluzioni: non farlo, scrivere una funzione al posto di una macro, dichiarare la funzione che chiami pure in uno dei svariati modi e sperare che il compilatore sia intelligente.


Comunque sì, plausibile diano risultati simili, era solo per non sprecare spazio

[Scara95]

Per rispondere a una cosa che mi ero perso:

[QUOTEUtilizzo 15 bit perché per vedere quali elementi sono presenti in una riga servono almeno n bit dove n = |valori_fra_cui_scegliere| = 5 nel nostro caso e ci sono 3 righe per cui n*3=5*3=15.

Continuo a non capire perchè la prima riga ha massimo 3 valori.[/QUOTE]
La prima può contenere solamente 3 elementi ma i valori fra cui scegliere sono 5 e siccome con un bit puoi segnare solamente presenza o assenza per segnarlo per 5 elementi ti servono 5 bit

[zacca94]

uhm, hai cambiato anche la definizione di HT_lookup spero >_>

hahaha ovvio... anche perchè altrimenti come faceva a funzionare
Ora proviamo la tua trie.

matias@matias-desktop:~/Desktop/Delilah.AI/sources$ time ./make/a.out
Best solution: 4 5 6 7 8

real    0m54.895s
user    0m50.600s
sys    0m4.196s

E qui vince la mia per qualche secondo

Ma onestamente non mi convince... secondo me si può fare il mashup della mia con la tua e ottenere un notevole incremento prestazionale.

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

Mi ero scordato di risponderti dicendoti che contavo i "|".

Da una parte ci spero che la tua lineare rimanga la migliore, perchè è troppo bello come la hai concepita (ho puttato persino i tuoi file .py nella carte /sources).

Non so tu, ma io mi sto divertendo un casino.

[Scara95]

Non è lineare ma hashing comunque

[zacca94]

Non è lineare ma hashing comunque

effettivamente non la scorri... non so perchè ho presupposto fosse lineare