Newsgroup: it.comp.lang.c
Titolo: Tabelle hash

Sto sviluppando, per un esame all'università, una piccola libreria C che
gestisca tabelle hash con liste di trabocco su disco, che sia capace di
essere efficiente per quanto riguarda le solite operazioni di
inserimento, cancellazione e ricerca anche in presenza di una decina di
milioni di record (tra l'altro ho già postato in richiesta di aiuto
sulla funzione _chsize() (vedi fine messaggio)).
Prendiamo buona l'ipotesi di una distribuzione uniforme delle chiavi
nella tabella hash.
Ora, il mio problema è questo : non riesco a capire se ho effettivamente
scritto una libreria veloce. Infatti, se un solo inserimento in un file
contenente taanti records (ho provato con uno che  conteneva  2 milioni
di records) è abbastanza veloce (<< 1 sec su di  un PII), l'inserimento
di 15000 records consecutivamente  per esempio, mi porta via parecchio
(credo) tempo (circa 40 secondi, sempre su PII), a partire da un file
vuoto!
Il dubbio è proprio qui : creare un database di 100000 records, tramite
l'uso delle tabelle hash con liste di trabocco, quanto dovrebbe in
teoria prendere? Lo so che il sistema sul quale gira influisce
parecchio, ma, considerato che il mio sistema è un PII con un hard disk
'normale', come drovrei regolarmi?
Per esempio, la insert(file,key), in caso di inserimento con successo,
fa un numero di accessi al disco, in lettura/scrittura, pari a 6/7 circa
(caso medio), considerate gli accessi alla tabella hash, ai buckets,
l'aggiornamente, la lettura del record associato alla chiave (che tra
l'altro, è memorizzato su di un secondo file) ecc....
Può essere il numero elevato di accessi al disco il collo di bottiglia?
Un'altra cosa. La tecnica che uso mi permette di mantenere la lunghezza
del file entro dimensioni accetabili all'inizio. Se però, vengono
inseriti dalla tabella diciamo 10 milioni di records, le sue dimensioni
crescono parecchio.
A questo punto, se si effettuano un notevole numero di rimozioni, la
grandezza del file rimane comunque la stessa. In C ANSI purtroppo, non
esiste nessuna funzione per dimensionare un file ad una nuova grandezza
(la _chsize() del Visual C non è ANSI...).
Qualche idea?
Grazie per la pazienza di esser arrivati fin qui! Ciao.

crescono parecchio.
Interessante... effettui una riorganizzazione della tabella di
hash ? Questo non comporta complicazioni nella ricerca per colpa
della diversa conformazione delle catene di collisioni ?
Comunque io, per questioni di velocita', tenevo la tabella di
hash solamente in memoria centrale e le catene di record su
disco, andando a effettuarne gli aggiornamenti dell'indice
solo alla chiusura del file. Ho provato a implementare caching
di vario tipo con qualche risultato ma alla fine i risultati
sono sempre stati abbastanza deludenti e ho quindi usato il
sistema di sorting che ti ho detto.
Una possibilita' che mi e' venuta in mente in questo momento
e' quella organizzare le liste di collisione in cluster da N
chiavi in modo da dividere per N il numero di I/O fisici fatto;
questo pero' comporta uno spreco di spazio visto che le voci
non usate nella pagina di collisione sarebbero sprecate
(pero' basterebbe un puntatore per pagina invece di un
puntatore per ogni record della lista di collisione).
Per strutture aggiornabili dinamicamente su memoria esterna
credo che altri approcci (come B*Tree) siano preferibili.
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

 credo che altri approcci (come B*Tree) siano preferibili.
Già. Le specifiche del progetto parlavano però chiaro: utilizzare tabelle
hash con liste di trabocco. Comunque,  per quanto riguarda la questione della
lentezza delle funzioni di inserimento/ricerca/cancellazione, facendo alcuni
test, ho visto che in fondo non erano poi così lente e che i tempi di attesa
erano, come dire, fisiologici.....
Il problema che invece mi stava più a cuore era quello dello spreco di spazio
su disco. Come ho già detto, una volta inserite 10000000 di chiavi, il
database diventa bello largo e non può essere ridimensionato se non tramite
una lentissima operazione che non sto qui a descriverti ma di cui potrai
benissimo immaginarne il funzionamento. Per risolvere tale problema, mi era
venuto in mente l'utilizzo delle funzioni a basso livello di accesso al
disco. Tramite la chsize() (è una funzione presente sul compilatore Visual C,
ma non è ANSI) è possibile troncare (ciò che serve a noi) od estendere un
file. A costo di un certo numero di operazioni di I/O in più per le funzioni
di ricerca/inserimento/cancellazione, è possibile mantenere le dimensioni del
database ottimali (o quasi...).
Il fatto però è che il nostro prof. ha esplicitamente vietato l'uso di
funzioni non ANSI, "perchè non v'è n'è bisogno alcuno", a detta sua.
Beh, tanto meglio. Il codice che avevo scritto per implementare quest'ultimo
caso non funzionava molto bene!
Ciao e grazie per la tua risposta.
Lucas.