View Full Version : [C] Identificazione univoca insiemi
fracarro
14-02-2008, 09:15
Salve ragazzi,
ho un problemino da risolvere e mi servirebbe qualche esperto in matematica e programmazione. Allora, io ho il mio insieme di elementi N={1,2,3,......,1000} da cui in base a certe operazioni genero un sottoinsieme di dimensione variabile, es. S1={5,24,134,432,567,700,876}. Ora il mio problema è trovare un sistema per assegnare una chiave univoca a questo insieme di elementi che lo distingua da qualsiasi altro insieme (di dimensione anche differente da S1) generabile da N.
Un modo per ottenere questo risultato è assegnare ad ogni elemento di N un numero primo. Dopodichè dato S1 mi basta moltiplicare i numeri primi associati ai suoi elementi per ottenere una chiave univoca. Il problema però è che moltiplicare tanti numeri primi mi genera delle chiavi spaventose quindi avrei bisogno di qualche altro modo per generare queste chiavi. Qualche idea?
se vuoi la certezza matematica avrai chiavi spaventosamente lunghe.
Se invece ti bassta un'ottima coperatura con una probabilita' decisamente bassa di conflitti allora ti puo' bastare una Hash.
Es: Metti tutti i numeri in fila, magari mettendoci anche la dimensione di ciascuno dei sotto-array, e passi tutti il flusso ad un algoritmo come
MD5
Ce ne sono tanti altri, questo e' uno dei piu' usati.
fracarro
14-02-2008, 11:14
se vuoi la certezza matematica avrai chiavi spaventosamente lunghe.
Se invece ti bassta un'ottima coperatura con una probabilita' decisamente bassa di conflitti allora ti puo' bastare una Hash.
Es: Metti tutti i numeri in fila, magari mettendoci anche la dimensione di ciascuno dei sotto-array, e passi tutti il flusso ad un algoritmo come
MD5
Ce ne sono tanti altri, questo e' uno dei piu' usati.
Esiste qualche implementazione in C di questo algoritmo? Inoltre il range delle "diverse" chiavi generate dall'algoritmo lo posso decidere io?
MD5 e' un algoritmo che restituisce sempre lo stesso spazio di 16byte di firma.
Come detto ce ne sono tanti altri, ma lo spazio della firma mi risulta sia fisso su ciascuno di essi. Cerca quello che ti piace di piu' e provalo.
Altri sono quelli della famiglia SHA
Ci sono anche quelli della famiglia CRC.
Per quanto riguarda l'implementazione invece ovviamente penso esistano implementazioni e librerie di tutti questi algoritmi in C, ma in C non saprei dove dirti di guardare. Piu' probabile C++, anche se su alcune librerie embedded si trova veramente di tutto.
In C# per esempio MD5 e' gia' in libreria, gia' dentro il framework, quindi e' una sola semplice chiamata. Se ti stai rivolgendo al mondo embedded prova anche a valutare il MicroFramwork, che si puo' montare su molti microprocessori del campo (ma non sono assolutamente esperto).
Per quanto riguarda il CRC vesione 32 pensa che negli x86, nella estensione delle istruzioni macchina SSE4.2 (introdotta sui Pentium4 Nehalem) esiste gia' addirittura hardware, sotto il codice opcode appunto CRC32.
Ti basterebbe quindi aprire una
__asm{
//qualcosina
CRC32
//qualcos'altro
}
fracarro
14-02-2008, 11:50
MD5 e' un algoritmo che restituisce sempre lo stesso spazio di 16byte di firma.
Come detto ce ne sono tanti altri, ma lo spazio della firma mi risulta sia fisso su ciascuno di essi. Cerca quello che ti piace di piu' e provalo.
Altri sono quelli della famiglia SHA
Ci sono anche quelli della famiglia CRC.
Per quanto riguarda l'implementazione invece ovviamente penso esistano implementazioni e librerie di tutti questi algoritmi in C, ma in C non saprei dove dirti di guardare. Piu' probabile C++, anche se su alcune librerie embedded si trova veramente di tutto.
In C# per esempio MD5 e' gia' in libreria, gia' dentro il framework, quindi e' una sola semplice chiamata. Se ti stai rivolgendo al mondo embedded prova anche a valutare il MicroFramwork, che si puo' montare su molti microprocessori del campo (ma non sono assolutamente esperto).
Per quanto riguarda il CRC vesione 32 pensa che negli x86, nella estensione delle istruzioni macchina SSE4.2 (introdotta sui Pentium4 Nehalem) esiste gia' addirittura hardware, sotto il codice opcode appunto CRC32.
Ti basterebbe quindi aprire una
__asm{
//qualcosina
CRC32
//qualcos'altro
}
Purtroppo a me serve in C e da utilizzare sia sotto windows che sotto linux. Ad ogni modo credo di aver trovato la soluzione qui: http://www.hwupgrade.it/forum/showthread.php?t=1508117&highlight=md5
Non mi resta che provare. Ad ogni modo grazie per l'aiuto.
P.S. Dati due insiemi per verificare se sono uguali mi basta generare le stringhe ad essi associate (concatenando semplicemente i numeri), passarle all'MD5 e poi usare la strcmp sulle due stringhe ritornate da questo algoritmo.
P.S. Dati due insiemi per verificare se sono uguali mi basta generare le stringhe ad essi associate (concatenando semplicemente i numeri), passarle all'MD5 e poi usare la strcmp sulle due stringhe ritornate da questo algoritmo.
Esatto. Nel caso in cui le 2 stringhe del MD5 siano diverse sei sicuro che i due insiemi erano diversi gia' in origine.
Se invece le 2 stringhe sono uguali, per avere la certezza dovrai controllarle direttamente. Cosi' funzionano le Hastable.
fracarro
14-02-2008, 12:21
Esatto. Nel caso in cui le 2 stringhe del MD5 siano diverse sei sicuro che i due insiemi erano diversi gia' in origine.
Se invece le 2 stringhe sono uguali, per avere la certezza dovrai controllarle direttamente. Cosi' funzionano le Hastable.
Tutto chiaro. Ora stabilito come assegnare ad ogni insieme una chiave diverse dovrei risolvere il secondo problema riguardante l'efficienza. Io ho una lista di insiemi (e quindi di rispettive chiavi) e un nuovo insieme S1. Per controllare se S1 già appartiene a questa lista il modo più semplice è scorrerla e verificare ad uno ad uno le stringhe generate dall'MD5. Non esiste un modo più furbo per fare la ricerca in tempo costante? ( O(1) per intenderci?).
Per esempio poichè le stringhe sono tutte differenti non c'è una funzione che restituisce un numero a seconda della stringa datagli in input? Se invoco l'atoi per fare una cosa del genere i numeri restituiti saranno differenti? Perchè in questo modo potrei generarmi un array booleano e verificare in tempo costante se S1 appartiene alla lista.
Stai reinventando l'hashtable, che ha proprio complessita' O(1)
Cerca una libreria per l'hashtable, una per l'MD5, cucini a fuoco lento ed hai finito.
fracarro
14-02-2008, 13:13
Stai reinventando l'hashtable, che ha proprio complessita' O(1)
Cerca una libreria per l'hashtable, una per l'MD5, cucini a fuoco lento ed hai finito.
non potresti indicarmene qualcuna? Magari che hai utilizzato in passato e con cui ti sei trovato bene?
Purtroppo in C non ne conosco, anche se cercando con google ne ho appena trovate tantissime. Non saprei consigliarti, ma ovviamente sembrano abbastanza complesse.
Personalmente le hastable le uso tutti i giorni, ma in C# (conosciute con il nome di Dictionary)
Ma perche' proprio C e non almeno C++? Forse in C++ qualche template samplice riesci a trovarlo.
Davvero penso che oggi il C sia limitato al mondo embedded, e anche li' piano piano lo stanno lasciando.
Fra l'altro, se la tua utility non e' un'utility grafica, oppure se fa uso regolare delle finestre allora potresti valutare di scrivere il codice in C# e farlo funzionare sia sotto Windows che sotto Linux (progetto MONO), oppure in Java, e farlo funzionare poi sotto qualche java virtual machine.
Io oggi seguirei questa strada, per non perdersi in tecnicismi che possono deviare i tuoi sforzi da quello che e' il vero studio della tua utility.
Manbearpig
14-02-2008, 15:21
se hai bisogno di identificare solo sottoinsiemi semplici e non multiinsiemi allora potresti vedere ogni sottoinsieme come una stringa di bit dove un bit e' posto a 1 se l'elemento e' presente ed e' posto a 0 se l'elemento non e' presente. Es. {0,3,7} = 1001000100000000000...
trasformi la stringa binaria in un intero e hai una chiave.
Se non ho capito male il problema e' diverso.
Vorrebbe che i 2 insiemi
{2,4,8} e {4,8,2} siano considerati diversi.
Manbearpig
14-02-2008, 15:35
Beh per definizione un isieme non e' ordinato. In ogni caso ho detto una stronzata prima convertirlo in un intero non e' possibile... (1000 bit)
Cmq potrebbe tenersi la stringa di bit come identificatore
fracarro
14-02-2008, 16:10
Allora per quanto riguarda {2,4,6} e {2,6,4} per me sono la stessa cosa proprio perchè insiemi. Tuttavia la soluzione con i bit se da un lato risparmia in memoria e mi permette di effettuare il confronto tra due insiemi velocemente tramite l'and bit a bit dall'altro mi costringerebbe a verificare la lista dei insiemi per intero, per questo ho scartato l'ipotesi dei bit.
A questo punto l'unica soluzione mi sembra quella di trovare una libreria (più semplice possibile) per l'hashtable come consigliato gugoXX.
Riguardo il mio codice sono algoritmi di ottimizzazione quindi niente grafica e finestre. Una semplice linea di comando per risolvere un determinato problema di ottimizzazione. (Gli insiemi registrati nella hash table non sono altro che gli elementi di una tabu list e siccome devo verificare velocemente se una "mossa" è tabu devo sapere velocemente se un insieme appartiene o meno all'hashtable).
Manbearpig
14-02-2008, 16:30
Il problema dell'hashtable sono le collisioni, avrai quindi insiemi diversi con lo stesso hash in quel caso dovrai confrontare tutti gli elementi dell'insieme con tutti gli insiemi che hanno lo stesso hash. nel peggiore dei casi hai 1000*1000*k confronti, dove k e' il numero di collisioni.
Manbearpig
14-02-2008, 16:33
Una soluzione ibrida probabilmente e' la cosa migliore, usi una hashtable nella quale memorizzi i tuoi valori sotto forma di stringhe di bit, in questo modo in caso di collisione puoi fare i confronti molto velocemente.
No, guarda, allora ti consiglio di utilizzare un ibrido della mia soluzione e quella di Manbearpig, perche' avevo sopravvalutato il problema.
Con la soluzione di Manbearpig ti calcoli la chiave di ogni tuo insieme. (1000bit = 62byte invece che 32 dell'MD5)
Con una hashtable mantieni l'insieme di tutti gli elementi, controllando l'esistenza in O(1).
La hastable non e' altro che un vettore di oggetti, il cui indice, chiamato chiave, non e' un intero come nei vettori normali, ma sono altri oggetti.
Giusto per spiegarti un funzionamento:
Se sei su linea di comando JAVA o C# e vai a nozze sia sotto Linux che sotto Windows.
Forse bisogna aggiungere qualcosa sul comparatore di eguaglianza del tipo byte[], ma non sono sicuro.
class Program
{
static void Main(string[] args)
{
//Inizializzo la hastable
//TaleHashTable in questa implementazione restituisce, dato un risultato compattato in bit, quello che era l'insieme degli interi originari.
// Se la hash la usi solo per testare l'esistenza del tuo risultato allora e' ancora piu' semplice.
Dictionary<byte[], List<int>> MyMem = new Dictionary<byte[], List<int>>();
do
{
//Leggo una nuova lista in qualche modo
List<int> nuovo=GenerateNuovoInsieme();
//Ne calcolo il risultato;
List<int> risultato = FromInisiemeToRisultato(nuovo);
//Compatto il risultato in bit, invece che usare l'MD5
byte[] RisultatoCompattato=CompactRisultato(risultato);
//Lavoro sulla hash
if (MyMem.ContainsKey(RisultatoCompattato))
{
//Qui il codice di che faccio se gia' ce l'ho
}
else
{
//Qui il codice di che faccio se non ce l'ho, oltre a memorizzarlo nella hash
MyMem[RisultatoCompattato] = nuovo;
}
} while (Console.ReadKey().Key!=ConsoleKey.Escape);
}
static List<int> FromInisiemeToRisultato(List<int> Insieme)
{
List<int> ret = new List<int>();
// qui il codice per calcolare l'insieme risultato dato l'insieme di ingresso
return ret;
}
static byte[] CompactRisultato(List<int> risultato)
{
byte[] ret=new byte[64];
//Qui il codice di ManBearPig per compattare una lista in un array di byte
return ret;
}
static List<int> GenerateNuovoInsieme()
{
List<int> ret = new List<int>();
// qui il codice per riempire l'insieme;
return ret;
}
}
fracarro
14-02-2008, 17:00
No, guarda, allora ti consiglio di utilizzare un ibrido della mia soluzione e quella di Manbearpig, perche' avevo sopravvalutato il problema.
Con la soluzione di Manbearpig ti calcoli la chiave di ogni tuo insieme. (1000bit = 62byte invece che 32 dell'MD5)
Con una hashtable mantieni l'insieme di tutti gli elementi, controllando l'esistenza in O(1).
La hastable non e' altro che un vettore di oggetti, il cui indice, chiamato chiave, non e' un intero come nei vettori normali, ma sono altri oggetti.
Giusto per spiegarti un funzionamento:
Se sei su linea di comando JAVA o C# e vai a nozze sia sotto Linux che sotto Windows.
Forse bisogna aggiungere qualcosa sul comparatore di eguaglianza del tipo byte[], ma non sono sicuro.
....
A me sembra invece più efficiente usare soltanto la hashtable senza creare la chiave tramite i bit (anche perchè non mi interessa risolvere eventuali conflitti nella hashtable). Mi spiego meglio. Se per esempio devo rappresentare l'insieme {2,7,4,9} io prima me lo ordino e poi genero la stringa str=2,7,4,9 che rappresenta la mia chiave. Da li poi uso la hashtable. Se invece la chiave la devo generare usando i bit sono costretto (almeno credo) a a inizializzarli tutti a zero e poi a settare ad uno solo quelli corrispondenti agli elementi dell'insieme. Se è così la prima soluzione è più efficiente.
Manbearpig
14-02-2008, 17:14
A me sembra invece più efficiente usare soltanto la hashtable senza creare la chiave tramite i bit (anche perchè non mi interessa risolvere eventuali conflitti nella hashtable). Mi spiego meglio. Se per esempio devo rappresentare l'insieme {2,7,4,9} io prima me lo ordino e poi genero la stringa str=2,7,4,9 che rappresenta la mia chiave. Da li poi uso la hashtable. Se invece la chiave la devo generare usando i bit sono costretto (almeno credo) a a inizializzarli tutti a zero e poi a settare ad uno solo quelli corrispondenti agli elementi dell'insieme. Se è così la prima soluzione è più efficiente.
Beh si e' una buona soluzione, in ogni caso i conflitti in qualche modo dovrai gestirli... ordinando gli insiemi riduci il costo del confronto in caso di conflitto ma hai il costo di ordinare tutti gli insiemi. Cosa in effetti sia piu' efficente dipende molto dall'istanza del problema.
Per quanto riguarda il settare i bit a zero ti basterebbe una memset che ha costo pari a zero, e per settare i bit a 1 ti basta scorrere una volta gli elementi dell'insieme.
Risposta da ignorante: e se invece ti costruisci degli alberi del tipo:
2
| - 3 - 4
| - 145
7
| - 456
per rappresentare ad es. gli insiemi {2,3,4}, {2,145}, {7,456}
e mentre crei un nuovo insieme confronti il primo elemento con le radici,
se non lo trovi l'insieme è nuovo (crei un nuovo albero),
se lo trovi confronti il secondo el. con i figli della radice, e così via,
finché non trovi l'elemento (insieme nuovo -> aggiungi un sottoalbero).
Nel caso sopra se generi l'insieme {2, 145, 146} al terzo tentativo saprai che
è nuovo, in quanto 145 non ha figli.
Forse questa roba ha anche un nome, ma io che sono un pozzo di ignoranza non lo so :fagiano:
A me sembra invece più efficiente usare soltanto la hashtable senza creare la chiave tramite i bit (anche perchè non mi interessa risolvere eventuali conflitti nella hashtable). Mi spiego meglio. Se per esempio devo rappresentare l'insieme {2,7,4,9} io prima me lo ordino e poi genero la stringa str=2,7,4,9 che rappresenta la mia chiave. Da li poi uso la hashtable. Se invece la chiave la devo generare usando i bit sono costretto (almeno credo) a a inizializzarli tutti a zero e poi a settare ad uno solo quelli corrispondenti agli elementi dell'insieme. Se è così la prima soluzione è più efficiente.
Se la quantita' di numeri e' bassa va bene.
Ma se puoi avere anche 200,300 numeri, allora la stringa diventa un po' lunga.
Nulla che non si possa gestire con la hastable, certo.
Per calcolare l'array di bit non devi neppure ordinare i numeri (risparmio minimo comunque)
A questo punto fallo prima con la hastable di stringhe, poi se vuoi ottimizzare ti diverti dopo.
Imho se vuoi puoi semplificare di molto l'hash.
Usa un hash a tre livelli: somma e prodotto in modulo 2^8 e numeor di elementi.
La probabilità di collisioni è molto bassa e non devi ordinare i vettori ;)
Se ci sono più insiemi con stessa somma e prodotto ovviamente devi gestirti una lista e fare i confronti con il numero degli elementi ed eventualmente il confronto elemento per elemento (visto che gli insiemi non sono ordinati).
struct list
{
int *vector;
int size;
struct list * next;
};
Dovrai allocarti un
struct list * hashtable[256][256];
Quindi per verificare se esiste in hash un dato insieme ti basta fare la somma e il prodotto in modulo 256, indicizzare con il risultato la hashtable e se ottieni un puntatore non NULL ti scorri la lista verificando il numero degli elementi (size nell'esempio). Se trovi un candidato valido (cioè ha size uguale a quella cerchi) devi fare il confronto elemento per elemento.
Un modo ancora più furbo per ottimizzare sarebbe fare l'inserimento degli elementi in ordine di size (far un inserimento in ordine ha costo O(n) con n il numero degli elementi nella lista, ma con un andamento casuale della dimensione siamo nell'ordine di una media di n/2).
fracarro
15-02-2008, 11:37
Imho se vuoi puoi semplificare di molto l'hash.
Usa un hash a tre livelli: somma e prodotto in modulo 2^8 e numeor di elementi.
La probabilità di collisioni è molto bassa e non devi ordinare i vettori ;)
Se ci sono più insiemi con stessa somma e prodotto ovviamente devi gestirti una lista e fare i confronti con il numero degli elementi ed eventualmente il confronto elemento per elemento (visto che gli insiemi non sono ordinati).
struct list
{
int *vector;
int size;
struct list * next;
};
Dovrai allocarti un
struct list * hashtable[256][256];
Quindi per verificare se esiste in hash un dato insieme ti basta fare la somma e il prodotto in modulo 256, indicizzare con il risultato la hashtable e se ottieni un puntatore non NULL ti scorri la lista verificando il numero degli elementi (size nell'esempio). Se trovi un candidato valido (cioè ha size uguale a quella cerchi) devi fare il confronto elemento per elemento.
Un modo ancora più furbo per ottimizzare sarebbe fare l'inserimento degli elementi in ordine di size (far un inserimento in ordine ha costo O(n) con n il numero degli elementi nella lista, ma con un andamento casuale della dimensione siamo nell'ordine di una media di n/2).
Per quanto riguarda le collisione, nel mio caso posso evitare di gestirle. Mi interessa solo vedere se "la casella nella tabella hash" è già occupato o meno. Per quanto riguarda la tua funzione l'unico problema potrebbe essere il costo di computazione della chiave perchè con un insieme di 1000 elementi dovrei leggere 2000 numeri per produrre la somma ed il prodotto.
Ad ogni modo ieri ho fatto varie ricerche su internet per trovare una libreria che gestisse in modo semplicissimo una tabella hash e ho trovato questa: http://cbfalconer.home.att.net/download/hashlib.zip
Ora sto implementando le funzioni richieste (6 funzioni banali) e quanto prima proverò a vedere se funziona.
Voglio comunque ringraziare tutti voi per le vostre risposte.
banryu79
15-02-2008, 13:30
Riguardo il mio codice sono algoritmi di ottimizzazione quindi niente grafica e finestre. Una semplice linea di comando per risolvere un determinato problema di ottimizzazione. (Gli insiemi registrati nella hash table non sono altro che gli elementi di una tabu list e siccome devo verificare velocemente se una "mossa" è tabu devo sapere velocemente se un insieme appartiene o meno all'hashtable).
Si tratta di un algortimo di tabu search?
In Java esiste questa libreria -> OpenTS - Java Tabu Search Framework (http://www.coin-or.org/Ots/index.html)
Per quanto riguarda le collisione, nel mio caso posso evitare di gestirle. Mi interessa solo vedere se "la casella nella tabella hash" è già occupato o meno. Per quanto riguarda la tua funzione l'unico problema potrebbe essere il costo di computazione della chiave perchè con un insieme di 1000 elementi dovrei leggere 2000 numeri per produrre la somma ed il prodotto.
E' comunque O(n) ;)
Con l'ordinamento era O(n log n)...
fracarro
15-02-2008, 13:44
E' comunque O(n) ;)
Con l'ordinamento era O(n log n)...
Corretto, ma io mi sto rifacendo alla soluzione proposta da gugoXX rappresentando gli insiemi come stringhe di bit. In questo modo evito di effettuare gli ordinamenti e a quanto ne so qualunque operazione dovrò fare su di essi (azzeramento e inizializzazione ad 1) è velocissima. Anche se la complessità è la stessa in pratica usare i bit potrebbe velocizzare il tutto oltre ad evitarmi la gestione di numeri enormi ( moltiplicazione dei numeri da 1 a 1000 prima di effettuare il modulo).
Si tratta di un algortimo di tabu search?
In Java esiste questa libreria -> OpenTS - Java Tabu Search Framework
Si è un algoritmo di tabu seach, ma sfortunatamente è in C quindi non posso utilizzare Java.
Grazie a tutti e due comunque.
Manbearpig
15-02-2008, 13:59
Per quanto riguarda le collisione, nel mio caso posso evitare di gestirle. Mi interessa solo vedere se "la casella nella tabella hash" è già occupato o meno.
Io questa cosa ancora la devo capire... come fai a non considerare le collisioni?
Corretto, ma io mi sto rifacendo alla soluzione proposta da gugoXX rappresentando gli insiemi come stringhe di bit. In questo modo evito di effettuare gli ordinamenti e a quanto ne so qualunque operazione dovrò fare su di essi (azzeramento e inizializzazione ad 1) è velocissima. Anche se la complessità è la stessa in pratica usare i bit potrebbe velocizzare il tutto oltre ad evitarmi la gestione di numeri enormi ( moltiplicazione dei numeri da 1 a 1000 prima di effettuare il modulo).
Però hai detto che l'insieme {1, 2, 3} deve essere indistinguibile dall'insieme {3, 1, 2} e per questo se lavori sulle stringhe di bit devi ad ogni costo ordinarli.
Al contrario sfruttando somma e prodotto non devi ordinare.
Inoltre il risultato di somma e prodotto è comunque coerente operando in modulo (cioè se sfora non è un problema), quindi non ti devi assolutamente preoccupare di numeri grossi e piccoli.
Cioè:
unsigned int a = 1;
a *= 123
a *= 124321412;
a *= 32412341234;
In a hai lo stesso risultato anche se inverti le righe anche se sfori il massimo degli interi.
Io questa cosa ancora la devo capire... come fai a non considerare le collisioni?
Infatti non mi torna, la collisione bisogna contarla perché due insiemi diversi possono avere lo stesso hash.
Manbearpig
15-02-2008, 14:12
Però hai detto che l'insieme {1, 2, 3} deve essere indistinguibile dall'insieme {3, 1, 2} e per questo se lavori sulle stringhe di bit devi ad ogni costo ordinarli.
No in realta' non e' necessario ordinarle, appunto essendo i due insiemi uguali in entrambi i casi poni a 1 i bit 1,2,3. Nel primo caso scorri gli elementi poni prima il bit 1 a 1 poi il bit 2 e il bit 3. Nel secondo caso poni a 1 prima il bit 3 poi l'1 e poi il 2.
No in realta' non e' necessario ordinarle, appunto essendo i due insiemi uguali in entrambi i casi poni a 1 i bit 1,2,3. Nel primo caso scorri gli elementi poni prima il bit 1 a 1 poi il bit 2 e il bit 3. Nel secondo caso poni a 1 prima il bit 3 poi l'1 e poi il 2.
E' uguale la cosa è improponibile. Devi fare una mappa di bit di 2^32 bit per coprire tutti gli interi ;)
Mi sembrava di aver capito che il numero piu' grande fosse circa 1000
Sarebbe quindi una stringa da 1000 bit.
128byte diciamo.
fracarro
15-02-2008, 14:19
No in realta' non e' necessario ordinarle, appunto essendo i due insiemi uguali in entrambi i casi poni a 1 i bit 1,2,3. Nel primo caso scorri gli elementi poni prima il bit 1 a 1 poi il bit 2 e il bit 3. Nel secondo caso poni a 1 prima il bit 3 poi l'1 e poi il 2.
Esatto questo è il modo per evitare l'ordinamento.
Per quanto riguarda le collisioni il motivo per cui le "trascuro" deriva dal fatto che le probabilità che si verifichino sono molto basse e quando si verifica una collisione mi limito a considerare tabu una mossa che potrebbe non esserlo. Questo "formalmente" potrebbe penalizzare il risultato finale dell'algoritmo ma per ora la cosa è accettabile (magari aggiungo in seguito la gestione delle collisioni se i risultati non mi soddisfano).
Per quanto riguarda il discorso del modulo non mi è chiaro l'esempio fatto. Supponiamo che il modulo sia 256 e che io debba calcolare la chiave come prodotto dei primi 1000 numeri interi. Non bisogna fare (1*2*3*4........*998*999*1000) % 256 ? Se si ovviamente il numero calcolato prima di applicare il modulo può essere enorme.
fracarro
15-02-2008, 14:22
E' uguale la cosa è improponibile. Devi fare una mappa di bit di 2^32 bit per coprire tutti gli interi ;)
Se la dimensione massima dei miei insiemi può essere composta da 1000 elementi mi basta una mappa di mille bit posti a zero o uno a seconda di quali siano effettivamente gli elementi che compongono l'insieme (sfrutto la loro posizione nella sequenza 1,2,3...999,1000).
Manbearpig
15-02-2008, 14:22
E' uguale la cosa è improponibile. Devi fare una mappa di bit di 2^32 bit per coprire tutti gli interi ;)
Ok sono d'accordo che in generale e' improponibile, ma nel suo caso da quel che ho capito gli insiemi contengono solo numeri da 1 a 1000.
Se la dimensione massima dei miei insiemi può essere composta da 1000 elementi mi basta una mappa di mille bit posti a zero o uno a seconda di quali siano effettivamente gli elementi che compongono l'insieme (sfrutto la loro posizione nella sequenza 1,2,3...999,1000).
Me l'ero perso...ma 1000 elementi al massimo o 1000 come numero massimo all'interno dell'insieme...la differenza è fondamentale.
fracarro
15-02-2008, 14:31
Me l'ero perso...ma 1000 elementi al massimo o 1000 come numero massimo all'interno dell'insieme...la differenza è fondamentale.
Per ora il mio limite è pari a 1000 elementi, ma questi elementi altro non sono che ID dei nodi di un grafo che quindi vengono scelti in sequenza da 1 a 1000. Ovviamente se decidessi di passare a 2000 elementi avrei i numeri da 1 a 2000 e così via. Quindi sempre la sequenza di numeri naturali da 1 al max_elementi.
Ok...allora va bene la mappa di bit.
fracarro
15-02-2008, 15:03
Dubbio. Poichè non ho sottomano i manuali e non ricordo molto riguardo i bit volevo chiedere come faccio a definire un maschera di 1000 bit posti a zero e poi settare "direttamente" quelli che voglio io a 1. Per pietà non ditemi che bisogna dividere la maschera in parole da 32 bit e gestirle una per una.
Per pietà non ditemi che bisogna dividere la maschera in parole da 32 bit e gestirle una per una.
Chiaro...ma è semplice da fare...
Fai un vettore di unsigned int e poi ti fai un paio di funzioni per settare il bit i-esimo e sei a posto.
fracarro
15-02-2008, 15:09
Chiaro...ma è semplice da fare...
Fai un vettore di unsigned int e poi ti fai un paio di funzioni per settare il bit i-esimo e sei a posto.
Speravo avessero creato qualche sistema nuova. Vabbè, allora ricapitolando mi tocca creare un array di unsigned int avente un numero di caselle x tale che 2^x e la più piccola potenza di 2 superiore a 1000 giusto (in questo acso x=2^10)? Definito questo array come faccio a settare i vari bit? Per esempio se voglio settare ad 1 il primo e quinto bit delle seconda e quarta cella dell'array come faccio? Avete qualche funzione da suggerire?
EDIT: x=10 non x=2^10
No...semplicemente allochi 1000 / (sizeof(int) * 8) interi.
fracarro
15-02-2008, 15:56
No...semplicemente allochi 1000 / (sizeof(int) * 8) interi.
Non dovrei allocare un array con sup (1000/sizeof(int)) celle?
Sì, ma ricordati che sizeof(int) ritorna 4, ma di bit ce ne stanno 32 in un int.
E' giusto comunque aggiungere un 1 intero se 1000 % (sizeof(int) * 8) > 0.
Manbearpig
15-02-2008, 16:05
Dovrebbe bastare una malloc((1000/8)+1)
Senza usare sizeof(int) che e' inutile.
Diventa inutile perché nella malloc bisogna moltiplicare di nuovo per sizeof(int)...ma se vuole sapere su quanti unsigned int deve lavorare quello è il modo ;)
Manbearpig
15-02-2008, 16:14
Diventa inutile perché nella malloc bisogna moltiplicare di nuovo per sizeof(int)..
e perche' mai? malloc prende come argomento un intero x e alloca x byte.
e perche' mai? malloc prende come argomento un intero x e alloca x byte.
Intendevo dire che se alloca un vettore di int con dimensione 1000 / (sizeof(int) * 8) + 1 e dopo deve passare il parametro a malloc ottiene la riduzione di sizeof(int) visto che deve allocare [(1000 / sizeof(int) * 8) + 1] * sizeof(int) byte, cioè 1000 / 8 + 4 byte.
Se vuole lavorare sui byte allora è un altro discorso. Io lavorerei sugli unsigned int, poi faccia lui.
Tra l'altro conviene usare calloc invece di malloc, con parametri:
v = (unsigned int *) calloc(1000 / (sizeof(int) * 8) + 1, sizeof(int));
Se invece si vuole usare i byte allora:
v = (unsigned char *) calloc(1000 / 8 + 1, 1);
fracarro
17-02-2008, 11:48
Allora. Sono riuscito ad impostare il tutto creando anche delle funzioni per settare direttamente i bit ma a questo punto sorge un altro problema.
Supposiamo che debba considerare un insieme di 128 bit quindi mi dichiaro un array di unsigned int di dimensione 4. Poi, sapendo che S={3,7,33} setto due bit nella prima cella dell'array e il terzo nella seconda cella ottenendo qualcosa del tipo:
cella 1: 0010001,.....,0
cella 2: 100,...,000
cella 3: 0...0
cella 4: 0...0
(N.B. Per evitare problemi di rappresentazione e cose del genere setto i bit in ai valori presenti in S leggendo gli insiemi da sinistra verso destra).
A questo punto dovrei "generare" la stringa univoca associata ad S da passare alla funzione hash, ma come la genero?
In modo rozzo potrei concatenare i numeri decimali presenti nella 4 caselle dell'array dividendoli con una virgola, ma forse sarebbe meglio convertire i 128 bit in una stringa di 0 e 1. Qualcuno sa come fare?
Ma scusa, abbiamo fatto tutto sto casino per avere un oggetto fatto di soli elementi binari e ora vuoi tornare alla stringa?
Potevi costruire la stringa subito allora, avresti risparmiato tutti gli OR e gli AND...
char pippo[128];
azzero pippo con tutti '0';
...
pippo[18]='1';
pippo[25]='1';
pippo[7]='1';
Che e' anche piu' facile, piu' corto, piu' leggibile e meno errori.
Comunque la hastable sarebbe funzionata direttamente anche con una struttura dei tuoi 4 unsigned int, senza per forza dover passare di nuovo alla stringa.
Manbearpig
17-02-2008, 12:03
beh se rappresenti il tutto con stringhe hai uno spreco non indifferente, usi un byte per ogni bit. Pero' potrebbe addirittura essere piu' veloce, potresti fare una prova mi interesserebbe vedere i risultati..
Cmq una funzione hash semplice potrebbe essere la somma dei 4 unsigned int mod(dimensione della hashtable).
fracarro
17-02-2008, 13:15
Una soluzione ibrida probabilmente e' la cosa migliore, usi una hashtable nella quale memorizzi i tuoi valori sotto forma di stringhe di bit, in questo modo in caso di collisione puoi fare i confronti molto velocemente.
Io stavo seguendo la logica riportata qui sopra. In pratica usando la stringa binario evito di dover ordinare gli insiemi e risparmio spazio, ma soprattutto potrei facilmente introdurre la gestione delle collisioni con un confronto su stringhe di bit che dovrebbe essere molto più veloce rispetto alla strcmp.
L'unica cosa che non mi è chiara però è che una volta costruito l'array con le 4 celle come faccio a passare questa stringa di 128 bit alla funzione hash?
Per la cronaca la funzione è questa:
void * hshinsert(hshtblptr master, void *item)
{
if ((TSPACE(master) <= 0) && !reorganize(master)) {
master->hstatus.herror |= hshTBLFULL;
return NULL;
}
return putintbl(master, item, 0);
} /* hshinsert */
Poichè in input prende un void* potrei passargli quello che voglio, secondo voi dandogli in nome dell'array lui correttamente effettuerà l'hash dei 128 bit? (magari potrei usare dei char invece che unsigned int per l'array così l'array stesso è automaticamente visto come una stringa. Ma i char non sono grossi come gli unsigned int,giusto?)
Manbearpig
17-02-2008, 13:31
Secondo me fai prima a fartela a mano la hashtable... alla fine non e' altro che un array di liste.
Per la funzione hash, cioe' quella che mappa una tua stringa di bit in una casella dell'array puoi usare la funzione che dicevo prima.
per la dimensione della hashtable usa un numero primo vedi qui (http://planetmath.org/encyclopedia/GoodHashTablePrimes.html). Quanto debba essere grande dipende da quanti elementi verranno inseriti, cmq e' meglio sovradimensionare se non vuoi avere troppe collisioni.
Poichè in input prende un void* potrei passargli quello che voglio, secondo voi dandogli in nome dell'array lui correttamente effettuerà l'hash dei 128 bit?
Qualsiasi cosa gli passi per lui è indifferente. Tanto converte a void *. Il problema è che non vedo alcune limitazione nella dimensione.
Non capisco perché tu voglia generare la stringa.
Anche secondo me conviene farti l'hash da solo.
Vuoi un semplice hash ? Fai la somma in modulo 2^16 degli interi che formano i dati e poi ci indicizzi un vettore di 2^16 puntatori a lista.
fracarro
18-02-2008, 09:40
Allora, il problema che stavo ponendo io era semplicemente come passare alla funzione hash la stringa di bit, indipendentemente da come viene gestita la tabella hash.
Quando Manbearpig dice: "Per la funzione hash, cioe' quella che mappa una tua stringa di bit in una casella dell'array ...", io vorrei capire "come" passo la stringa di bit alla funzione hash, una volta costruita.
Io pensavo di fare così. Supponendo di avere i soliti 128 bit da gestire, ho dichiarato un array di "5" caselle di "unsigned char". Nell'ultima casella ho messo il carattere di fine stringa '\0' mentre le prime 4 caselle sono utilizzare come al solito sui bit per rappresentare gli elementi dell'insieme S considerato. A questo punto una volta creata la stringa di bit passo il nome dell'array alla funzione hash e il gioco è fatto. Quanto prima verificherò se la cosa funziona.
Per chiarire le cose riguardo la tabella hash, il motivo per cui preferisco utilizzare una libreria esterna piuttosto che farmela da me risiede nella probabilità di ridurre le collisioni. Poichè io devo gestire insiemi derivati dai numeri naturali da 1 a 1000 e questi insiemi possono avere una qualsiasi dimensione, in teoria il numero di insiemi generabili è \sum_i=1^1000 binomial(1000,i) quindi un numero spaventoso. Ovviamente l'eurista genererà solo un piccolo sottoinsieme di questo numero ma a seconda dei criteri di arresto, del numero di miglioramenti prodotti dalla soluzione di partenza e del numero di iterazioni totali, questo numero di insiemi può arrivare a milioni. Per questo motivo usare algoritmi già implementati da qualcun'altro che riducono la possibilità di collisioni nonostante numeri elevati di elementi da inserire nella tabella hash erano ben graditi.
Come ti ho già detto c'0è qualcosa che non va nella libreria. Perché o quella libreria prende in input solo stringhe (limitate da \0), ed in tal caso non cpaisco perché sia vopid *) o manca un parametro che dimensioni la memoria puntata dal puntatore a void.
Se la dimensione è stata impostata in altra maniera (magari nella costruzione della hashtable) allora va bene e qualsiasi cosa tu passi a quella funzione va bene, basta che sia di dimensione pari a quella impostata (indipendentemente che sia stringa o struttura).
Manbearpig
18-02-2008, 09:58
Allora non sapendo come e' implementata la hastable che stai usando e' un po' dura rispondere, cmq per quanto riguarda l'hash, nel tuo caso sara' la libreria che usi ad arrangiarsi, infatti prende come argomento (item) un puntatore a void. Prova semplicemente a passargli come argomento il tuo array.
Per quanto riguarda le collisioni, ora non so come sia implementa ma di solito la dimensione devi comunque stabilirla. Ci sono implementazioni in cui puoi decidere di espandere la tabella se questa raggiunge un certo fattore di carico ad es se hai 1000 elementi su una tabella grande 500 allora per evitare troppe collisioni la dimensione della tabella viene raddoppiata. Come funzioni di preciso il procedimento non lo so, ma penso che l'espansione sia cmq abbastanza costosa (biogna ricalcolare tutti gli hash?).
fracarro
18-02-2008, 10:00
Come ti ho già detto c'0è qualcosa che non va nella libreria. Perché o quella libreria prende in input solo stringhe (limitate da \0), ed in tal caso non cpaisco perché sia vopid *) o manca un parametro che dimensioni la memoria puntata dal puntatore a void.
Se la dimensione è stata impostata in altra maniera (magari nella costruzione della hashtable) allora va bene e qualsiasi cosa tu passi a quella funzione va bene, basta che sia di dimensione pari a quella impostata (indipendentemente che sia stringa o struttura).
Allego di seguito i due file della libreria con la guida su come utilizzarla. A dire il vero non ho ancora studiato a fondo come funziona la libreria e quindi come "decide" la dimensione della tabella. Tuttavia il suo utilizzo è estremamente semplice perchè come riportato dalla guida tutto quello che bisogna fare è implementare delle semplici funzioni necessarie alla libreria perchè ovviamente prendendo in input un void* la libreria a priori non può sapere come fare il "confronto" tra due elementi (soprattutto se sono strutture).
Spero che sia una buona libreria voi che ne dite?
P.S. Ho dovuto rinominare i file della libreria perchè i .c e .h non me li fa allegare.
fracarro
18-02-2008, 10:00
Ho dimenticato il readme, eccolo qua.
Manbearpig
18-02-2008, 10:16
Beh mi sembra chiaro dalla documentazione come usarla... secondo me puoi passargli semplicemente l'array come argomento. Per il confronto crei una tua funzione che fa il confronto tra due chiavi e la passi come argomento alla funzione di init. La dimensione a quanto pare la gestisce automaticamente, quanto sia positivo non lo so...
La dimensione a quanto pare la gestisce automaticamente, quanto sia positivo non lo so...
Più che altro...come fa ? Cioè l'hash se lo deve calcolare in qualche modo e per fare un hash serio si lavora su tutta l'estensione dei dati...estensione alla libreria sconosciuta :confused:
fracarro: non mi torna anche un'altra cosa. Come mai hai parlato di un vettore di 4 interi ? In teoria dovresti avere almeno 1000 bit, quindi come minimo 32 interi :mbe:
Manbearpig
18-02-2008, 10:44
Più che altro...come fa ? Cioè l'hash se lo deve calcolare in qualche modo e per fare un hash serio si lavora su tutta l'estensione dei dati...estensione alla libreria sconosciuta :confused:
Beh penso che per la dimensione inizi con una dimensione predefinita (probabilmente piccola) e poi per ogni espansione ricalcoli tutti gli hash.
per quanto riguarda l'hash nella documentazione dice:
Your actual data takes some form, which is entirely up to you.
It must be possible to refer to a complete data item by a
single pointer. Your data also will have some sort of key, or
even multiple keys. It can have whatever auxiliary data you
like. This implies you must define a structure somewhere for
your own benefit:
typedef struct hashitem {
sometype yourkey;
otherstuff yourdata;
} item, *itemptr;
The field names, structure name, typedef'd names, etc are
entirely up to you.
L'unica limitazione (ovviamente) e' che non puoi avere puntatori all'interno della struct.
Nel suo caso puo' semplicemente passare l'array credo...
fracarro: non mi torna anche un'altra cosa. Come mai hai parlato di un vettore di 4 interi ? In teoria dovresti avere almeno 1000 bit, quindi come minimo 32 interi :mbe:
mi sa che sta facend una prova con un insieme piu piccolo...
Sì, ma come fa a calcolare l'hash sui dati se non conosce la dimensione dei dati ?
Manbearpig
18-02-2008, 11:05
Sì, ma come fa a calcolare l'hash sui dati se non conosce la dimensione dei dati ?
Si ho fatto confusione, in effetti non puo' passare l'array.... l'unica soluzione e' creare una struct con dentro n interi che pero' fa un po' schifo come cosa.. Altrimenti modificare la libreria.
Manbearpig
18-02-2008, 11:14
No spe, a quanto pare puoi customizzare tutte le funzioni che vengono passate ad hashinit, quindi devi crearti la tua funzione hash. Di conseguenza puoi usare anche l'array.
fracarro
18-02-2008, 11:15
Sì, ma come fa a calcolare l'hash sui dati se non conosce la dimensione dei dati ?
Da profano chiedo: non può calcolare l'hash a partire da una stringa, qualunque sia la sua dimensione? Tenete presente che mentre lui gestisce strutture con vari dati nel mio caso la struttura è sostituita da una semplice stringa (la famosa stringa di bit) che io gli do in input.
Nel file di utilizzo riguardo da dimensione della tabella c'è scritto questo: "You may be wondering "for what is hashlib useful". The answer
is that it is a storage facility. You can hand it things, and
it will tuck them away, and make it easy for you to find them
later.
A major point is that the time it takes to store, find, delete,
or retrieve an item is almost constant no matter how big the
table gets. Also, you don't have to worry about the table size,
because it will automatically adapt itself. It may hold 5 items
or millions. The limit is your memory."
Ad ogni modo, se vi può interessare, la libreria completa (con tutti i file ed esempi già pronti) la trovate qui: http://cbfalconer.home.att.net/download/hashlib.zip
Imho la soluzione più semplice è farsi l'hash a mano. Tanto il calcolo dell'hash su un insieme ha come minimo complessità O(n) (con n pari al numero degli interi, se si vuole fare un hash valido), sia che lo faccia lui, sia che lo faccia una libreria.
Il primo hash che mi viene in mente per la soluzione con i bit è quello di fare una somma degli interi di un insieme in modulo 2^24, dovrebbe consentire di "spalmare" bene gli elementi.
Sono 64 MB di tabella hash (vettore di puntatori a lista) allocata con calloc (per azzerare tutto).
Dopo che si è indicizzata la tabella si tratta di fare un semplice confronto fra gli elementi nella lista e l'insieme che abbiamo indicizzato, nel worst case O(n), anche se in media i confronti saranno molti meno, visto che si può uscire appena si trova un intero diverso.
Manbearpig
18-02-2008, 11:21
Nella documentazione che hai postato prima c'e' scritto tutto... RTFM :D
devi crearti tutte le funzioni che vengono passate a hshinit.
mytable = hshinit(myhash, myrehash,
mycmp,
mydupe, myundupe,
0);
which tells hashlib all about the customizing functions you have
created. Note that all those functions can be static, unless
you have other uses for them outside your source file. You can
use those functions yourself as you please.
C'e' anche scritto come vanno fatte..
fracarro
18-02-2008, 11:26
Nella documentazione che hai postato prima c'e' scritto tutto... RTFM :D
devi crearti tutte le funzioni che vengono passate a hshinit.
mytable = hshinit(myhash, myrehash,
mycmp,
mydupe, myundupe,
0);
which tells hashlib all about the customizing functions you have
created. Note that all those functions can be static, unless
you have other uses for them outside your source file. You can
use those functions yourself as you please.
C'e' anche scritto come vanno fatte..
Si si infatti mi è piaciuta questa libreria proprio perchè è estremamente semplice da usare. Ho creato le funzioni e già l'ho implementata verificando anche che funziona e trova le chiavi che ho inserito.
Attualmente però la generazione della chiavi, che passo alla funzione hash, avviene nella modalità "lenta" concatenado i numeri (precedentemente ordinati) separati da virgola, quindi abbastanza inefficiente. Per questo volevo passare alla rappresentazione a bit. A questo punto devo solo provare se usando gli unsigned char posso passare direttamente l'array alla funzione hash.
Also, you don't have to worry about the table size,
because it will automatically adapt itself. It may hold 5 items
or millions. The limit is your memory.[/I]"
Ad ogni modo io non parlavo di dimensioni della tabella, ma cercavo di capire come facesse a calcolare l'hash dai dati visto che non viene impostata in nessun modo la dimensione dei dati su cui calcolare l'hash.
Senza considera che se la tabella è dinamica, la libreria si dovrebbe anche ricalcolare gli hash.
Ripeto, ti consiglio di calcolare l'hash a mano, visto che stai cercando le prestazioni.
Considera che con una tabella di 64 MB sono 2^24 liste, pensa che con 500 milioni di insiemi inseriti raggiungi una media di circa 30 elementi a lista, nella maggior parte dei casi i confronti con gli elementi collisi (quelli nella lista) sarà dell'ordine di uno per elemento (perché il primo confronto non fallisca i due insiemi devono avere il primo intero uguale E lo stesso hash).
Attualmente però la generazione della chiavi, che passo alla funzione hash, avviene nella modalità "lenta" concatenado i numeri (precedentemente ordinati) separati da virgola, quindi abbastanza inefficiente.
Non è inefficiente...è sbagliata ;)
Per definizione l'hash deve mappare un insieme di cardinalità maggiore in un insieme di cardinalità minore. Se questo non avviene non hai bisogno di hash.
Concatenando gli elementi crei una corrispondenza 1 a 1 fra hash e insieme di partenza, certo elimini la possibilità di collisione, ma crei di fatto una struttura che non è una hash table e che è estremamente meno efficiente di una hash table.
fracarro
18-02-2008, 11:47
Non è inefficiente...è sbagliata ;)
Per definizione l'hash deve mappare un insieme di cardinalità maggiore in un insieme di cardinalità minore. Se questo non avviene non hai bisogno di hash.
Concatenando gli elementi crei una corrispondenza 1 a 1 fra hash e insieme di partenza, certo elimini la possibilità di collisione, ma crei di fatto una struttura che non è una hash table e che è estremamente meno efficiente di una hash table.
Un attimo. Allora non ho capito nulla riguardo le tabelle hash.:cry:
L'idea che mi ero fatto io era questa. Dato un insieme molto grande di elementi io assegno in modo univoco ad ogni elemento una "chiave" (una stringa o qualsiasi altra cosa) che passo ad una funzione hash la quale memorizza questo elemento dell'insieme nella tabella hash. Ora quello che è fondamentale è assegnare una chiave distinti per ogni elemento dell'insieme di partenza. Tuttavia poichè la dimensione della tabella hash è inferiore al numero di elementi del mio insieme di partenza può succedere che la funzione hash indichi la stessa posizione nella tabella per due chiavi "distinte" date in input. Quindi per due elementi distinti mi ritroverò la stessa posizione nella tabella hash e questo è il fenomeno delle collisioni.
Se è così allora è fondamentale dare chiavi distinte agli elementi dell'insieme se a due elementi do la stessa chiave sicuramente la funzione hash li destinerà nella stessa posizione della tabella hash.
La collisione è un fenomeno accettato e necessario per ottenere una tabella hash efficiente. Il vantaggio della tabella hash è proprio quello di poter accedere velocemente ad elementi con un determinato hash in maniera diretta (O(1)).
Ma se hai chiavi distinte tanto vale effettuare un'indicizzazione tramite qualche altra struttura dati.
Le strutture sono le più innumerevoli...ad esempio i B+ tree.
fracarro
18-02-2008, 12:36
Perdonami se insisto ma io credo che si possa benissimo usare la tabella hash anche se le chiavi sono distinte. Ti riporto la descrizione riguardo le tabelle hash che ho recuperato dal libro introduction to algorithm:
...
When the set K of keys stored in a dictionary is much smaller than the universe U of all possible keys, a hash table requires much less storage than a direct-address table. Specifically, the storage requirements can be reduced to Θ(|K|) while we maintain the benefit that searching for an element in the hash table still requires only O(1) time. The only catch is that this bound is for the average time, whereas for direct addressing it holds for the worst-case time.
With direct addressing, an element with key k is stored in slot k. With hashing, this element is stored in slot h(k); that is, we use a hash function h to compute the slot from the key k. Here h maps the universe U of keys into the slots of a hash table T[0 ‥ m - 1]:
h : U → {0, 1, ..., m - 1} .
We say that an element with key k hashes to slot h(k); we also say that h(k) is the hash value of key k. Figure 11.2 illustrates the basic idea. The point of the hash function is to reduce the range of array indices that need to be handled. Instead of |U| values, we need to handle only m values. Storage requirements are correspondingly reduced.
Figure 11.2: Using a hash function h to map keys to hash-table slots. keys k2 and k5 map to the same slot, so they collide.
There is one hitch: two keys may hash to the same slot. We call this situation a collision. Fortunately, there are effective techniques for resolving the conflict created by collisions.
...
In pratica qui fanno vedere come risolvere il problema di spazio derivato dall'indirizzamento diretto usando una tabella hash ma non viene specificato che le chiavi possono essere duplicate anzi parlano di insiemi di chiavi e se non ricordo male per definizione in un insieme non si può ripetere due volte lo stesso elemento.
Manbearpig
18-02-2008, 12:42
peccato che |U| nel tuo caso sia 2^1000 :D
fracarro
18-02-2008, 12:52
peccato che |U| nel tuo caso sia 2^1000 :D
EDIT: hai ragione.
Tuttavia il trucco sta proprio nel fatto che rispetto a questo numero astronomico, l'insieme di chiavi K che in realtà dovrò andare a memorizzare è solo quello degli insiemi generati dal mio algoritmo che potrebbe essere al più qualche milione.
Come si nota dalla definizione data dal libro la funzione hash ovviamente deve prendere in input una qualsiasi chiave (quindi un qualsiasi elemento di U) e tradurmela nello slot corrispondente nella tabella hash tutto qui. Ovviamente se io associassi la stessa chiave a diversi insiemi andrei contro i miei interessi perchè genererei sicuramente le collisioni che invece voglio minimizzare.
Come si nota dalla definizione data dal libro la funzione hash ovviamente deve prendere in input una qualsiasi chiave (quindi un qualsiasi elemento di U) e tradurmela nello slot corrispondente nella tabella hash tutto qui.
Ok...allora se la tabella hash si occupa di indirizzarti verso un dato slot e la cardinalità dell'insieme degli hash è pari a quella dell'insieme dei possibili insiemi...quanti slot possibili hai nel tuo caso ?
fracarro
18-02-2008, 13:02
Ok...allora se la tabella hash si occupa di indirizzarti verso un dato slot e la cardinalità dell'insieme degli hash è pari a quella dell'insieme dei possibili insiemi...quanti slot possibili hai nel tuo caso ?
Ma se la dimensione della tabella hash è uguale all'insieme di partenza faccio l'indirizzamento diretto.
La dimensione della tabella hash e la sua gestione dovrebbero essere gestite automaticamente dalla libreria che vi ho postato prima e spero che lo faccia in modo efficiente. Da quello che ho capito ingrandisce la tabella ogni volta che ve ne è la necessità raddoppiandone la dimensione. Non può di certo allocare una tabella delle dimensioni del mio insieme di chiavi (non U ma K) perchè neanche io so quante chiavi genererò. Quindi dovrà aggiungerle mano mano (ovviamente le chiavi verranno anche rimosse quando non mi servono più).
Riprendendo quello scritto sopra:
With direct addressing, an element with key k is stored in slot k. With hashing, this element is stored in slot h(k); that is, we use a hash function h to compute the slot from the key k. Here h maps the universe U of keys into the slots of a hash table T[0 ‥ m - 1]:
Se la cardinalità del codominio di h(k) ha la stessa cardinalità di k allora il numero di slot prima e dopo l'implementazione dell'hashing è lo stesso ;) E per quale motivo abbiamo inserito l'hashing ?
Ma se la dimensione della tabella hash è uguale all'insieme di partenza faccio l'indirizzamento diretto.
Appunto. Di fatto stai facendo un indirizzamento diretto.
fracarro
18-02-2008, 13:46
...
Se la cardinalità del codominio di h(k) ha la stessa cardinalità di k allora il numero di slot prima e dopo l'implementazione dell'hashing è lo stesso ;)
Giustissimo Ma la mia domanda è: perchè il codomio dovrebbe essere uguale al dominio? Perchè la libreria dovrebbe allocare una tabella hash di dimensioni pari a K?
In pratica quando il "fattore di carica" ( http://it.wikipedia.org/wiki/Hash_table ) della tabella hash supera una soglia stabilita, la tabella viene raddoppiata in dimensione per ridurre quanto più possibile le collisioni ( ridurre non eliminare). Questo dovrebbe fare la libreria. Se poi la libreria alloca uno slot per ogni chiave inserita, allora è un "genio" chi ha implementato la hashtable in questo modo.
EDIT. Nel file .c della libreria nei commenti delle varie funzioni ho trovato questo:
/* Space available before reaching threshold */
/* Ensure this can return a negative value */
#define TSPACE(m) ((long)TTHRESH(m->currentsz) \
- (long)m->hstatus.hentries)
/* table of k where 2**n - k is prime, for n=8 up. 0 ends */
/* These numbers are chosen so that memory allocation will */
/* usually allow space for system overhead in a 2**n block */
/*http://www.utm.edu/research/primes/lists/2small/0bit.html */
e
/* Increase the table size by roughly a factor of 2 */
/* reinsert all entries from the old table in the new. */
/* revise the currentsz value to match */
/* free the storage for the old table. */
static int reorganize(hshtblptr master)
...
Quindi dovrebbe raddoppiare la dimensione della tabella (copiando i dati dalla vecchia alla nuova e questo non tanto lo gradisco) ogni volta che viene raggiunta una soglia.
Ma allora la stringa che stai costruendo è una chiave o l'hash ? Mi sa che ho fatto un po' di confusione. Il discorso mi torna se la stringa che stai costruendo è la chiave, ma non mi torna se è l'hash.
Supponendo che sia la chiave, allora è normale che sia univoca, ma anche il fatto che sia univoca non ti assicura che non ci siano collisioni (anzi, ci sono di sicuro, altrimenti appunto la tabella hash dovrebbe essere troppo grande), in ogni caso non ha senso andarsi a costruire questa stringa perché puoi utilizzare direttamente i dati contenuti nel vettore per costruire l'hash, in quanto sono già una chiave univoca.
Manbearpig
18-02-2008, 14:14
Quindi dovrebbe raddoppiare la dimensione della tabella (copiando i dati dalla vecchia alla nuova e questo non tanto lo gradisco) ogni volta che viene raggiunta una soglia.
E deve pure ricalcolarsi tutti gli hash per ogni chiave...
Come gia' detto secondo me ti conviene fartela a mano stimando grosso modo quanti sottoinsiemi dovrai gestire e dimensionando la hashtable di conseguenza.
Se non puoi fare stime allora devi ridimensionare.
fracarro
18-02-2008, 14:55
Ma allora la stringa che stai costruendo è una chiave o l'hash ? Mi sa che ho fatto un po' di confusione. Il discorso mi torna se la stringa che stai costruendo è la chiave, ma non mi torna se è l'hash.
Supponendo che sia la chiave, allora è normale che sia univoca, ma anche il fatto che sia univoca non ti assicura che non ci siano collisioni (anzi, ci sono di sicuro, altrimenti appunto la tabella hash dovrebbe essere troppo grande), in ogni caso non ha senso andarsi a costruire questa stringa perché puoi utilizzare direttamente i dati contenuti nel vettore per costruire l'hash, in quanto sono già una chiave univoca.
Ah ecco perchè non ci trovavamo sul discorso.
Ovviamente la stringa che sto costruendo è la chiave che darò in pasto alla funzione hash la quale a sua volta genererà lo slot dove inserire l'elemento nella tabella hash.
Ritornando quindi alla domanda che avevo fatto nella pagina precedente, dopo aver costruito la stringa di bit lavorando sulle 4 caselle di unsigned char posso dare in pasto alla funzione hash direttamente l'array dato che ora questo array rappresenta una stringa?
E deve pure ricalcolarsi tutti gli hash per ogni chiave...
Come gia' detto secondo me ti conviene fartela a mano stimando grosso modo quanti sottoinsiemi dovrai gestire e dimensionando la hashtable di conseguenza.
Se non puoi fare stime allora devi ridimensionare.
Pioichè non posso fare stime dovrei ingrandire e ridurre dinamicamente la dimensione della tabella man mano che vengono inseriti nuovi elementi. Quindi credo di utilizzare la libreria che spero utilizzi dei criteri "testati" per stabilire le soglie oltre le quali aggiornare la tabella.
Ritornando quindi alla domanda che avevo fatto nella pagina precedente, dopo aver costruito la stringa di bit lavorando sulle 4 caselle di unsigned char posso dare in pasto alla funzione hash direttamente l'array dato che ora questo array rappresenta una stringa?
Mi fai vedere come vuole la chiave la libreria ?
Se vuole una stringa allora non puoi utilizzare il vettore come chiave (se un byte è vuoto lo interpreta come fine stringa). Se non vuole una stringa, ma un void * e la dimensione della chiave allora sì.
fracarro
18-02-2008, 15:12
Mi fai vedere come vuole la chiave la libreria ?
Se vuole una stringa allora non puoi utilizzare il vettore come chiave (se un byte è vuoto lo interpreta come fine stringa). Se non vuole una stringa, ma un void * e la dimensione della chiave allora sì.
Per quanto riguarda la funzione di inserimento è questa:
/* insert an entry. NULL == failure, else item */
void * hshinsert(hshtblptr master, void *item)
{
if ((TSPACE(master) <= 0) && !reorganize(master)) {
master->hstatus.herror |= hshTBLFULL;
return NULL;
}
return putintbl(master, item, 0);
} /* hshinsert */
Riguardo l'inserimento in generale nelle istruzioni c'è scritto questo:
Copying
=======
When you pass an item to hashlib you don't want to worry about
who owns the space it takes. Therefore the principle is
"hashlib owns all the items it stores". Thus hashlib makes a
copy of any data item it inserts into the table. Once more,
only you know how to do this, and you have to tell hashlib.
typedef void *(*hshdupfn)(void *item);
in hashlib.h specifies what this function must look like. For
the simple structure above, all it would have to do is malloc
space for a copy, and copy the fields. It must copy at least
the key field, the rest is up to you. Remember it is dealing
with pointer to data, and the first thing you have to do is
make the item pointer into a pointer to your structure.
Lets make the simple data structure above more concrete:
typedef struct hashitem {
int yourkey;
int yourdata;
} item, *itemptr;
Then the hshdupefn (notice how the function is defined by
editing the typedef for hshdupfn) could be:
void *mydupe(void *item)
{
itemptr myitem = item;
itemptr newitem;
if (newitem = malloc(sizeof *newitem) {
newitem.yourkey = myitem.yourkey;
newitem.yourdata = myitem.yourdata;
/* or "*newitem = *myitem" in this case */
}
return newitem;
}
Notice again that only your code knows what is in the items to
be stored, and thus how to copy them. Your item can be as
complicated as you wish. So lets make it store strings:
typedef struct hashitem {
char *yourkey;
int yourdata;
} item, *itemptr;
and see how it affects the hshdupefn. Yourkey is now just a
pointer to a string somewhere, which may want to be modified
or used in some manner. So we have do what is called a deep
copy.
void *mydupe(void *item)
{
itemptr myitem = item;
itemptr newitem;
if (newitem = malloc(sizeof *newitem) {
if (newitem->yourkey =
malloc(1+strlen(myitem->yourkey) {
strcpy(newitem->yourkey, myitem->yourkey;
newitem.yourdata = myitem.yourdata;
}
else { /* we ran out of memory, release and fail */
free(newitem)
newitem = NULL
}
}
return newitem;
}
Notice how it returns NULL if malloc fails to secure the
necessary memory anywhere. This allows hashlib to do the
right things under nasty cases, such as exhausting memory.
The need for a deep copy is generally signalled by having
pointers in your data type description. All those pointers have
to be resolved to data that can belong to the hash table.
Manbearpig
18-02-2008, 15:13
Da quel che avevo capito io la libreria vuole un unsigned long, quindi devi costruire la funzione hash che ritorna quel tipo di valore. Una semplice soluzione come gia detto qualche pagina fa e' prendere la somma degli elementi, chiaramente avrai insiemi diversi con le stesse chiavi ma secondo me non e' un gran problema.
fracarro
18-02-2008, 15:16
Da quel che avevo capito io la libreria vuole un unsigned long, quindi devi costruire la funzione hash che ritorna quel tipo di valore. Una semplice soluzione come gia detto qualche pagina fa e' prendere la somma degli elementi, chiaramente avrai insiemi diversi con le stesse chiavi ma secondo me non e' un gran problema.
Dalla definizione che ho postato sopra riguardo l'hashitem sembra che la chiave che lui utilizza per generare lo slot di destinazione è un semplice char*.
Io ce l'ho a morte con chi scrive le librerie e poi usa delle orride abbreviazioni nei nomi dei tipi e delle funzioni, rendendo tra l'altro oscuro il funzionamento delle stesse ;)
fracarro: continuo a pensare che ti convenga fare come ti avevo detto qualche pagina fa. Ci vuole più tempo a capire come funziona quella libreria (data l'assurdità anche dei nomi) che a scrivere l'hash table con 2^24 entry che ti avevo suggerito qualche post fa ;)
Manbearpig
18-02-2008, 15:18
quella e' la funzione predefinita, devi crearne una tua...
This is fundamental to the efficient operation of a hashtable,
although hashlib can put up with pretty rotten hashing and still
grind out answers (but it may take a long time). What we need
to do is calculate a single unsigned long value from the key.
What these functions are is basically black magic, therefore
hashlib contains a couple of utility functions usable for
hashing strings. There are also examples of hashing integers
in the hashtest.c program along with some references to the
subject of creating hash functions. For now we will just use
the utility string hashing functions provided in hashlib, i.e.
hshstrhash(char *) and hshstrehash(char *).
Because of the efficient way hashlib handles overflows (it
basically just corrects them) it is necessary to have two
hash functions. For the above item type with strings, they
would be:
typedef unsigned long (*hshfn)(void *item);
for reference, which we edit again and get:
unsigned long myhash(void *item)
{
itemptr myitem = item; /* getting used to this? */
return hshstrhash(myitem->yourkey);
}
and we need two such functions, so:
unsigned long myrehash(void *item)
{
itemptr myitem = item; /* getting used to this? */
return hshstrehash(myitem->yourkey);
}
which basically differ only in their names and in the
convenience hash function they call.
Now we have finally customized the system to our own data
format. We will tell hashlib about these functions when
we create a hashtable with hshinit.
quella e' la funzione predefinita, devi crearne una tua...
Alla fine fa prima a fare tutto da solo :D
Manbearpig
18-02-2008, 15:23
Io ce l'ho a morte con chi scrive le librerie e poi usa delle orride abbreviazioni nei nomi dei tipi e delle funzioni, rendendo tra l'altro oscuro il funzionamento delle stesse ;)
Haha beh questi nomi sono bellissimi: hshstrhash(char *) and hshstrehash(char *). sembra di leggere arabo :D
Manbearpig
18-02-2008, 15:26
Alla fine fa prima a fare tutto da solo :D
Ma e' da ieri che lo dico eh :D
fracarro
18-02-2008, 15:32
quella e' la funzione predefinita, devi crearne una tua...
...
Allora. Le funzioni che ho dovuto costruire io per utilizzare la libreria (seguendo la guida che è veramente fatta bene) sono solo 6 tra cui queste due:
unsigned long myhash(void* item){
char *s1 = item;
return hshstrhash(s1);
}
unsigned long myrehash(void* item){
char *s1 = item;
return hshstrehash(s1);
}
Come puoi vedere nel mio caso solo banali perchè un item per me è una stringa. Se invece fosse stato un oggetto allora sarei dovuto andare a recuperare la chiave all'interno dell'oggetto e passarla alle funzioni hshstrhash e hshstrehash.
Queste funzioni effettuano il famoso hash ossia l'individuazione dello slot (l'unsigned long a cui tu fai riferimento) della tabella hash dove verrà inserito l'item.
Per curiosità vi riporto anche qual'è la funzione hash utilizzata da questa libreria (io ovviamente non l'ho capita):
/* NOTE: hash is called once per operation, while rehash is
called _no more_ than once per operation. Thus it
is preferable that hash be the more efficient.
*/
/* Hash a string quantity */
unsigned long hshstrhash(const char * string)
{
unsigned long h;
h = 0;
while (*string) {
h = h * 31UL + (unsigned char) *string++;
}
return h;
} /* hshstrhash */
/* 1------------------1 */
/* ReHash a string quantity */
unsigned long hshstrehash(const char * string)
{
unsigned long h;
h = 0;
while (*string) {
h = h * 37UL + (unsigned char) *string++;
}
return h;
} /* hshstrehash */
Io ce l'ho a morte con chi scrive le librerie e poi usa delle orride abbreviazioni nei nomi dei tipi e delle funzioni, rendendo tra l'altro oscuro il funzionamento delle stesse
fracarro: continuo a pensare che ti convenga fare come ti avevo detto qualche pagina fa. Ci vuole più tempo a capire come funziona quella libreria (data l'assurdità anche dei nomi) che a scrivere l'hash table con 2^24 entry che ti avevo suggerito qualche post fa
Sulla questione dei nomi delle librerie sono d'accordo con te, sono assurdi e non si capisce niente. Per il funzionamento tuttavia basta usare quelle indicate nella guida, per creare la tabella e poi fare le tre operazioni necessarie, inserimento cancellazione e ricerca.
Cosa ne pensi riguardo l'idea di passare l'array contenente la stringa di bit alla funzione hshstrhash? Dovrebbe funzionare giusto? In fondo anche se una cella dell'array contiene 0 non mi dovrebbe creare problemi dato che il carattere di fine stringa è '\0'.
fracarro
18-02-2008, 15:34
Ma e' da ieri che lo dico eh :D
lo so ma avendo già scritto le funzioni e implementato il codice usando la libreria mi scoccia ricominciare da capo.
In compenso dopo questa discussione con voi due ho capito bene (spero) il funzionamento delle tabelle hash e soprattutto che piuttosto di utilizzare il codice di qualcun'altro faccio prima a scrivermelo da me.
In fondo anche se una cella dell'array contiene 0 non mi dovrebbe creare problemi dato che il carattere di fine stringa è '\0'.
Scrivi questo comando:
printf("%d", '\0');
soprattutto che piuttosto di utilizzare il codice di qualcun'altro faccio prima a scrivermelo da me.
Non sempre, solo se la libreria è stata scritta con i piedi.
fracarro
18-02-2008, 15:48
Scrivi questo comando:
printf("%d", '\0');
Ops. Provato e mi stampa zero, che vuol dire?
Ad ogni modo ho scritto questo codice per verificare se inserire lo 0 nell'array mi crea problemi.
int main(){
unsigned char prova[10];
prova[0]= '1';
prova[1]= '2';
prova[2]= '3';
prova[3]= '4';
prova[4]= '5';
prova[5]= '0';
prova[6]= '7';
prova[7]= '\0';
printf("\n%s\n",prova);
return 1;
}
Risultato: 1234507 :yeah:
Spero che faccia lo stesso quando i valori nelle celle vengono modificati tramite le operazioni sui bit. Quasi quasi provo anche quello.
Vuol dire che il carattere di fine stringa è l'intero 0 ;)
La tua prova è falsata. Il carattere '0' corrisponde ad un intero diverso da 0.
Scrivi così:
prova[0]= '1';
prova[1]= '2';
prova[2]= '3';
prova[3]= '4';
prova[4]= 0;
prova[5]= '0';
prova[6]= '7';
prova[7]= '\0';
Manbearpig
18-02-2008, 15:59
giusto per curiosita' cosa centra sta roba dei char? :D
Ma soprattutto il carattere di fine stringa a che ti serve in questo caso?
fracarro
18-02-2008, 16:01
Vuol dire che il carattere di fine stringa è l'intero 0 ;)
La tua prova è falsata. Il carattere '0' corrisponde ad un intero diverso da 0.
Scrivi così:
prova[0]= '1';
prova[1]= '2';
prova[2]= '3';
prova[3]= '4';
prova[4]= 0;
prova[5]= '0';
prova[6]= '7';
prova[7]= '\0';
Bingo. Non funziona è come dici tu. Come faccio a convertire questa benedetta stringa di bit in una stringa allora?
fracarro
18-02-2008, 16:04
giusto per curiosita' cosa centra sta roba dei char? :D
Ma soprattutto il carattere di fine stringa a che ti serve in questo caso?
All'inizio avevo usato un array di unsigned int su cui effettuavo le operazioni sui bit per poter rappresentare l'insieme. Il problema che era sorto derivava dal fatto che una volta terminata la rappresentazione dell'insieme mi ritrovavo con un array di unsigned int mentre a me serviva una stringa da passare come chiave alla funzione hash. Pensavo di poter risolvere il problema sostituendo gli unsigned int con gli unsigned char in modo che l'array prodotto dopo le operazioni sui bit era già una stringa che potevo direttamente passare alla funzione di hash. Come cionci mi ha fatto notare però se in qualche casella rimane il valore zero la stringa viene troncata in quel punto e solo una parte della chiave associata all'insieme sarebbe considerata.
giusto per curiosita' cosa centra sta roba dei char? :D
Ma soprattutto il carattere di fine stringa a che ti serve in questo caso?
Perché vuole usare la funzione di hashing standard presente nella libreria.
Gli serve perché appunto queste funzione ha bisogno del carattere di fine stringa per terminare la lettura.
Manbearpig
18-02-2008, 16:11
All'inizio avevo usato un array di unsigned int su cui effettuavo le operazioni sui bit per poter rappresentare l'insieme. Il problema che era sorto derivava dal fatto che una volta terminata la rappresentazione dell'insieme mi ritrovavo con un array di unsigned int mentre a me serviva una stringa da passare come chiave alla funzione hash. Pensavo di poter risolvere il problema sostituendo gli unsigned int con gli unsigned char in modo che l'array prodotto dopo le operazioni sui bit era già una stringa che potevo direttamente passare alla funzione di hash. Come cionci mi ha fatto notare però se in qualche casella rimane il valore zero la stringa viene troncata in quel punto e solo una parte della chiave associata all'insieme sarebbe considerata.
Si ma scusa ti basta implementare la funzione hash in modo che prenda l'array di int........ Cioe' non so se non ti e' chiara sta cosa ma e' previsto dalla libreria che sia tu a implementare la funzione hash, quella che c'e' e' solo un esempio sui char.......
fracarro
18-02-2008, 16:32
Si ma scusa ti basta implementare la funzione hash in modo che prenda l'array di int........ Cioe' non so se non ti e' chiara sta cosa ma e' previsto dalla libreria che sia tu a implementare la funzione hash, quella che c'e' e' solo un esempio sui char.......
Qualche idea/esempio :help: di come implementare una buona funzione hash che prenda in input un array di int e restituisca un long? Ovviamente una funzione del genere deve tener presente della divisione in celle dell'array perchè |3|15|8|4| e |31|5|8|4| sono due insiemei diversi e quindi devono avere associate due chiavi diverse da passare alla funzione di hash.
Manbearpig
18-02-2008, 16:52
io farei la somma degli degli unsigned int del tuo array.. Altre alternative semplici non mi vengono in mente, magari Cionci ha qualche idea :P
fracarro
18-02-2008, 16:58
io farei la somma degli degli unsigned int del tuo array.. Altre alternative semplici non mi vengono in mente, magari Cionci ha qualche idea :P
Purtroppo questa idea non mi garantisce l'univocità delle chiavi associate agli insiemi.
Comunque viste le complicazioni che sono sorte mi arrendo. Lascio il codice attuale con la versione lenta della generazione delle chiavi. Semplicemente ogni insieme viene identificato come la stringa ordinata degli elementi che lo costituiscono separati da una virgola. Sarà meno efficiente (a causa dell'ordinamento) ma per lo meno funziona.
Grazie a tutti e due per i consigli comunque.
Manbearpig
18-02-2008, 17:01
beh non e' un grosso problema, avrai qualche collisione in piu' ma le collisioni non sono la morte eh :P
Hai rotto le palle con le prestazioni per due giorni e adesso ti tieni la versione lenta? :D
fracarro
18-02-2008, 17:07
beh non e' un grosso problema, avrai qualche collisione in piu' ma le collisioni non sono la morte eh :P
Hai rotto le palle con le prestazioni per due giorni e adesso ti tieni la versione lenta? :D
:(
Speravo si potesse risolvere il problema efficientemente e velocemente ma a quanto sembra non è così.
Siccome questa della tabella hash è solo una piccolissima parte di un codice che devo terminare quanto prima non posso bloccarmi su questo senza terminare il codice. Per ora ho una versione funzionante "ottimizzabile", in futuro potrò sempre cambiarla. ;)
Il problema delle collisioni è molto semplice. Vorrei evitarle per non escludere delle "mosse" che erroneamnete vengono identificate come tabu. Associare la stessa chiave a più insiemi aumenterebbe le mosse escluse e questo non va bene perchè alla fine l'algoritmo potrebbe essere più performante ma se la soluzione che mi ritorna fa schifo non mi serve ad un granchè, quindi devo comunque individuare un giusto tradeoff.
Manbearpig
18-02-2008, 17:25
nessuna mossa viene identificata erroneamente come tabu!! Insomma che ci siano collisioni o meno il risultato e' e deve essere sempre lo stesso. L'unica differeza e' che in caso di collisione devi scorrerti la lista degli insiemi associata allo stesso indice per vedere se effettivamente e' tabu, cosa che con i bit fai molto velocemente considerando che puoi fare il confronto quasi istantaneamente (NOT A AND B). Avendo le stringhe, devi innanzitutto ordinarle tutte e poi fare i confronti che nel peggiore dei casi sono 1000*k dove k e' il numero di insiemi con la stesso indice. Inoltre usi 8 volte la memoria necessaria.
Il problema delle collisioni viene gestito internamente dalla hashtable...te non devi fare niente. Le collisioni sono a livello di hash e non di chiave.
fracarro
18-02-2008, 19:43
nessuna mossa viene identificata erroneamente come tabu!! Insomma che ci siano collisioni o meno il risultato e' e deve essere sempre lo stesso. L'unica differeza e' che in caso di collisione devi scorrerti la lista degli insiemi associata allo stesso indice per vedere se effettivamente e' tabu, cosa che con i bit fai molto velocemente considerando che puoi fare il confronto quasi istantaneamente (NOT A AND B). Avendo le stringhe, devi innanzitutto ordinarle tutte e poi fare i confronti che nel peggiore dei casi sono 1000*k dove k e' il numero di insiemi con la stesso indice. Inoltre usi 8 volte la memoria necessaria.
Appunto il problema è proprio quello. In caso di collisione lo scorrimento della lista degli insiemi associati a quello slot può diventare costosa se devo fare un confronto tra stringe (l'attuale versione). Inoltre dovrei fare un'altro ordinamento (oltre a quello usato per generare ogni chiave) e spreco memoria. Per questo ho deciso di utilizzare una tabella hash con la speranza di avere meno collisioni possibili perchè quando a due insiemi viene assegnato lo stesso slot io evito di fare il confronto lo marco tabu e basta.
Sicuramente con i bit le cose erano differenti perchè non c'era ordinamento per la generazione della chiave ne per fare i confronti e soprattutto questi ultimi era velocissimi. Purtroppo non sono riuscito a lavorare con i bit e quindi per ora va così. Quando il codice sarà pronto, analizzerò tramite il profiler il tempo sprecato per le operazioni di ordinamento e gestione della hashtable.
Il problema delle collisioni viene gestito internamente dalla hashtable...te non devi fare niente. Le collisioni sono a livello di hash e non di chiave.
Si ma usando le stesse chiavi per più insiemi aumenterei le collisioni e questo lo vorrei evitare per le ragioni scritte sopra.
Si ma usando le stesse chiavi per più insiemi aumenterei le collisioni e questo lo vorrei evitare per le ragioni scritte sopra.
Ripeto :D Le chiavi non devono collidere, devono essere univoche, sono gli hash che collidono. Se anche generi una chiave con una stringa formata da tutti gli elementi, e questa è univoca per definizione, la collisione a livello di hash ce l'hai comunque ;)
Manbearpig
19-02-2008, 06:39
Ripeto :D Le chiavi non devono collidere, devono essere univoche, sono gli hash che collidono. Se anche generi una chiave con una stringa formata da tutti gli elementi, e questa è univoca per definizione, la collisione a livello di hash ce l'hai comunque ;)
penso si riferisse al fatto che prendendo la somma degli unsigned int come chiave, hai "colisioni" anche sulle chiavi. Ma secondo me non e' un grande problema.
fracarro
19-02-2008, 08:33
penso si riferisse al fatto che prendendo la somma degli unsigned int come chiave, hai "colisioni" anche sulle chiavi. Ma secondo me non e' un grande problema.
Esatto, mi riferivo proprio a quello.
Speravo si potesse passare la stringa di bit direttamente alla funzione ma così non è perchè come detto da cionci una volta modificati i bit se una casella contiene il valore 0 la chiave viene troncata. Purtroppo non ho altre idee a riguardo e quindi per ora vado avanti con la versione lenta.
Speravo si potesse passare la stringa di bit direttamente alla funzione ma così non è perchè come detto da cionci una volta modificati i bit se una casella contiene il valore 0 la chiave viene troncata. Purtroppo non ho altre idee a riguardo e quindi per ora vado avanti con la versione lenta.
E' inutile. Le collisioni sull'hash ce l'avrai sempre e comunque ;)
Questo perché stai usando uno spazio di memoria minore di quello necessario a contenere tutti i tuoi dati.
Lo sai che fa quella libreria ? Prende un unsigned int come hash e fa il modulo fra l'hash e la dimensione del vettore che contiene i puntatori a lista. Quando il fattore d'utilizzo supera un certo valore aumenta di un bit la capacità di indirizzamento e quindi moltiplica per due la dimensione del vettore e rialloca tutti gli elementi delle liste sfruttando l'hash già calcolato, ma usando il modulo con la nuova dimensione.
Quindi non fa ne più ne meno quello che ti avevo suggerito io, solo che con il mio avresti da subito evitato una marea di collisioni ed avresti evitato di ridimensionare il tutto (cosa che ha un costo enorme).
Sei sempre in tempo e ci vuole pochissimo a farlo ;)
10 minuti e si preparano le funzioni per accedere all'hash.
Per invogliarti ti ho scritto parte del codice ;)
Ora sta a te scrivere la funzione che recupera l'elemento dalla tabella.
Nota che non ho compilato, ma dovrebbe essere corretto, al max, a meno di mistyping, dovrebbe esserci uno warning.
efine DATA_BITS 1000
#define DATA_SIZE 32
#define TABLE_SIZE (1 << 24)
typedef struct element_struct
{
int data[DATA_SIZE];
struct element_struct * next;
} element;
typedef struct element_struct * hashtable;
hashtable * create_hashtable()
{
return calloc(TABLE_SIZE, sizeof(hashtable));
}
void destroy_hashtable_and_elements(hashtable * table)
{
int i = 0;
element * list;
element * next;
for(; i < TABLE_SIZE; ++i)
{
list = table[i];
while(list)
{
next = list->next;
free(list);
list = next;
}
}
free(table);
}
void add_data(hashtable * table, int * data)
{
int hash = 0;
int i = 0;
element * list
element * new_element;
new_element = (element *) malloc(sizeof(element));
new_element->next = NULL;
for(; i < DATA_SIZE; ++i)
{
hash += data[i];
new_element->data[i] = data[i];
}
hash %= TABLE_SIZE;
if(!table[hash])
{
table[hash] = new_element;
}
else
{
list = table[hash];
while(list->next)
{
list = list->next;
}
list->next = new_element;
}
}
Ho fatto una piccola modifica ;)
fracarro
19-02-2008, 10:39
Innanzitutto grazie mille cionci sei estremamente disponibile. :ave:
Detto questo alcune domande:
E' inutile. Le collisioni sull'hash ce l'avrai sempre e comunque ;)
Questo perché stai usando uno spazio di memoria minore di quello necessario a contenere tutti i tuoi dati.
Giustissimo e chiaro. Il problema però che io voglio evitare è di associare la stessa chiave a due insiemi diversi. Se ad S1 e S2 do la stessa chiave k è ovvio che h(k) mi restituirà lo stesso slot creando la collisione. Per questo preferirei avere chiavi distinte per ogni insieme considerato. In questo modo le collisioni si verificheranno solo quando h(k1)=h(k2), ossia quando la funzione hash pur prendendo in input due chiavi distinti genera lo stesso slot di output.
Nella funzione che mi hai scritto generi la chiave effettuando la somma dei numeri contenuti nell'array:
hash += data[i];
Questo implica che 1234,55, 37, 64,433, ecc.ecc. verranno identificati con la stessa chiave 10 e quindi inseriti nello stesso slot dalla funzione hash. Queste collisioni andrebbero evitate usando chiavi distinte e limitandole quindi solo ai casi in cui la funzione hash assegna lo stesso slot a chiavi differenti.
Lo sai che fa quella libreria ? Prende un unsigned int come hash e fa il modulo fra l'hash e la dimensione del vettore che contiene i puntatori a lista.
Onestamente non ho ancora chiaro come effettua l'hash la libreria tuttavia osservando la seguente funzione di hash:
/* Hash a string quantity */
unsigned long hshstrhash(const char * string)
{
unsigned long h;
h = 0;
while (*string) {
h = h * 31UL + (unsigned char) *string++;
}
return h;
} /* hshstrhash */
sembra che prenda in input una stringa e generi il valore hash sfruttando ogni carattere della stringa (cosa che noi perdiamo con la somma dei numeri) e moltiplicandolo per questo 31UL che non so cosa sia.
Quando il fattore d'utilizzo supera un certo valore aumenta di un bit la capacità di indirizzamento e quindi moltiplica per due la dimensione del vettore e rialloca tutti gli elementi delle liste sfruttando l'hash già calcolato, ma usando il modulo con la nuova dimensione.
Quindi non fa ne più ne meno quello che ti avevo suggerito io, solo che con il mio avresti da subito evitato una marea di collisioni ed avresti evitato di ridimensionare il tutto (cosa che ha un costo enorme).
Sei sempre in tempo e ci vuole pochissimo a farlo ;)
10 minuti e si preparano le funzioni per accedere all'hash.
Sul ridimensionamento della tavola sono d'accordo con te.
E' un'operazione costosa e probabilmente nel mio caso inutile. Un'allocazione iniziale mi eviterebbe problemi di allocazione di memoria e copia dei valori che sono costose.
A questo punto penso di fare così. Vedo se esiste un modo per generare un numero univoco da un array di interi considerando anche le posizioni di ogni numero. Se lo trovo uso direttamente le tue funzioni aggiungendo quello che manca.
Per invogliarti ti ho scritto parte del codice ;)
Te ne sono grato.
fracarro...è sempre il solito discorso. Una cosa è una chiave, una cosa è l'hash. Ogni insieme DEVE avere una chiave distinta, ma più insiemi DEVONO AVERE hash uguali, è IMPOSSIBILE fare diversamente perché altrimenti dovresti avere un sistema di memorizzazione con tanti elementi quanti sono i possibili insiemi.
E stessa cosa fa il codice della libreria che hai postato, infatti mappa una stringa in un intero, questo mapping equivale ad applicare una funzione h : K -> Y, con K lo spazio delle chiavi (una per insieme), Y lo spazio degli hash. La cardinalità dello spazio delle chiavi è molto minore (2^32) del numero degli insiemi (2^1000).
Poi quell'hash viene usato sicuramente in modulo per indicizzare le liste all'interno della tabella.
Nel codice che ho postato la chiave è l'insieme stesso e questo implica che è univoca.
Nella funzione che mi hai scritto generi la chiave effettuando la somma dei numeri contenuti nell'array:
hash += data[i];
Questo implica che 1234,55, 37, 64,433, ecc.ecc. verranno identificati con la stessa chiave 10 e quindi inseriti nello stesso slot dalla funzione hash. Queste collisioni andrebbero evitate usando chiavi distinte e limitandole quindi solo ai casi in cui la funzione hash assegna lo stesso slot a chiavi differenti.
No. L'array è una mappa di bit, quindi non è assolutamente così.
L'insieme 1,2,3,4 avrà mappa di bit (se il numero uno viene mappato sul bit 0):
2^(1-1) + 2^(2-1) + 2^(3-1) + 2^(4-1) = 15 (la somma viene quindi 15 perché gli altri byte sono a 0)
5,5 non è un insieme, ma 3-7 sì:
2^(3-1) + 2^(7-1) = 66 (la somma viene quindi 66)
Quindi 3,7 viene mappato sullo slot 66, mentre 1,2,3,4 sullo slot 15.
Con la somma noi non perdiamo niente, abbiamo somme uguali con numeri diversi, ma allo stesso modo con l'hash fatto dalla libreria avrai hash uguali con numeri diversi.
fracarro
19-02-2008, 11:33
No. L'array è una mappa di bit, quindi non è assolutamente così.
L'insieme 1,2,3,4 avrà mappa di bit (se il numero uno viene mappato sul bit 0):
2^(1-1) + 2^(2-1) + 2^(3-1) + 2^(4-1) = 15 (la somma viene quindi 15 perché gli altri byte sono a 0)
5,5 non è un insieme, ma 3-7 sì:
2^(3-1) + 2^(7-1) = 66 (la somma viene quindi 66)
Quindi 3,7 viene mappato sullo slot 66, mentre 1,2,3,4 sullo slot 15.
Quando io parlavo dell'array con 1,2,3,4 intendo dire che nella casella 0 c'è il numero 1, nella caseslla 1 il numero 2 e cosi via (l'attuale rappresentazione). Invece da quello che scrivi tu, stai facendo riferimento alla rappresentazione in bit e quindi qualcosa del tipo 11110....0000 dato che i primi 4 bit devono essere posti a 1 mentre gli altri a 0. In questo caso concordo con quello che dici tu e facendo la somma ottengo un numero univoco. Il problema però è come comportarmi quando per esempio ho gli elementi 999 e 1000 nel mio insieme. In questo caso dovrei fare 2^999+2^1000 e poi il modulo, ma ovviamente non credo di poter calcolare i primi due numeri.
Con la somma noi non perdiamo niente, abbiamo somme uguali con numeri diversi, ma allo stesso modo con l'hash fatto dalla libreria avrai hash uguali con numeri diversi.
Il problema è che noi avremo somme uguali che mi produrranno collisioni OLTRE alle collisioni che di suo la funzione hash produce con chiavi differenti.
Come gia' proposto a pagina 2, io userei una Hashtable la cui chiave e' una stringa di 1000 caratteri, con ogni carattere che puo' valere '0' o '1'.
L'ottimizzazione a bit, se vuoi farla, potrai farla in seguito con calma.
Ovviamente il vettore di interi nel mio codice rappresenta la mappa di bit.
Il problema è che noi avremo somme uguali che mi produrranno collisioni OLTRE alle collisioni che di suo la funzione hash produce con chiavi differenti.
Fanno esattamente la stessa cosa.
L'hash è su un unsiegned int, il modulo a 2^24 crea altre collisioni, ma è la stessa cosa che avviene all'interno della libreria: l'hash effettivo della libreria non è quello che ti calcoli in quella funzione, ma hash % dimensione del vettore.
E' assolutamente identico a quello che faccio io, solo che parto già con 2^24 elementi per evitare da subito collisioni. La libreria magari parte con 2^8, poi con 2^9, poi con 2^10, semplicemente l'hash viene riadattato in base alla dimensione della tabella partendo da quell'unsigned int ed utilizzando il modulo.
Sono esattamente equivalenti e non ci sono collisioni in più o in meno, per carità, magari ci sarebbe da studiare se effettivamente una funzione di hashing o l'altra spalma bene i valori su tutto lo spazio di indirizzamento, ma questo è un altro discorso.
Come gia' proposto a pagina 2, io userei una Hashtable la cui chiave e' una stringa di 1000 caratteri, con ogni carattere che puo' valere '0' o '1'.
L'ottimizzazione a bit, se vuoi farla, potrai farla in seguito con calma.
Secondo me è più complesso così che con i bit, è molto più complesso arrivare ad un hash coerente.
Ci vuole un minuto per fare due funzioni che accedono ai bit.
Ad esempio supponendo che si voglia mappare i bit:
int set_bit(unsigned int *data, int index)
{
if(index < 0 || index > (SIZE_BITS - 1))
return -1;
data[SIZE_BITS/(sizeof(int) * 8)] |= 1 << (index % (sizeof(int) * 8));
return 0;
}
int get_bit(unsigned int *data, int index)
{
if(index < 0 || index > (SIZE_BITS - 1))
return -1;
return ((data[SIZE_BITS/(sizeof(int) * 8)] & (1 << (index % (sizeof(int) * 8))) > 0) ? 1 | 0;
}
Fatto alla svelta e senza tutti i crismi di leggibilità.
PS: mi sono accorto che nel codice di prima dovevo usare unsigned int e non int.
Secondo me è più complesso così che con i bit, ci vuole un minuto per fare due funzioni che accedono ai bit.
Ho letto i tuoi interventi Cionci. Anche io farei esattamente come te, che era anche una delle mie proposte.
Cerchiamo di arrivare alla hastable per gradi, qualunque delle 2 soluzioni e' sempre meglio che scartare la hastable e fare una lista di stringhe magari neppure ordinata.
Poi che sia piu' complessa la stringa con i caratteri direi di no, anzi direi piu' semplice perche' la get e la set sarebbero oltremodo banali.
Sicuramente i packed bit sarebbero piu' ottimizzati e il sistema oltre a occupare meno sarebbe anche piu' veloce, questo si'.
Poi che sia piu' complessa la stringa con i caratteri direi di no, anzi direi piu' semplice perche' la get e la set sarebbero oltremodo banali.
Quello è sicuro, ma passare da stringa ad hash sarebbe più complesso. Come faresti ?
Quello è sicuro, ma passare da stringa ad hash sarebbe più complesso. Come faresti ?
Ma quello spero bene che lo faccia la libreria all'interno no?
Altrimenti che cavolo fa sta libereria? Ha solo una lista di liste?
Ho visto che:
-Devo costruire l'oggetto trattato (in C++ non si puo' fare altrimenti)
-Devo dare il costruttore di copia (in C++ non si puo' fare altrimenti)
-Se devo anche dare la funzione di hash direi che posso lasciare perdere e la hastable me la faccio da zero...
Normalmente ogni implementazione di hastable dovrebbe avere la sua funzione di hash interna che calcola la hash per ciascuna chiave. ed e' per questo che possono funzionare solo su strutture che non contengono puntatori. Per costruire la hash e' sufficiente giocare un po' con i byte della chiave, che appunto non devono contenere puntatori (altrimenti le uguaglianze vanno a farsi benedire).
Poi se si vuole fare l'override di tale funzione, per ottimizzare al massimo ben venga, ma spero che in quella libreria non sia necessario.
Parlavo della costruzione dell'hash table da zero, non dell'uso della libreria.
Quella libreria ha una funzione di hashing di default che prende in input una stringa e quindi dovrebbe andare bene per la stringa di 1 e 0, anche se a questo punto alla stringa di 1 e 0 imho è preferibile una stringa con i numeri stampati direttamente dentro separati da spazio, sempre di chiave univoca si tratta e pure più economica da costruire ;)
Parlavo della costruzione dell'hash table da zero, non dell'uso della libreria.
Scusami, non avevo capito
Quella libreria ha una funzione di hashing di default che prende in input una stringa e quindi dovrebbe andare bene per la stringa di 1 e 0, anche se a questo punto alla stringa di 1 e 0 imho è preferibile una stringa con i numeri stampati direttamente dentro separati da spazio, sempre di chiave univoca si tratta e pure più economica da costruire ;)
Pero' li dovresti ordinare, e se la quantita' di numeri di ciascun insieme e' altra non risparmia piu' di tanto.
Vabbe', che si faccia come si vuole.
Solo dico che se non si usa una hastable e' uno di quei classici casi in cui si usa il C++ pensando di andare piu' veloci, e poi a causa di *, &, [], ->, ***, int i+++=++i; si lascia perdere il vero concetto di ingegneria del software e si fanno le cose lente, illeggibili o fatto con i piedi.
E non mi sto assolutamente riferendo a te, fracarro.
Nella tua soluzione di sotware privato puoi fare quello che vuoi.
Usa una soluzione che potrai rileggere e capire anche fra 2 anni, quando magari dovrai rimetterci mano sopra.
Se pero' in un software commerciale vedo che per controllare l'esistenza di una sequenza binaria in un lungo elenco, al posto che un hastable ( poco piu' di O(1)) vedo un loop su tutti gli elementi ( O(n) ), neppure ordinato (che sarebbe O(ln(n)) ) allora mi cascano le wallas.
fracarro
19-02-2008, 13:50
SSSSSSSIIIIIIIIIIIIIIIIIIIIIIII !!!!!!!!!!!!!! :winner: :winner: :winner:
Ci sono riuscito. Sono riuscito a trovare una soluzione banale che è veloce, risparmai spazio e mi garantisce chiavi univoche per ogni insieme generato.
Ricapitolando (visto che a questo punto se ne sono dette di cose):
Poichè la funzione di hash prende in input una stringa dovevo trovare il modo di generare una stringa diverse (la famosa chiave da dare in pasto alla funzione hash) per ogni insieme generato nel minor tempo possibile, risparmiando memoria e potendo eventualmente controllare le successive collisioni velocemente. Per farlo ho fatto così (supponiamo che gli elementi variano da 1 a 1000):
- dichiarazione di un array di unsigned char con un numero di caselle pari a ceil(1000/ sizeof(unsigned char)*8);
- l'array viene inizializzato a zero perchè allocato con la calloc. ( Per sicurezza lo azzero anche io poi vedo se posso eliminare questa costosa inizializzazione).
A questo punto la tecnica di base che già avevamo discusso prevedeva di porre ad 1 i bit in corrispondenza degli elementi presenti nell'insieme. Il problema con questa soluzione è che alla fine l'array di unsigned char era si una stringa ma se una delle caselle dell'array aveva valore 0 la chiave veniva troncata e ciò era sbagliato. Per risolvere il problema alla fonte ho semplicemente imposto dopo l'inizializzazione a zero dell'array che il primo bit di ogni cella deve essere 1. Ovviamente questo implica che i bit a disposizione diventano 7 per cella invece che 8 e che se per esempio voglio settare il bit corrispondente all'elemento 8 andrò a settare il bit 10 invece che l'8.
In questo modo dopo aver effettuato le operazioni sui bit con questa modifica ottengo la stramaledetta chiave da passare alla funzione hash.
Inoltre questo metodo mi permette anche di effettuare in caso di collisioni un confronto veloce tramite le operazioni sui bit, e di ridurre la memoria necessaria per la chiave. Ovviamente il tutto avendo eliminato l'ordinamento che prima era necessario per generare la chiave.
fracarro
19-02-2008, 13:57
Se pero' in un software commerciale vedo che per controllare l'esistenza di una sequenza binaria in un lungo elenco, al posto che un hastable ( poco piu' di O(1)) vedo un loop su tutti gli elementi ( O(n) ), neppure ordinato (che sarebbe O(ln(n)) ) allora mi cascano le wallas.
IMHO Questa direi che è incompetenza perchè un DB gestito in questo modo diventa in breve lentissimo nella ricerca degli elementi se li deve scorrere uno per uno. E' come fare la ricerca lineare, che richiede O(n), di un elemento in un array ordinato mentre basta applicare la ricerca binaria per ridurre il costo dell'operazione a O(logn).
Ad ogni modo come detto sopra ho risolto lavorando con i bit ed ottenendo tutti i vantaggi da essi derivati.
fracarro
19-02-2008, 13:59
Parlavo della costruzione dell'hash table da zero, non dell'uso della libreria.
Quella libreria ha una funzione di hashing di default che prende in input una stringa e quindi dovrebbe andare bene per la stringa di 1 e 0, anche se a questo punto alla stringa di 1 e 0 imho è preferibile una stringa con i numeri stampati direttamente dentro separati da spazio, sempre di chiave univoca si tratta e pure più economica da costruire ;)
Esattamente la mia vecchia soluzione (utilizzavo le virgole per separare gli elementi) che però come fatto notare anche da gugoXX richiedeva l'ordinamento preventivo per funzionare correttamente.
SSSSSSSIIIIIIIIIIIIIIIIIIIIIIII !!!!!!!!!!!!!! :winner: :winner: :winner:
Ci sono riuscito. Sono riuscito a trovare una soluzione banale che è veloce, risparmai spazio e mi garantisce chiavi univoche per ogni insieme generato.
Bene che tu ci sia riuscito.
Non ho capito il problema dei byte a 0. Se e' un array di unsinged char, non per forza deve essere considerato stringa.
e non penso che la libreria usata si arrabbi.
Dovresti potere anche avere dei byte a 0 senza problemi.
Alla fine allora hai fatto una mappa di bit...
gugoXX: ha utilizzato la mappa di bit, non una stringa di char a '0' o a '1'. Ha solamente sfruttato 7 bit su 8 mettendo il msb a 1
fracarro
19-02-2008, 14:04
Alla fine allora hai fatto una mappa di bit...
Yesssss, :D
grazie a tutti per l'aiuto.
Alla fine allora hai fatto una mappa di bit...
gugoXX: ha utilizzato la mappa di bit, non una stringa di char a '0' o a '1'. Ha solamente sfruttato 7 bit su 8 mettendo il msb a 1
Sisi', ho riletto meglio dopo.
ero stato tratto in inganno dalla dimensione dell'array (1000/ sizeof(unsigned char)*8)
Ma non e' sbagliato? E' proprio di 1000, quanto servirebbe per lo stringone. Boh?
E poi non ho capito il problema del byte a 0 in un BYTE[].
Fa lo stesso basta che hai capito cosa sono le hastable.
Solo non ho capito il problema del byte a 0 ma fa lo stesso.
In pratica se c'è un intero byte a zero nella stringa, viene interpretato come il carattere di fine stringa dalla funzione che crea l'hash, quindi la creazione termina prima.
fracarro: ricordati che serve un carattere di fine stringa, quindi il numero di byte da usare deve essere (N / 8) + 1 (o + 2 se N non è multiplo di 8).
fracarro
19-02-2008, 14:27
...
fracarro: ricordati che serve un carattere di fine stringa, quindi il numero di byte da usare deve essere (N / 8) + 1 (o + 2 se N non è multiplo di 8).
Grazie del consiglio, avevo già provveduto e poichè viene fatta l'inizializzazione a zero dell'array sono sicuro che l'ultima casella resterà a zero e indicherà il fine stringa.
In pratica se c'è un intero byte a zero nella stringa, viene interpretato come il carattere di fine stringa dalla funzione che crea l'hash, quindi la creazione termina prima.
fracarro: ricordati che serve un carattere di fine stringa, quindi il numero di byte da usare deve essere (N / 8) + 1 (o + 2 se N non è multiplo di 8).
e se gli avessi passato un array di interi?
Come avrebbe fatto a capire la lunghezza di ciascuna chiave?
Boo? Ma siamo sicuri che possa funzionare con un puntatore nella struttura e non direttamente con il valore della chiave? Nell'esempio e' scritto cosi', ma non riesco a capire come possa funzionare per l'array di interi quindi...
Mi spiego:
Io avrei fatto una struttura fissa, tipo
struct{
unsigned char pippo[1000/8];
int value;
}
e non
struct{
unsigned* pippo;
int value;
}
e secondo me avrei potuto avere anche dei byte a zero.
Ma se invece la struttura fosse stata fatta tipo
struct{
int* pippo;
int value;
}
come avrebbe fatto l'algoritmo di hashing a capire quanto era lungo ciascun mio array di interi, per calcolarne la hash?
fracarro
19-02-2008, 14:41
e se gli avessi passato un array di interi?
Come avrebbe fatto a capire la lunghezza di ciascuna chiave?
Boo? Ma siamo sicuri che possa funzionare con un puntatore nella struttura e non direttamente con il valore della chiave? Nell'esempio e' scritto cosi', ma non riesco a capire come possa funzionare per l'array di interi quindi...
Mi spiego:
Io avrei fatto una struttura fissa, tipo
struct{
unsigned char pippo[1000/8];
int value;
}
e non
struct{
unsigned* pippo;
int value;
}
e secondo me avrei potuto avere anche dei byte a zero.
Ma se invece la struttura fosse stata fatta tipo
struct{
int* pippo;
int value;
}
come avrebbe fatto l'algoritmo di hashing a capire quanto era lungo ciascun mio array di interi, per calcolarne la hash?
Non è necessario conoscere la dimensione della chiave in quanto utilizzando un array di unsigned char invece che int si ottiene direttamente una stringa e sarà il carattere di fine stringa ad indicare alla funzione hash quando è grande.
ecco. e allora nel caso di int*
struct{
int* pippo;
int value;
}
Come avrebbe fatto?
Manbearpig
19-02-2008, 14:44
Boh a me sta storia dei byte a 0 sembra una stupidata, scusa eh ma la libreria dice che devi usare una TUA funzione hash, perche' ti ostini ad usare quella predefinita? hshinit e' fatto apposta in modo che tu possa passargli dei puntatori a funzione.
gugoXX: lascia perdere la struttura, lui ha usato quel metodo per generare la chiave.
fracarro
19-02-2008, 15:05
Boh a me sta storia dei byte a 0 sembra una stupidata, scusa eh ma la libreria dice che devi usare una TUA funzione hash, perche' ti ostini ad usare quella predefinita? hshinit e' fatto apposta in modo che tu possa passargli dei puntatori a funzione.
Perchè è veloce e conveniente passare alla funzione hash una stringa come ho fatto io.
Supponiamo di cambiare la funzione hash e di fargli prendere un intero k in input. A questo punto bisogna trovare un sistema per generare velocemente l'intero k a partire dagli elementi dell'insieme "garantendo" che k è diverso per ogni insieme generabile. C'è un modo?
Supponiamo di cambiare la funzione hash e di fargli prendere un intero k in input. A questo punto bisogna trovare un sistema per generare velocemente l'intero k a partire dagli elementi dell'insieme "garantendo" che k è diverso per ogni insieme generabile.
No...non c'è alcuna speranza...K DEVE essere univoco e quindi scelto da un insieme con cardinalità uguale o maggiore di quello dell'insieme degli insiemi.
Manbearpig si riferiva a passare ad esempio la tua struttura dati (che sarà un vettore di interi, mi immagino) ed in base a quella generare l'intero.
Come fare è abbastanza semplice (sempre contando sulla somma come hash).
data è il vettore di interi del tuo insieme (non la mappa di bit).
hash += 1 << (data[i] % 32);
E' esattamente equivalente a fare la mappa di bit e poi fare la somma degli interi che la costituiscono.
fracarro
19-02-2008, 15:27
No...non c'è alcuna speranza...K DEVE essere univoco e quindi scelto da un insieme con cardinalità uguale o maggiore di quello dell'insieme degli insiemi.
Manbearpig si riferiva a passare ad esempio la tua struttura dati (che sarà un vettore di interi, mi immagino) ed in base a quella generare l'intero.
Come fare è abbastanza semplice (sempre contando sulla somma come hash).
data è il vettore di interi del tuo insieme (non la mappa di bit).
hash += 1 << (data[i] % 32);
E' esattamente equivalente a fare la mappa di bit e poi fare la somma degli interi che la costituiscono.
Ho capito, quindi effettuerebbe solo un'operazione in più per generare la chiave. E' un'alternativa, ma leggermente più costosa.
Ho capito, quindi effettuerebbe solo un'operazione in più per generare la chiave. E' un'alternativa, ma leggermente più costosa.
Scusa, ma a me sembra molto meno costosa, in quanto non devi generare la chiave, i dati stessi sono la chiave.
fracarro
19-02-2008, 16:54
Scusa, ma a me sembra molto meno costosa, in quanto non devi generare la chiave, i dati stessi sono la chiave.
non devi fare la somma degli interi che la costituiscono per ottenere la chiave?
non devi fare la somma degli interi che la costituiscono per ottenere la chiave?
E te come fai per costruirti la mappa di bit ? E come fa la funzione implementata nella libreria a costruirsi l'hash dalla stringa ? Metti insieme queste operazioni e vedrai che sono molto più costose che a fare una sola somma ;)
fracarro
19-02-2008, 17:08
E te come fai per costruirti la mappa di bit ? E come fa la funzione implementata nella libreria a costruirsi l'hash dalla stringa ? Metti insieme queste operazioni e vedrai che sono molto più costose che a fare una sola somma ;)
Allora, non voglio insistere ma forse qualcosa mi sfugge. Se ho capito bene quest'altra funzione lavora così:
Per ogni casella dell'array effettui un'operazione di modulo 32, uno shift ed una somma che ti permettono di ottenere lo slot di destinazione.
Nel mio caso, per ogni casella dell'array io devo settare un bit a 1 e poi passare il risultato alla funzione hash che tramite il modulo stabilisce lo slot di destinazione. Perchè la mia operazione è molto più costosa?
Inoltre una volta individuato con il tuo metodo lo slot di destinazione se voglio verificare la presenza di un elemento nella tabella hash il confronto su cosa lo faccio? Nel mio caso basta confrontare le chiavi tramite i bit, nel tuo?
fracarro: provo a rispiegarti tutto da capo.
Modo A:
1) hai un vettore di numeri non ordinati
2) ti costruisci una stringa con la mappa di bit
3) quando vuoi aggiungere un insieme alla tabella, la libreria passa la chiave ad una funzione che produce un unsigned int a partire dalla stringa (nota che questo unsigned int non individua lo slot della hashtable, ma per individuarlo deve essere fatto un modulo rispetto alla dimensione della hashtable)
Modo B (che ti ho suggerito):
1) hai il vettore di numeri non ordinati
2) quando vuoi aggiungere un insieme alla tabella, la libreria passa la chiave ad una funzione che produce un unsigned int a partire dall'insieme di numeri non ordinati
Qual è più veloce ?
Quella somma che ho scritto sopra serve per calcolare l'hash nella funzione che devi passare alla libreria, non serve per calcolare la chiave.
fracarro
19-02-2008, 17:53
fracarro: provo a rispiegarti tutto da capo.
Modo A:
1) hai un vettore di numeri non ordinati
2) ti costruisci una stringa con la mappa di bit
3) quando vuoi aggiungere un insieme alla tabella, la libreria passa la chiave ad una funzione che produce un unsigned int a partire dalla stringa (nota che questo unsigned int non individua lo slot della hashtable, ma per individuarlo deve essere fatto un modulo rispetto alla dimensione della hashtable)
Modo B (che ti ho suggerito):
1) hai il vettore di numeri non ordinati
2) quando vuoi aggiungere un insieme alla tabella, la libreria passa la chiave ad una funzione che produce un unsigned int a partire dall'insieme di numeri non ordinati
Qual è più veloce ?
Quella somma che ho scritto sopra serve per calcolare l'hash nella funzione che devi passare alla libreria, non serve per calcolare la chiave.
Se il costo della funzione hash della libreria è pari alla somma da te indicata l'operazione in più che faccio è la costruzione della mappa dei bit, giusto?
Ok, per me quello è un costo accettabile anche perchè mi permette avendo una chiave associata ad ogni insieme di poter verificare ogni qual volta c'è una collisione se quell'insieme è o meno presente nella hashtable.
Non ho capito invece tu come fai questa verifica. Ossia, dato un insieme S, tu tramite la tua somma generi lo slot di destinazione nella hashtable e lo inserisci. A questo punto se io ti passo un nuovo insieme S1 tale che la destinazione della hashtable sia la stessa come faccio a distinguere S ed S1?
Secondo punto. La tua funzione hash se gli do l'insieme 3,7 mi restituisce 2^(3-1) + 2^(7-1) = 68 giusto? Ok se questa somma eccede la dimensione della tabella fai il modulo della somma per la dimensione della tabella?
Hai ragione, non avevo pensato alla verifica in caso di collisioni, anche se la verifica si potrebbe fare con un costo pari alla costruzione della mappa di bit di due insiemi, quindi di fatto il costo complessivo sarebbe lo stesso in caso di collisione, ma le collisioni si dovrebbero verificare poco di frequente.
Ok se questa somma eccede la dimensione della tabella fai il modulo della somma per la dimensione della tabella?
Questa cosa ci pensa la libreria a farla...anche nel caso della funzione hash di default.
fracarro
20-02-2008, 09:00
...
Questa cosa ci pensa la libreria a farla...anche nel caso della funzione hash di default.
Ho solo un dubbio riguardo questa cosa. Mi spiego meglio.
Nel mio caso io uno una chiave k per ogni insieme distinto di U. Quindi l'assegnazione degli slot dipende esclusivamente dalla funzione hash h:K->table_size. In teoria una buona funzione hash fa si che il numero di elementi per slot dovrebbe essere pari a |U|/table_size (distribuzione uniforme). Per esempio potrei fare un semplice hash con k%table_hash. Questo è quello che più o meno mi aspetto dalla funzione.
Nel tuo caso se oltre al primo modulo applicato su ogni elemento dell'array ne faccio un secondo nel caso in cui la somma eccede la table_hash. Questo mi fa venire il dubbio che la distribuzione possa essere più sbilanciata perchè il numero di elementi su cui faccio il modulo table_hash è inferiore a K. (per capire l'idea dovresti supporre per un attimo che lo slot che generi e su cui fai il successivo modulo rappresenti anche la chiave dell'insieme. In questo caso quello che succede è che più insiemi hannno la stessa chiave sulla quale viene applico il modulo table_size).
Ad ogni modo questo problema si può facilmente risolvere conoscendo il numero iniziale di elementi N ed allocando una table_hash maggiore di 31*N (che è la somma massima producibile dell'array). In questo modo il secondo modulo diventa inutile e il long da te prodotto va bene.
So di non essere stato chiaro perchè questo è un dubbio che mi è venuto e non mi è tanto chiaro a me figuriamoci spiegarlo ad altri.
Questo dubbio ce l'avevo anche io sia ben chiaro, ma non è così importante la cosa. Dubito che ci sia un distribuzione uniforme, ma dubito anche che ci sia una grande differenza su tutta la distribuzione.
Non puoi allocare 2^32 slot perché metteresti in ginocchio il sistema (sono 4 GB di ram).
Reimplementando la funzione hash del modulo comunque il secondo modulo non viene fatto, ci pensa la libreria a farlo comunque (sia nel caso della sua hash di default che di quella modificata), questo perché devi mappare 2^32 elementi su 2^N slot con N minore di 32.
Ho fatto due prove...e la distribuzione è molto uniforme...
fracarro
20-02-2008, 11:16
Ho fatto due prove...e la distribuzione è molto uniforme...
Ok, grazie, un dubbio in meno.
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.