Newsgroup: it.comp.lang.c++
Titolo: organizzazione lista lineare , albero

Salve a tutti,
un parere su un tipo d'organizzazione di dati,
albero binario,
albero b-tree,
struca struca sono liste lineari con un'organizzazione astratta decisa
dalla struttura del tipo,
stavo cercando di realizzare un'albero b-tree ma sto optando per un
lista lineare che ottiene la stessa o leggermente inferiore velocità
nell'esplorazione dei dati, ma con risparmio di memoria visto che
l'organizzazione del tipo non è necessaria, mi spiego meglio,
quando costruiamo un albero b-tree abbiamo dei nodi e delle foglie,
le foglie sono i dati, vale a dire la lista lineare,
i nodi sono l'astrazione del tipo che permette di esplorare il tipo
d'organizzazione dei dati, vale a dire, la distanza che noi adoperiamo
per interrogare i diversi elementi dei dati,
quest'ultima dimostra che i nodi sono spazio di memoria che
utilizziamo per tracciare un percorso, spazio che ci costa in ram o
hd, questo avrebbe senso se i nodi avessero delle informazioni da
conservare, come una proprietà di visibilità o meno, ma non
necessitando di ciò,
utilizziamo una lista lineare che permette un'esplorazione simile al
tipo Q-sort, che mi sembra sia l'organizzazione utilizzata dal b-tree,
risparmiando memoria con l'uguale o quasi velocità del b-tree,
secondo voi è sbagliato?
grazie anticipatamente.

 grazie anticipatamente.
Scusa, ma hai riletto il messaggio prima di mandarlo ?
Non e' che proprio ti sei sforzato di essere chiaro... :-)
La scelta della struttura dati dipende almeno da
1) una stima di quanti elementi dovra' contenere (e di quanto e' 
"grande" un elemento)
2) quali operazioni (tipo inserimento/ricerca/cancellazione...) devi
fare sulla struttura e quali di queste sono critiche in termini
di tempo.
Nel tuo caso i punti 1 e 2 come sono messi ?
Non capisco cosa intendi dicendo che la "lista lineare permette
una esplorazione tipo Q-sort".
La lista lineare di solito consiste di un insieme di record
che contengono il dato e un puntatore al record successivo e a
quello precedente (doppia lista) o solo a quello successivo.
Anche se la lista fosse ordinata, la ricerca di un elemento
non potrebbe comunque giovarsene, perche' nella lista
mi posso spostare solo da un record ai 2 adiacenti,
mentre una ricerca basata sull'ordinamento ha di solito
bisogno di poter accedere ai dati in modo non consecutivo.
Se invece della lista usassi un vettore dinamico mantenuto ordinato,
allora la ricerca sarebbe veloce, ma l'inserzione o la cancellazione
no.  (Se poi per lista lineare tu intendi qualcosa di diverso
dallo standard, allora spiega!)
In generale, che una lista lineare possa avere una velocita'
uguale o quasi a quella di un b-tree e' una pia illusione,
se il numero di elementi e' abbastanza elevato e devi
fare molte operazioni di reperimento.
Tieni presente che per fare una ricerca di
un valore in una lista devi scandirla fino a trovare l'elemento
che ti interessa, quindi il costo e' grosso modo lineare nel
numero degli elementi, mentre il costo di un find in un albero
e' circa proporzionale al logaritmo del numero degli elementi.
Se hai una decina o un centinaio di record allora probabilmente
i costi si equivalgono (o puo' anche essere piu' veloce la lista),
ma se hai migliaia o milioni di record allora non c'e' paragone.
Comunque gli alberi b-tree non te li devi implementare da solo,
sono (solitamente) gia' inclusi in alcune strutture dati messe
a disposizione dal c++ (una volta nella STL, non so se adesso sono
proprio nel linguaggio) tipo map, set e compagnia,
ciao,
g.

 proprio nel linguaggio) tipo map, set e compagnia,
