Newsgroup: it.comp.lang.visual-basic
Titolo: [!][lungo][noioso] Implementazione BTree in Visual basic

Qualche giorno fa cercavo qualcosa per salvare su disco e ritrovare in seguito
numeri/stringhe in modo efficiente ed era saltato fuori l'algoritmo Btree.
L'ho "implementato" in Visual basic 6.
Implementato è un parola grossa,. come vedremo avanti, diciamo che ho gettato le
basi per l'implementazione, ma ho ottenuto quanto inizialmente mi serviva.
Intanto lo zuccherino per andare avanti con la lettura:
Ho un milione di chiavi long da inserire nel "DB", ecco i risultati del
minibenchmark che ho fatto:
Popolamento del milione di chiavi nel 'DB': 15,19 sec.
Esecuzione di 1.000.000 ricerche nel DB popolato: 24,5 sec.
tempo medio di ricerca fra un milione di elementi (su disco): 0,0245
millisecondi (25 milionesimi di secondo ;) ) per chiave.
Immagino che il file fosse interamente in cache...
Merito dell'algoritmo Btree non di termoPilucco, comunque.
Il codice per utilizzare la classe è molto lineare:
Dim c As clsBtree
Set c = New clsBtree
' creazione nuovo DB
c.apriDB "c:\pippo.db", true
' inserimento di tre chiavi
c.inserisciChiave 123
c.inserisciChiave 432
c.inserisciChiave 987
' verifica esistenza di due chiavi
If c.esisteChiave(123) Then msgbox "trovato 123!"
If c.esisteChiave(432) Then msgbox "trovato 432!"
' chiusura
c.chiudiDB
Set c = Nothing
Fin qui le cose belle :)
Ora i limiti:
-Uso GET/PUT per l'accesso ai file, quindi non oltre i 2 GB di file, per il
resto la cosa è scalabile.
-Non ho implementato la rimozione di chiavi perchè non serviva ai miei scopi;
chi la vuole fare sono c***i suoi, letteralmente (è la parte più complessa).
-Codice incasinatissimo, come sempre... talvolta credo di non essere in grado di
sintetizzare o trovare l'essenza degli algoritmi...
-Non gestisco in alcun modo la concorrenza, per cui apro il "DB" in modo
esclusivo per evitare problemi di coerenza del file fra letture e scritture
concorrenti.
-Non so cosa possa succedere se l'applicazione che ha aperto il file viene
terminata o salta la corrente... probabilmente si "corrompe il db", ma non ho
preparato alcun "compatta e ripristina".
-ho testato l'inserimento di un milione di chiavi casuali e sono state ritrovate
tutte... ma vista la complessità della cosa non mi stupirei se in casi
particolari qualcosa andasse storto (anche se non credo accada)...
-Le chiavi non puntano a nulla!
A me servivano solo per verificare se una data chiave fosse presente o meno.
Se si vuole che puntino a dei dati veri e propri, occorre modificare la
struttura base (comunque ho messo un commento evidente).
La cosa più ovvia da fare sare far affiancare ad ogni chiave un posizione su un
altro file in modo da recuperare i dati attraverso il "file degli indici".
Credo che molti DB commerciali facciano la stessa cosa.
-Se volete utilizzare effettivamente la classe, togliete la parte di codice
relativa alla treeview che serve solo per verificare che l'albero sia come
atteso.
Sorgenti very early con breve spiegazione in italiano del funzionamento del
Btree qui:
http://www.unbelsito.com/vb/Btree0.1.zip
Nei sorgenti e nell'eseguibile ho impostato:
Const ordineBtree As Integer = 5 
In questo modo la visualizzazione su treeview è pensata per una fruizione umana
(ogni nodi ha al massimo 5 figli ma normalmente 2) 
Se volte utilizzare la classe con profitto impostate tale costante attorno a 151
(75 figli per nodo...).
Tenete conto che una volta scelta la costante si è scelta la compilazione (è
tutto statico) e si è scelto il formato del "db", per cui una volta partiti a
lavorare, non modificatela più.
Io dovrò portare avanti il progetto in una direzione particolare (hash
retrieving), per cui quello che farò non sarà più utilizzabile in questo
progetto.
Se volete trastullarvi con il btree senza inquinarvi il pc con le mie zozzerie,
qui c'è un applet java che mi ha aiutato a verificare la correttezza della mia
implementazione:
http://sky.fit.qut.edu.au/~maire/baobab/baobab.html
Si può anche scaricare e usare in locale.
termoPilucco

 L'ho "implementato" in Visual basic 6.
[snip]
Quanto tempo che non sentivo parlare di BTree :)
Hola
-> GbC|
www.gbcweb.com

 Quanto tempo che non sentivo parlare di BTree :)
