Newsgroup: it.comp.lang.c
Titolo: Ricerca-binaria vs Alberi

In teoria, è più veloce, la ricerca binaria iterativa
su una tabella di stringhe già ordinate (in ordine alfabetico)
oppure la ricerca su un bi-albero bilanciato (tipo BTREE) ??
In entrambi i casi, la funzione di ricerca sarebbe un algoritmo (in C)
che opera in memoria ram e
sullo stesso numero di stringhe alfanumeriche, niente uso del disco,
tranne per il caricamento della tabella.
In pratica mi servirebbe sapere, in questo contesto, qual'è l'agoritmo
più veloce per la ricerca di una stringa.
Non ho ancora fatto delle prove e sarebbe molto difficile per me, farle,
volevo chiedere un vostro parere prima di iniziare,
anche perchè, guardando in giro, il codice scritto in C per la gestione
di
un bi-albero bilanciato (btree) sembra molto complicato da scrivere,
almeno per me.
se questo messaggio fosse OT , potete dirmi su quale NG devo postare??
:-)
grazie
Ciao
Dave

Con i computer odierni, la velocità è diventata l'ultima preoccupazione.
Entrambe le ricerche, quella binaria e quella ad albero, sono velocissime ed
è minima la differenza di velocità tra le due.
Io opterei per quella binaria senza l'uso degli alberi, anche perchè
quest'ultima è molto più complessa da applicare e francamente non ricordo
più bene come funziona ;-)
Per aiuto contattami
--------------------------------
Inviato via 
http://usenet.libero.it

 ha scritto nel messaggio
news:0ZfRa.180551$lK4.5...@twister1.libero.it...

La ricerca sui B-Tree si usa ad esempio nelle implementazioni dei DBMS per
minimizzare il numero di pagine caricate dal disco (visto che gli accessi ai
dischi sono le operazioni che occupano piu' tempo).
Visto che lavori solo in memoria, credo che convenga sviluppare una ricerca
binaria:
e' piu' semplice da implementare sia la ricerca che la gestione degli
alberi!
Ciao,
Ema

 Con i computer odierni, la velocità è diventata l'ultima
preoccupazione.
Nei casi 'normali' questo è vero, ma cmq dipende sempre da cosa deve
fare il programma.
Ad esempio tu prova ad eseguire la funzione di Fibonacci ricorsiva
e vedrai che ti rallenta anche il computer più potente al mondo..
Anche gli algoritmi sulla crittografia rallentano qualsiasi computer,
inoltre, molti programmi non si possono ancora usare in modo
soddisfacente
perchè i computer sono troppo lenti, ad es. le simulazioni real-time.
La potenza dei computer non è mai abbastanza per me. ;-)
Probabilmente tra 50 anni non sarà più un problema.
Ciao
Dave

> Probabilmente tra 50 anni non sarà più un problema.
Fra 50 anni probabilmente si vorranno fare e si faranno cose che ora i
computer non possono permettersi di fare e.... fra 50 quelle cose metteranno
a dura prova i computer e.... i produttori di computer continueranno a fare
computer semrpe piu' veloci. (anche se forse la velocita' non la si
aumentera' piu' con i GHz ;-)
Tommy

D'accordo hai ragione, ma qusti esempi che hai fatto tu...sono RARISSIMI!!
Tu normalmente sviluppi applicazioni Real-Time?
non penso proprio.
O crei applicazioni per decrittare codici come il DES o l'RSA?!
non penso proprio.
Qui parliamo del 95% di codice che viene utilizzato e creato nel mondo, cioè
programmi di database per lo più, e non penso che sia rilevante la velocità!
Ciao


 aumentera' piu' con i GHz ;-)
E' proprio questo il punto, se non ci sono imprevisti climatici... ;-)
fra 50 anni si parlerà forse di THz (Tera-Hertz) , ovvero computer mille
volte più veloci di quelli di oggi.
Sono assolutamente convinto, che, fra 50 anni, le persone addette ai
lavori non programmeranno i "computer"
come facciamo oggi, ci penseranno i computer, a programmarsi da soli,
nella maggioranza dei casi.
In una società totalmente interconnessa, il calcolo (parallelo)
distribuito sarà la norma e
quindi problemi di ottimizzazione in C non ne vedo proprio.. ;-)
Immaginate dei PC con una potenza di qualche THz, interconnessi in rete
ad alta velocità con altri PC,
io vedo una potenza mostruosa, ma veramente mostruosa, per non parlare
della nanotecnologia!
(10^3) Kilo Mega Giga Tera Peta Exa Zetta Yotta Xona Weka Vunda Uda
Treda (10^39)
scusate l'OT.
ciao
Dave

 programmi di database per lo più, e non penso che sia rilevante la
velocità!
è vero, infatti nel caso dei database, una volta, su un grosso server
dbms con centinaia di utenti, ho visto
un monitoraggio della cpu in uso, ed era solo del 3-4 % !!
ciao
Dave


grazie del consiglio, ciao.
Dave

 quindi problemi di ottimizzazione in C non ne vedo proprio.. ;-)
Secondo me ci saranno sempre! Non con il C in se (si programmera' ancora in
C?) ma con gli algoritmi!
Ciao,
Tommy

Dave wrote:
Qui si stava parlando di 2 cose quasi identiche in complessita', con minime
differenze trascurabili. La differenza diventa apprezzabile quando hai
grandi moli di dati, nel qual caso i b-alberi vanno meglio perche' fanno
meno accessi al disco.
Comunque per quanto possa aumentare la potenza dei calcolatori, COMUNQUE
alcuni algoritmi danno risultati in secondi, altri in anni.
Ovviamente solo parlando di percezione umana... se il risultato
dell'algoritmo dovra' essere dato in pasto ad un calcolatore, allora la
differenza di prestazioni, che un umano potrebbe non notare con il suo
computer del futuro, rimarra' apprezzabile come lo e' ora.
-- 
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."