Newsgroup: it.comp.lang.c++
Titolo: strutture dati efficienti

ciao a tutti.
devo realizzare un progetto per l'università in cui dobbiamo trattare
diverse strutture dati in c++.
mi chiedevo se qualcuno di voi è a conoscenza di nuove strutture dati
efficienti da poter trattare (come "nuove" intendo che non siano i soliti
alberi b+, red-black, strutture hash, etc...).
qualunque aiuto è ben accetto, e naturalmente mi basta anche solo un link
dove andarmi a documentare :)
ho cercato un po' su google ma non ho trovato nulla di interessante o
comunque che non conoscessi già.
grazie in anticipo a tutti quelli che mi risponderanno!
gianpi

gianpi wrote:
[CUT]
volevo solo aggiungere che vanno benissimo (anzi sarebbero persino meglio)
strutture dati di cui magari non è stata ancora sviluppata nessuna libreria
in c++.
so che è difficile ma chiedere non costa nulla.
grazie e ciao
gianpi

 efficienti da poter trattare
Efficienti per cosa, scusa? Se ne esistesse una efficiente in generale 
le altre non avrebbe senso esistessero... ;)
-- 
Luc

 le altre non avrebbe senso esistessero... ;)
sě, effettivamente sono stato troppo generico :)
sostanzialmente il problema č questo: abbiamo un modulo c++ che prende una
n-upla di dati e la ricerca all'interno di una struttura dati che contenga
n-uple fatte nello stesso modo. Per il momento la struttura dati che
utilizziamo č un albero red-black. Il nostro compito sarebbe di valutare
l'utilizzo di altre 3-4 strutture dati e verificarne l'efficienza per una
ricerca di questo tipo, realizzando poi il modulo c++ adatto.
Spero di essere stato piů chiaro questa volta.
ciao
gianpi


wrote:

ho l'impressione che le uniche furbate che puoi fare sono:
a) Trovare una funzione hash particolarmente adatta.
b) Bilanciare la ricerca in base a come sono distribuite le n-uple.
(la mia č solo un'impressione)
Se lo spazio delle n-uple č piccolo potresti addirittura trovare una
funzione "hash" senza collisioni, e quindi mettere tutto in un
vettore. Non importa se viene enorme, tanto c'č la memoria virtuale
(hardware che ti aiuta)

 (la mia è solo un'impressione)
Questo infatti è quello che facciamo con l'albero red-black che
manteniamo bilanciato al momento dell'inserimento (dato che la creazione
della struttura viene fatta solo una volta in fase di inizializzazione).
gianpi

 accettabile.
Avete considerato il "trie"?
-- 
	Carlo Milanesi
 
http://digilander.libero.it/carlmila

della struttura viene fatta solo una volta in fase di inizializzazione).
sono andato a guardare negli header di Visual C++ .NET, e, come
sospettavo, gli alberi utilizzati sono proprio alberi red-black :-]
ciao
Walter

 Avete considerato il "trie"?
sinceramente non so nemmeno cosa sia :P
hai qualche link per documentarmi?
grazie!
gianpi


Cercando nel Web, ho trovato:
Un articolo sugli algoritmi di ricerca:
http://www.ece.iastate.edu/~aluru/bcb2002/String.pdf.pdf
Un articolo si trie con codice in Java:
http://www.hta-bi.bfh.ch/~ctr/archive/project1/DigitalSearchTrie2/description/DigTrie.html
Del codice in linguaggio C:
http://inconnu.isu.edu/~ink/new/projects/trie/trie.h
http://inconnu.isu.edu/~ink/new/projects/trie/trie.c


 
http://inconnu.isu.edu/~ink/new/projects/trie/trie.c
Mi sembra molto interessante :)
Grazie mille, consiglio utilissimo!
gianpi

...

Una struttura che sembra fare al caso vostro e' l'albero ternario:
http://www.cs.princeton.edu/~rs/strings/
Ciao,
Nicola

...

Umm, dal momento che l'accesso agli articoli non e' comodissimo ne do
una descrizione.
Ragionando sulle stringhe per comodita', nell'albero ternario ogni
nodo non contiene un'intera stringa, ma solo un carattere. I nodi a
sinistra e destra contengono i caratteri di valore minore o maggiore
che possono trovarsi nella posizione corrente, il nodo "sotto" (il
terzo ramo) porta al sottoalbero che descrive la posizione successiva.
Si capisce piu' chiaramente con un'esempio: nell'albero ternario qui
sotto sono rappresentate le parole 'cane', 'cala', 'casa' e 'cena':
                           c
                           |
                           a---+
                           |   e
                           |   |
                         +-n-+ n
                         l | s |
                         | | | |
                         a e a a
Ciao,
Nicola