Magari avevi anche i sorgenti in VB e mi risparmiavi il lavoro :)
termoPilucco
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

[MEGACUT]
Come ti dissi gia a suo tempo anche io cercavo un algoritmo di 
indicizzazione tipo il btree.
In questo momento sto super occupato con un progetto di criptazione dati 
e il brevetto di un nuovo algoritmo di criptazione ma appena avrò un 
minuto guarderò ciò che tu hai fatto.
Per ora ti dico solo grazie perchè mi hai risparmaito moltissimo lavoro :D
Saluti
-- 
[CapoBecchino]
Cimiteri associati & Co.
ULTIME OFFERTE !!!!
Muori oggi ed avrai uno sconto del 50% / Muori domani ed avrai una 
sepoltura GRATIS!!!

Dannazione ma perchč vi accingete a costruire con VB alberi b-tree o 
cose cosě complicate?
Perchč non vi mettete un tantino a farle in C e a 
supertermopiluccovelocizzare le vostre applicazioni?
  :)
  :)
  :)
  :)
Non mi sto innervosendo eh?
Perň quando penso che gente cosě preparata come voi, insiste nel voler 
usare VB per certi algoritmoni di ottimizzazione... beh vedo il vostro 
lavoro un po' sprecato.
P.S.: Ormai vedo la parola "termopilucco" come riferimento a algoritmi 
ottimizzati :D
-- 
Quando noi ignoranti eravamo di piů,
tutto era piů bello...
(Adriano Celentano)

 
Ma guarda che io non lo sto implementando in vb6 ma in 
vb.net
 :)
Il progetto è sviluppato interamente in 
vb.net
 e non vorrei usare DB 
esterni per svariati motivi, ma mi rendo conto che se non inizio con 
qualcosa dubito che potrò competere con i DB esistenti anche 
semplicemente ottimizzandolo solo per la mia applicazione :)


 ottimizzati :D
oh oh..


 L'ho "implementato" in Visual basic 6.
Giusto l'altro ieri ho trovato un algoritmo BTree implementato in .Net (non
ricordo se 
vb.net
 o c#)
Per cui magari puoi "ripulire" il codice dandoci un'occhiata.
http://www.codeproject.com/csharp/RedBlackCS.asp
Non è un vero BTree ma un albero puramente binario (il classoco red/black)
Ciao

 Ed è esattamente quello che ho ottenuto :)
La butto lì perchè non sono affatto convinto che quello che dirò sia una
soluzione performante, ma hai provato ad usare una semplice Collection?
Ciao

 soluzione performante, ma hai provato ad usare una semplice Collection?
A me serviva qualcosa di permanente (salvabile su disco) e che gestisse un
numero di chiavi che parte da 1.000.000 ma che fosse scalabile (10/100
milioni).
Le collection non sono scalabili (bastano poche decine di migliaia di
elementi per farle andare in crisi) e, a quanto ne so, non si possono
salvare su disco e ricaricare successivamente.
Tra l'altro avevo già fatto in precedenza l'equivalente delle collection
usando alberi binari bilanciati residenti in memoria: pur programmati in
VB6 erano di gran lunga più performanti delle collection :)


 VB6 erano di gran lunga più performanti delle collection :)
Infatti ricordo che anche nei test del mio piccolo progetto XCollection sul
sito comune avevo riscontrato un decadimento pauroso delle prestazioni delle
Collection sopra i 10.000 elementi.
Ciao

 se si parla di array di tipi primitivi, anche VB non se la cava male.
ma parli di VB o di VB.Net?
In ogni caso credo ancora che il C sia più veloce (se usato decentemente 
intendo) di entrambi; forse VB6 ha un vantaggio sul .Net, cioè la 
mancanza di framework ke faccia da tramite col processore, ma in ogni 
caso credo che un algoritmo come l'ordinamento che hai chiesto giri 
molto più velocemente se scritto in C.
-- 
Quando noi ignoranti eravamo di più,
tutto era più bello...
(Adriano Celentano)

 molto più velocemente se scritto in C.
Attenzione: VB.Net viene compilato in memoria a runtime, quindi quello che
gira è puro codice X86.
Il framework non è un coso tipo Java che interpreta il codice.
Comunque dalle mie (pochissime) prove (dei semplici FOR) VB6 e VB.net hanno
prestazioni del tutto analoghe (mi aspettavo qualcosa di più da VB.net),
almeno se compilati con le ottimizzazioni di default.
Ciao

 molto più velocemente se scritto in C.
Ni, io discuto il "molto".


 riferimento a algoritmi ottimizzati :D
