Newsgroup: it.comp.lang.perl
Titolo: hash e memoria

ciao a tutti
devo caricare un grande hash con chiavi potenzialmente molto lunghe.
Per salvare un po' di memoria, ha senso inventarsi un algoritmo di
compressione della chiave o questo procedimento viene gia' fatto dal
Perl ?
 Raffaello
Esempio:
$big_string = "lsifhgkljsafgnkasfjgnajfgnakljfnhakfnhlkadfnhakjdfnhkajdfn
sdhljafgnasnfgkasfngkjfgakfgkafjaksjfgbalksjnglksndgajksglkajsfgkasjfgn";
$big_hash{$big_string} = $a_value;
 oppure
$big_hash{ comprimi ($big_string) } = $a_value;

Il Tue, 24 Jun 2003 10:47:45 +0200, Raffaello Galli ha scritto:
[CUT]
Scusa se non rispondo, ma colgo la palla al balzo per fare una domanda:
C'è un modo per farsi restituire la dimensione di una variabile?
(all'incirca come l'istruzione sizeof del C?)
Grazie,
-- 
+--------+ ASCII ribbon campaign ( )
|  kral  |  - against HTML email  X 
+--------+              & vCards / \

 (all'incirca come l'istruzione sizeof del C?)
Devel::Size
ciao,
Stefano

 Perl ?
Con il modulo che mi ha suggerito il buon larsen (Devel::Size), potresti
fare delle prove e vedere quale differenza ottieni in termini di
memoria. Non so suggerirti algoritmi per comprimere le chiavi. (Forse
con Digest::MD5).
Ciao,


 con Digest::MD5).
Quando ho tempo faro' delle prove e vi faro' sapere i risultati.
Grazie
 Raffaello

compressione della chiave 
Perchè inventare? usa Digest::MD5 per calcolare il digest di ogni
stringa originale che non vuoi usare come key e usa il valore
esadecimale del digest (stringa) come key vera intercettando nella
hash l'evento (*estremamente* improbabile) di un digest duplicato. In
questo modo l'occupazione di memoria in funzione del numero di entries
è predicibile. 
Ciao



Mi serve una valutazione **precisa** di questa *estrema* improbabilita'.
 Raffaello

The algorithm takes as input a message of arbitrary length and produces as output a 128-bit ``fingerprint'' or ``message digest'' of the input.
e quindi usando MD5 stai effettivamente mappando l' insieme di
possibili chiavi di arbitraria lunghezza della tua hash in un universo
di 3 punto 4 e rotti elevato dieci alla 28 possibili stringhe con un
algoritmo che è studiato apposta per massimizzare la distanza tra
stringhe di ingresso arbitrariamente vicine. Difficile far di meglio,
per gestire le chiavi di una hash (salvo usare algoritmi analoghi)
Una valutazione 'spannometrica' della probabilità? Dividi il numero di
chiavi della tua hash per 2 alla 128 (non corretto ma attendibile se
devi gestire fino a solo solo pochi miliardi di chiavi)
Se la valutazione spannometrica non ti basta, mi spiace, non conosco a
sufficienza l'algoritmo per dirti come eventuali correlazioni presenti
nei dati si traducano in pattern delle stringhe in uscita ma MD5, per
quanto ne so io, dovrebbe funzionare proprio da decorrelatore.
Se la diffidenza persiste ti fai un brevissimo script che genera le
chiavi che ti interessano, trasformi secondo MD5 e memorizzi la tua
hash da qualche parte, ti costruisci la logica che intercetta l'
evento di duplicazione, ti costruisci infine la statistica relativa .
Ma dovrai aspettare parecchio prima di vedere il primo evento, credo.
Ma tutto questo è perfettamente inutile in quanto a te non serve la
garanzia di non generare mai un evento di chiave duplicata; a te serve
solo sapere che una certa chiave è duplicata. So che quanto segue è
banale.
-generi la tua stringa in ingresso S;
-generi M, la tua hash MD5
-se M non esiste nella hash H di accesso ai dati usi quella chiave;
-se M esiste nella hash H di accesso ai dati usi come chiave S e
inserisci S nella hash D dei duplicati.
conversamente, per l' accesso ai dati, guardi prima se S è presenti in
D; se lo è è un duplicato e accedi direttamente ad H con S; se non lo
è accedi ai dati con M.
Tu sai certamente meglio di me come l'accesso alle hash in perl è
sufficientemente efficiente; se puoi tollerare l'overhead marginale
del doppio accesso puoi risparmiare una quantità di spazio
semplicemente enorme (e, soprattutto, facilmente calcolabile).
Ciao