Newsgroup: it.comp.lang.visual-basic
Titolo: Algoritmi per indici

Vorrei usare un file per tenere traccia di un numero molto alto di
stringhe a lunghezza fissa.
Le funzioni che mi servono sono "inserimento nuova stringa" e "verifica
esistenza stringa".
Banale, direte voi, ma vorrei che la verifica fosse istantanea (senza
dover leggere tutto il file, quindi) come avverrebbe con un DB indicizzato.
E ovviamente vorrei evitare che anche l'inserimento sia lento (cosa che
avverrebbe se inserissi le stringhe ordinate)
Non voglio portarmi dietro dipendenze di alcun genere, per cui non voglio
usare Access nè altro, ma un semplice file binario.
Avevo fatto tempo fa, un programma basato sugli alberi bilanciati che
creava in memoria una struttura utile al mio scopo e che consentiva di
inserire nuovi elementi e verificare l'esistenza nell'albero degli
elementi stessi in qualche decimillesimo di secondo.
Il problema e che non posso caricare 10.000.000 di stringhe in memoria.
Per cui devo capire come fanno i DB a lavorare su file.
Ho (frettolosamente) cercato qualche algoritmo in giro o qualche
spiegazione su come funzionino nel dettaglio gli indici, ma non ho trovato
nulla di ispirante.
Lo so che esistono DB open source, ma vorrei evitare di spulciare in tutto
quel codice alla ricerca dell'algoritmo che mi serve.
Qualcuno ha qualche idea? 
termoPilucco
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it


SQLite è un database in un unico file. 

 SQLite è un database in un unico file.
Fra i sorgenti di SQLito ho trovato btree.c che dovrebbe essere
l'implementazione su file dell'algoritmo che cercavo...
spero di capire esattemente come funziona.
Comunque credo che usando le parole chiave "btree" e "Knuth" su google
vengano fuori anche spiegazioni estese sulla cosa.
Spero non sia troppo complicato.


termoPilucco wrote:
premesso che sei un temerario :-)
in effetti ti toccherà implementare, nel file, qualcosa di 
simile ad un mini file-sistem.
Anche io non riesco ad immaginare altro (in termini molto 
generici e vaghi) che una sorta di mappatura su disco della 
rappresentazione in ram di un albero (con dati "sparsi" in modo 
da poter crescere dinamicamente dentro il file laddove c'è 
posto, tipo in coda, con puntatori doppi, e tale da contenere 
soltanto puntatori a stringhe di dati o ad altri sotto-alberi, 
diciamo)
L'albero crescerebbe ad inserimento (logico, non fisico, in 
quanto i dati sono aggiunti in coda, ma agganciati da puntatori 
di tipo long, che sono offset nel file), e quindi 
tendenzialmente potrebbe anche non essere un albero bilanciato 
vero, ma uno di forma irregolare.
Non riesco a figurarmi il compito in modo chiaro senza fare 
tentativi, ma darei ad ogni nodo una struttura piuttosto 
semplice del tipo, puntatore ad un unico dato reale (la stringa) 
e sua lunghezza, puntatore ad un sottonodo sinistro e a uno destro.
Se devi anche poter cancellare, già le cose si complicano perché 
ci vorrebbe una lista linkata degli spezzoni vuoti e un 
mostruoso allocatore (che tenta il best-fit sui vuoti prima di 
sbattere nuovi dati in coda al file. Ma non l'hai detto, eh he 
he, quindi non ci fasciamo la testa in anticipo !)
Certo, gli alberi random sono veloci in inserimento perché non 
devi mai spostare niente né riequilibrare la struttura, ma in 
fase di ricerca, se la sequenza di inserimento dei dati è 
infelice o al limite la peggiore possibile, possono anche 
sfociare in liste semplici che ti costringono alla scansione 
intera, mi par di rammentare (anche se è proprio il caso estremo 
e molto improbabile)
Cmq le prestazioni in ricerca, accesso a disco a parte (ma si 
può sempre tenere in cache o in un file a parte almeno le 
strutture dei puntatori, relegando i dati veri e propri al 
disco, o a un file diverso), dovrebbero essere mediamente ancora 
logaritmiche, sempre se non ricordo male.
P.S.
bisognerebbe anche gestire i dati nulli (tipo nei nodi appena 
creati) e stabilire se l'inserimento di una nuova stringa (e di 
un nuovo nodo) debba avvenire a destra del valore inferiore o a 
sinistra di quello superiore (gemmando l'una piuttosto che 
l'altra branca). Questa decisione è critica perché una decisione 
fissa, è veloce ma espone al rischio di sbilanciamento eccessivo 
della struttura se i dati vengono sottoposti in una sequenza 
sfigata. Decidere im modo ponderato comporta di stabilire una 
funzione di lookup che "si renda conto" del punto in cui si 
trova (del tipo, per giungere sin qui ho attraversato X volte il 
ramo destro e Y quello sinistro, per cui scelgo di gemmare un 
ramo da una certa parte piuttosto che da un altra per correggere 
gli sbilanciamenti. Ahhh, a parole le cose son semplici a dirsi, 
ma poi ...)
ciao
cccp++mario
P.P.S.
Cmq io implementerei due file, lasciando almeno un po' id lavoro 
"allocatorio" al S.O.
Tra l'altro, in questo modo il file dei soli descrittori può 
essere anche gestito diversamente dall'albero, ossia come array 
di puntatori ORDINATO ai dati (sparsi e disordinati dell'altro 
file).
In questo caso, è vero, paghi un po' di più nell'inserimento 
perché potresti dover spostare molti puntatori in avanti (cmq in 
una sola lettura di un blocco contiguo), ma poi la ricerca 
diventa una ricerca binaria pura, con prestazioni logaritmo in 
base due del numero di elementi totali tra cui scegliere, il 
ché, mi risulta, è il massimo che si possa ottenere)


 ché, mi risulta, è il massimo che si possa ottenere)