come sempre ....lo strumento è funzionale al problema...se diventa "parte"
del problema c'è qualcosa che non va.....
tecnicamente ...
non scriverei mai un driver stampante in VB o Cobol o Delphi
non scriverei mai un gestionale di magazzino in C o C++ o Fortran
non scriverei mai un programma di grafica in Cobol o ADA
....
ciò non toglie che forse tecnicamente si può fare....che date
implementazioni siano ottime fatte in C++ o ADA (ad esempio)anche in campi
non "canonici"
(vedi Autocad e Lisp ...fino a poco tempo fa)
SE
IO non lo so fare....ciò non vuol dire che sia impossibile....
la concezione "ego-centrica" è proprio il "male" ...il peccato originale del
90% dei programmatori
Ritenere che il proprio know-how sia il massimo e conservarlo.
Io son curioso e sperimentatore...SE l'algoritmo di "termo" va bene...e vedo
dove applicarlo .....perchè non dovrei applicarlo? Perchè è fatto in VB???
tutto questo...mi ricorda molto la discussione flame che presi da giovane
non su sto NG
all'epoca io avevo un Archimedes con CPU RISC....aveva il Basic nativo...e
poi comprai l'ANSI C ( 4 floppy!!!...bei tempi tra un po non basta più
neanche un dvd doppio strato!)..e pure...il Prolog....
logicamente la diatriba era RISC vs CISC
come sempre...e come nel caso di sto topic....la verità non sta da nessuna
parte!
TALVOLTA
hai ragione tu
TALVOLTA
ha ragione il "termo"
il furbo programmatore SA' riconoscere quando uno dei due ha ragione...e
riesce ad aver ragione nel 100% dei casi!!!
Pragmatismo...ragazzi...pragmatismo!!!
-- 
Il Wodkino Nazionale è a : 
www.martek.it
Pagina Vb/Bestiario/Lamer Experience :
http://www.martek.it/go.asp?portamia=2
 New Entry nel
bestiario! :-)
---
Messaggio scannerizzato e certificato "Virus free" da AVG free edition.
Checked by AVG anti-virus system (
http://www.grisoft.com
).
Version: 6.0.769 / Virus Database: 516 - Release Date: 24/09/2004

 termoPilucco
Darkbyte [Work]


 Pragmatismo...ragazzi...pragmatismo!!!
Ripeto... rileggiti il mio post va'...


 Ripeto... rileggiti il mio post va'...
eh eh eh...se lo rileggo mi incazzo ancor di più lo sai????
perchè senza togliere nulla a te
(ma allora non togliere nulla a me)
non capisco perchè una cosa "complicata" non si possa fare in VB.......
(già il complicato è una convinzione....non un dato di fatto...oggettivo...)
....
e cmq...se anche tu avessi tutte le ragioni di questo mondo e di tutto
l'Omniverso....
SE..io e "termo" ...VOGLIAMO....usare il VB.....
e lasciacelo usare....!
Dopo tutto VB è IT C e C++ è OT.....su questo NG!
"Termo" non doveva convincere un C-ista o minare in alcun modo la "C
Comunity" ma rendere noto alla comunita' VB-ista una sua implementazione!
...tutto il resto son parole.....
ora lo dico io ...
ecchecazzo!
p.s.
Il flame ciclico " VB skifo C(++) goduria"...lasciamolo fare ai trolloni ed
ai lameroni per piacere!
Saluti!


 ad essere meglio l'algoritmo che hai pensato e scritto tu.
Solo per parlare e senza polemica....
prima o poi in linguaggio macchina ci va a finire sto codice
...e allora si porterà dietro i vizi e le convinzioni del compilatore VB (e
le eventuali ottimizzazioni che il programmatore li ha imposto di usare)
stessa cosa se fosse fatto in C...o C++...o LISP....o che ne so...Ruby
il fatto che sia il miglior codice macchina possibile.....è un altra cosa!
Ci sono Guru che han preso il codice l'han disassemblato e confrontato....
Un compilatore cerca sempre di mediare e risolvere "a modo suo"...qualcuno
in alcune situazioni eccelle in  altre no.....
In molti casi si produce un codice "buono"
Resta il fatto che se ci fosse un team di guru (che non hanno neanche le
grosse SWhouse) che sviluppassero in Assembler il codice sarebbe il +
performante possibile....il fatto è che nessuno oggi come oggi è tanto pazzo
(per i tempi ...per i costi...per il porting da CPU a CPU...e da
architettura ad architettura) da farlo!
Questi problemi son problemi di "nicchia" ....quindi è una discussione solo
per parlare...nel 99% dei casi ci fidiamo dei nostri compilatori...in VB di
più !(anche perchè ci possiamo fare poco)
in C  intervenite un po di più sul vostro compilatore e sopratutto ne potete
provare molti....anche free....


 Saluti!