penso tu l'abbia detto per consigliarmi ma scrivo codice per rendermi
conto della difficoltà del funzionamento,
poi vengono i dubbi e chiedo a persone che hanno già incontrato
l'argomento per chiarirmi le idee,
mi sembra ridicolo pensare il contrario, considera sempre che per me è
un hobby,
chiedersi perchè l'uomo va nello spazio a capire ciò che c'è già...
non credo sia inutile ciò che fa ;)
buona giornata

 avendo diversi punti da controllare... ti ringrazio in anticipo ;)
Secondo me non e' corretto. Intanto mi sembra dal codice sotto
che tu confonda i concetti di lista e di array o vettore.
Mi sembra che tu stia tentatando di implementare una semplice
ricerca binaria in un array. Il problema e' che poi se devi inserire
un elemento in mezzo devi scorrere in giu' tutti gli elementi che 
seguono, uno alla volta. Se hai un milione di elementi questo porta via
del tempo e farlo fare ad un thread separato non porta nessun guadagno,
visto che fino a che non hai completato lo spostamento l'array si
trova in uno stato che non permette di effettuare con sicurezza altre
operazioni.
 > penso tu l'abbia detto per consigliarmi ma scrivo codice per rendermi
 > conto della difficoltà del funzionamento,
 > poi vengono i dubbi e chiedo a persone che hanno già incontrato
 > l'argomento per chiarirmi le idee,
Che tu lo faccia per hobby o meno, ti consiglio il libro
Cormen, Leiserson, Rivest : "Introduzione agli algoritmi"
ci sono un sacco di cose su strutture dati e algoritmi.
Sperimentare e provare va bene, ma farsi guidare dagli esperti
secondo me fa risparmiare un sacco di tempo.
ciao,
g.

// il codice esprime solo concettualmente la metodologia del B-tree
CString **lista;
DWORD nDimensioneLista;
int ordine= 4;
DWORD CLista::Cerca(CString TStringa)
{
 DWORD tPos= TStringa,nDimensioneLista/ordine,nDimensioneLista/ordine);
 return !lista[tPos]->Compare(TString) ? tPos : -1;
}
DWORD CLista::Cerca(CString &TStringa, DWORD TPos, DWORD TScostamento)
{
 if( TScostamento ){
  if( !lista[TPos]->Compare(TStringa) ){
   return TPos;
  }
  else if( lista[TPos]->Compare(TStringa) < 1 ){
    // stringa inferiore
   if( lista[ TPos+TScostamento ]->Compare(TStringa) < 1 ){
    return Cerca(TStringa, TPos+TScostamento, TScostamento);
   }		
   return Cerca(TStringa, TPos+TScostamento, TScostamento/ordine);
  }
  else{
    // stringa superiore
   if( lista[ TPos-TScostamento ]->Compare(TStringa) > 1 ){
    return Cerca(TStringa, TPos-TScostamento, TScostamento);
   }
   return Cerca(TStringa, TPos-TScostamento, TScostamento/ordine);
  }
 }
 return TPos;
}
Sintetizzando,
Un vettore dinamico ordinato può esplorare i suoi elementi come un
B-tree perchè può utilizzare la stessa metodologia,
un B-tree di ordine 4 una volta creato può cambiare la sua
organizzazione ricreando se stesso es: da ordine 4 a 8,
un vettore può farlo cambiando una sola variabile 'ordine' perchè non
esiste struttura da mantenere, la memoria utilizzata è dedicata
esclusivamente ai dati.
Una vettore ordinato è inferiore al B-tree come velocità
d'aggiornamento dovuto all'inserimento ed eliminazione di ogni
elemento,
mi sembra aver riassunto correttamente il contenuto dei post
scritti...
ovviamente ho evidenziato soltanto i punti che volevo esporre in
maniera che anche altri avessero modo di pensarci un po' su,
un B-tree è un'organizzazione che non si può sostituire con una
semplice lista, questo è palese.