si può fare log(log(n)) :)
Nel caso i dati siano ordinati e uniformemente distribuiti (e sarebbe il
mio caso). Basta infatti interpolare i dati anzichè cercare in modo
dicotomico: per esempio quando apri la pagine gialle per cercare "Abate"
non le apri in mezzo ma quasi all'inizio.
tra l 'altro log(log(n)) cresce talmente poco che viene considerato una
costante uguale a 6 ;)
infatti 2^(2^6)= 1,84467440737096E+19 = abbastanza record da riempire
tanti HD.


[SNIP]
Anche io sto studiando un algoritmo del genere per una mia applicazione 
anche se dovrò muovere molti più dati di quanti ne hai ipotizzato te.
Per ora sto svolgendo il tutto su un db MySql ma sto cercando una 
soluzione che non comporti altre installazioni oltre al mio software in 
modo da poter gestire la cosa senza aiuti esterni.
Se ti va una mano per poter trovere entrambi la soluzione, fai un 
fischio la mail è quella che posto basta levare NO SPAM :)
Magari riusciamo a trovare nuove soluzioni e creiamo il DB definitivo .. :)
e magari lo chiamiamo AccessXXXP
Saluti .. :)
-- 
[CapoBecchino]
Cimiteri associati & Co.
Da Barzellette.it:
In una lapide di un cimitero c'è questo epitaffio:
"Qui riposa, per la seconda volta, Ernesto Rossi. Una prece."
Un tizio, incuriosito, chiede informazioni al necroforo che, fra l'altro,
conosceva il defunto e così gli risponde:
- Vede signore, il defunto Rossi in vita lavorava in Comune...

 
ciao
cccp++mario

 effetti. Cmq non lo sapevo. 
termoPilucco


In data Wed, 15 Sep 2004 17:18:07 +0200, termoPilucco scrisse:
Allora, l'algoritmo che avevo a suo tempo implementato in RAM (basandomi sulla
teoria degli alberi red'n'black, ma mettendoci un po' di mio) è un po' lungo e
complicato da passare su NG.
Per cui l'ho pubblicato qui:
http://www.unbelsito.com/vb/alberoBinario.zip
Nota:  i tempi misurati con la funzione timer non sono affidabili quando sono
troppo piccoli, per cui dovete inserire un numero congruo di nodi, in base alla
potenza della vostra cpu, per avere risultati verosimili.
Sul mio Pc l'algoritmo trova un elemento qualunque su 100.000 data la chiave in
0,003 MILLIsecondi (non ho sbagliato a scrivere decimali ne' l'unità di misura).
Sono 3 milionesimi di secondo :O
Si può ottimizzare ulteriormente, soprattutto il consumo della memoria,
eliminando le parti di codice (in particolar modo i membri della classe) che
coinvolgono la visualizzazione grafica.
Nota dolente, anzi debilitante:
Rimane il problema della deallocazione dei nodi: se usate l'eseguibile, il
programma rimane a fare chissà quali "dispose" implicite (magari per decine di
minuti se create alberi con troppi nodi) anche dopo che è sparita la form a
video.
termoPilucco

ti ho mandato due righe in pvt (dato che era c++) su classi 
filtro per vedere files come ram, nel senso della stessa 
sintassi di accesso agli array, non so se il tuo indirizzo 
accetta posta da estranei.
ciao
cccp++mario

In data Wed, 15 Sep 2004 22:13:21 GMT, Soviet_Mario: scrisse:

Li acceterebbe, ma l'indirizzo corretto è il mio nick presso hotmail ;)
termoPilucco

 e magari lo chiamiamo AccessXXXP
Oppure  Ac²es²X³P


 termoPilucco


ho riprovato come mi hai detto
ciao
cccp++mario
P.S.
se non rifunge, pazienza, rinuncio

sintassi di accesso agli array
Arrivato, grazie.
Scusino gli altri.
termoPilucco