A te.
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 beh vedo il vostro lavoro un po' sprecato.
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Lokar
-- 
Sito Comune: 
http://www.it-lang-vb.net/
Manifesto: 
http://www.it-lang-vb.net/docs/Manifesto.txt
Statuto: 
http://www.it-lang-vb.net/docs/Statuto.txt
UGIdotNET - 
http://www.ugidotnet.org
 

 Lokar

> Lokar
p.s.
leggi la risposta che ti ho dato più in su sui compilatori...forse è li che
dovremmo discutere non su questo pseudo-flame....
p.p.s
se io e te ci incontramo a faccia IN IPOTESI quello che hai detto non mi
offende più di tanto....perchè casomai sorridi...hai modi affabili etc
etc...ossia "sento" quello che vuoi dire!
Scritto su uno schermo di pc....non so quello che "intendi dire"...e mi
limito a quello che "hai scritto"....
Se lo rileggo e lo rileggi tu a mente fredda quello che hai scritto diventa
"forse" un altra cosa rispetto a quello che intendevi dire
:
a) Ironia c'è ..eh se c'è!...addirittura.....io dico presa per le mele!
b) Presupponenza: della serie "Ah ah ah! Io uso C e son meglio di voi perchè
il mio codice è più performante"
c) Ottusità: non solo io ma anche altri ti han detto che forse il tuo post
poteva essere interpretabile male e te invece di essere obiettivo e dire "ok
mi son espresso male "...hai detto una cosa del tipo "Ah non mi
capite...uffa la tronco qui"
p.p.p.s
Quando ero giovane.....ci misi un mese per scrivere un bubble sort in RISC
Assembler per l'archimedes (tanto all'università ci si andava solo per le
tope no???)...il timing delle istruzioni non lo considerai perchè il 99% di
esse erano di un ciclo macchina (vantaggio del RISC...per l'intel dovrei
considerare questo aspetto invece)
Alla fine avevo il mio oggettino...intelletualmente bello...ma assolutamente
inutile (anche perchè quel PC lo avevamo in 10 in tutta Italia)!
Per dirti che anche il C non è il massimo della vita!
Chi vuol capire ....intenda...! eh eh eh :-) rotfl!
Saluti
(con la i finale)
Smile you are on trolling camera!
:-)
La finisco anche io vah!
-- 
Il Wodkino Nazionale è a : 
www.martek.it
Pagina Vb/Bestiario/Lamer Experience :
http://www.martek.it/go.asp?portamia=2
 New Entry nel
bestiario! :-)
---
Messaggio scannerizzato e certificato "Virus free" da AVG free edition.
Checked by AVG anti-virus system (
http://www.grisoft.com
).
Version: 6.0.770 / Virus Database: 517 - Release Date: 27/09/2004

Wodka40° ha scritto:
[...]
Su... fate i bravi :)
Riassumo le mie motivazioni sulla scelta del linguaggio:
-Volevo distribuire un programma funzionante da pochi KB senza alcuna
dipendenza/file esterni/installazione (eccetto il runtime di VB, opzionale
per chi non l'ha già): il Btree mi serviva per evitare di distribuire
ADO/DAO/quant'altro.
-Ho scelto Btree perchè è usato da diversi motori di DB, per cui ero certo
delle prestazioni. Le prestazioni si misurano in complessità
computazionale che è indipendente dal linguaggio utilizzato. La differenza
tra un linguaggio e l'altro a parità di algoritmo, è costante. Quindi
bisogna capire quanto questa costante sia importante ai propri scopi.
-Non volevo scrivere l'implementazione più veloce possibile, ma quella
abbastanza veloce da far lavorare il programma principale (il Btree non
era fine a se stesso). Si tenga conto che l'inserimento delle chiavi non
sarà fatto tutto una volta, ma distribuito, nell'arco di anni, in chiamate
da qualche centinaio di chiavi: in pratica non ci sarà alcun tempo di
attesa percettibile da parte dell'utente. Ed è questo che conta.
-Quando ho in mente una cosa sento di volerla finire subito, per cui
avventurandomi nel C (che uso pochissimo) avrei perso più tempo di quanto
ne avrebbero risparmiato gli utilizzatori del programma tutti insieme :)
-In ufficio non ho Visual C
-Se l'avessi scritto in C, non l'avrei postato qui :) 
Infine non sono d'accordo sul fatto che un algoritmo buono/complesso debba
essere implementato in un linguaggio particolare: al contrario penso che
non bisogna usare algoritmi scarsi in nessun linguaggio.


 (con la i finale)
Eh beh a te piace l'italiano :)