[C] Dubbio sulle prestazioni

[misterx]

sto valutando che tipo di struttura dati usare per un progetto di lavoro ed avendo implementato pee l'esame di algoritmi un albero red-black, ho rispolverato il codice.

Ora ho popolato l'albero con 800000 strutture che contengono: percorso, data, orario, dimensioni, nome del file.

Visitando l'abero in ordine facendo stampare i file per anno e tipo esempio:

2008, *.jpg *.txt (fino a 90 tipi diversi di file)

ottengo prestazioni di tutto rispetto, nell'ordine di 5/8 secondi.

Per curiosità ho provato ad usare la findstr della shell di windows per vedere la differenza in termini prestazionali: non capisco l'enorme divario che osservo.

La findstr dovrebbe stampare tutte le stringhe corrispondenti all'anno 2008 con estenzione .jpg ma impiega svariati minuti: che motivo potrebbe esserci?

[ESSE-EFFE]

Originariamente inviato da misterx

La findstr dovrebbe stampare tutte le stringhe corrispondenti all'anno 2008 con estenzione .jpg ma impiega svariati minuti: che motivo potrebbe esserci?

A me pare che la findstr faccia qualcosa di sostanzialmente diverso, quindi è del tutto normale avere una tempistica diversa, però dovresti chiarire cosa intendi con "visitando l'albero".

[banryu79]

Originariamente inviato da ESSE-EFFE

A me pare che la findstr faccia qualcosa di sostanzialmente diverso, quindi è del tutto normale avere una tempistica diversa, però dovresti chiarire cosa intendi con "visitando l'albero".

Non è che la findstr esegue una ricerca anche rispetto al contenuto dei file? Che sia per quello?

[WarDuck]

findstr si comporta come grep, quindi cerca token all'interno del file e stampa le righe che contengono quel token.

Quindi direi che stiamo confrontando mele con pere.

[misterx]

Originariamente inviato da ESSE-EFFE

A me pare che la findstr faccia qualcosa di sostanzialmente diverso, quindi è del tutto normale avere una tempistica diversa, però dovresti chiarire cosa intendi con "visitando l'albero".

l'ho scritto sopra, la visita avviene in-order partendo quindi dalla radice.
Essendo il tempo di ricerca negli alberi RB O(log n) già questo potrebbe giustificare in un certo senso le prestazioni ma non credo che sia tutto legato alla particolare struttura.

Ho usato la findstr perchè ho pensato che agisse in modo sequenziale cioè, fa passare tutte le stringhe per trovare ciò che si sta cercando.
Un esperimento analogo è stato fatto con visual basic ottenendo tempi motlo superiori.

Tornando all'albero, siccome nella ricerca in-order io ho già piazzato nei membri delle 800000 strutture i dati già divisi, una delle ragioni delle prestazioni maggiori a favore dell'albero non risiede nella struttura dell'albero stesso ma da fatto che confronto in un certo senso dati già "filtrati" e cioè, che non devo tokenizzare.

Mi chiedo allora se invece di usare una albero RB usassi 5 array, otterrei le medesime prestazioni effettuando una ricerca di tipo sequenziale senza riordinare i dati in alcun modo?

p.s.
i dati nell'albero venogo ordinati in base ad una chiave numerica non usata durante le ricerceh quindi, è un po come se i dati fossero messi a caso nei nodi dell'albero, cioè, non ho usato alcuna logica ma li inserisco così come si trovano del file che leggo come input.

[ESSE-EFFE]

Originariamente inviato da misterx

l'ho scritto sopra, la visita avviene in-order partendo quindi dalla radice.

Hai scritto come, ma non cosa. Devi paragonare cosa fa il tuo programma (quali operazioni) mentre scorri l'albero e cosa fa la findstr. E verosimilmente sono cose diverse, quindi una tempistica diversa è naturale, non ha neanche senso confrontarle.

[misterx]

il senso c'è eccome.
Sto paragonando due differenti sistemi ed in base alle prestazioni decido se ha senso usare un albero RB per lo scopo che mi sono prefissato.

Durante la visita dell'albero cerco dati che se soddisfano i criteri di ricerca imposti vengono stampati.

Lo stesso dicasi per la findstr.

Ora ho sostituito all'albero RB 5 array di puntatori e di primo acchitoi tempi di ricerca che ottengo sono i medesimi.

Di certo non sto usando l'albero RB nel modo per lo scopo per cui è stato creato. Il tema centrale di questo thread è appunto quello di capire se sto usando tale struttura nel modo corretto: a quanto sembra direi di no.

[ESSE-EFFE]

Originariamente inviato da misterx

Durante la visita dell'albero cerco dati che se soddisfano i criteri di ricerca imposti vengono stampati.
Lo stesso dicasi per la findstr.

Direi di no.

Originariamente inviato da misterx

il senso c'è eccome.
Sto paragonando due differenti sistemi ed in base alle prestazioni decido se ha senso usare un albero RB per lo scopo che mi sono prefissato.

Non stai paragonando sistemi diversi, ma programmi diversi. L'hanno ribadito anche altri due utenti, ai quali lascio la parola. Io ci rinuncio.

[misterx]

Originariamente inviato da ESSE-EFFE

Io ci rinuncio.

Poi ho scritto che ora ho implementato il medesimo MIO programma, bada bene, non il comando findstr, attraverso array ottenendo i medesimi risultati. A quanto pare ho tenuto conto di quanto dicevano gli altri utenti.

Ma se non sei interessato pazienza

[misterx]

Originariamente inviato da WarDuck

findstr si comporta come grep, quindi cerca token all'interno del file e stampa le righe che contengono quel token.

Quindi direi che stiamo confrontando mele con pere.

ed invece ho usato la findstr in quanto di primo acchito sembrava piuttosto efficiente e poi non avevo ancora scritto il medesimo programma

a) usando un albero rosso nero
b) usando 5 array

Facendo dei test e scoprendo l'acqua calda se l'albero viene persorso tutto è **** equivalente ai tempi di ricerca di un array.

A questo punto mi chiedo in quali casi un albero RB offre le sue massime prestazioni?

Forse nella ricerca di un singolo elemento a patto che l'albero venga strutturato in modo particolare?


**** rettifica
NON è assolutamente equivalente. facendo una ricerca per tipo di 800000 file e sommandone le dimensioni ottengo:
ALBERO RB = 223 secondi (800000 x 90 tipi)
ARRAY = 60 secondi

[WarDuck]

Originariamente inviato da misterx

ed invece ho usato la findstr in quanto di primo acchito sembrava piuttosto efficiente e poi non avevo ancora scritto il medesimo programma

a) usando un albero rosso nero
b) usando 5 array

Facendo dei test e scoprendo l'acqua calda se l'albero viene persorso tutto è **** equivalente ai tempi di ricerca di un array.

A questo punto mi chiedo in quali casi un albero RB offre le sue massime prestazioni?

Forse nella ricerca di un singolo elemento a patto che l'albero venga strutturato in modo particolare?


**** rettifica
NON è assolutamente equivalente. facendo una ricerca per tipo di 800000 file e sommandone le dimensioni ottengo:
ALBERO RB = 223 secondi (800000 x 90 tipi)
ARRAY = 60 secondi

Partendo dalla teoria, che dovresti già conoscere:

Un albero red-black è un albero binario di ricerca auto-bilanciante.

E' una classica struttura a dizionario del tipo <key, value>.

L'albero è ottimizzato per ricercare le key, e questo viene fatto imponendo un ordinamento sulle key stesse (esempio: le key inferiori alla radice sono a sinistra, le key superiori o uguali a destra).

Un albero RB così fatto ti garantisce prestazioni nell'ordine O(log n) nella ricerca delle key.

Tutto sta nello scegliere le key giuste per il lavoro che vuoi svolgere (esempio: vuoi cercare i files per anno, la tua key sarà l'anno mentre il tuo value sarà una semplice lista di tutti i file corrispondenti a quell'anno).

Chiaramente se vuoi ottimizzare la ricerca per diverse key, hai bisogno di più alberi.

Gli alberi in generale sono utili quando hai bisogno di effettuare molti lookup su dati che, anche se raramente, potrebbero cambiare.

PS: findstr fa una ricerca grezza su file di testo, nel caso implementi algoritmi tipo il Boyer-Moore per il pattern matching hai nel caso medio O(n) (al peggio O(nm), dove m è la lunghezza del pattern di ricerca e n è la dimensione del testo.

Dunque ti invito a farci capire meglio cos'è che vuoi realizzare di preciso.

[clockover]

Magari mi sono perso qualcosa per strada leggendo un po di fretta ma ho dei dubbi su quello che hai fatto. Non conoscendo findstr sono andato a vedere qui --> http://www.microsoft.com/resources/d....mspx?mfr=true e a quanto pare, come già ha detto WarDuk, è analogo a grep, quindi ricerca del testo all'interno del file.
A quanto ho capito quello che fai tu invece è di popolare un albero red-black con dei dati relativi a dei files. Effettui una ricerca all'interno di questo albero... ma che tipo di ricerca, cosa cerchi effettivamente? Effettui operazioni di I/O sulla entry relativa al file trovato?
Tu fai controllare se all'interno del tuo albero un file soddisfa dei requisiti. Anche se l'albero è un BST una visita in-order visita sotto-albero sx e poi dx quindi ti controlla comunque tutto l'albero, quindi O(n), non O(logn) che è il tempo di ricerca di una chiave.

Fai un esempio pratico di quello che fai fare al tuo programma e di quello che fai fare a findstr.

[misterx]

Originariamente inviato da WarDuck

Dunque ti invito a farci capire meglio cos'è che vuoi realizzare di preciso.

allo stato attuale è solo un esperimento che mi serve per capire come usare gli alberi RB. Per questo ho popolato un albero con diverse strutture e la key che dici tu per me è un numero che si incrementa ad ogni inserimento.

Una volta popolato l'albero ho semplicemente richiamato la funzione inorder() la quale vista appunto l'albero in ordine.

Per fretta, ho paragonato la in-order con la findstr solo allo scopo di valutarnle le prestazioni, ance se sapevo che i due programmi agivano in modo differente.

Ora ho implementato il medesimo programma attraverso array e la stessa operazione di scansione di tutto l'array nei confronti dell'alber RB è 5 volte più rapida.

Questo risultato mi ha portato a dubitare che stessi usando l'albero RB per gli scopi per cui è stata inventata tale struttura. Rileggendo il mio libro leggo che la inorder ha prestazioni O(n) e non O( log n) come invece erroneamente pensavo.

La morale è che se mi interessa scansire completamente un albero RB a modi array allora l'albero RB non è la struttura adatta alle mie esigenze, questo in quanto non ho necessità di cancellazioni e/o nuovi inserimenti.

Comunque: bella esposizione

grazie

[WarDuck]

Lo scopo degli alberi binari è quello di velocizzare la ricerca dei dati rispetto ad una determinata chiave di ricerca (il nome del file oppure l'anno come supponevamo prima).

Dunque per avere dei vantaggi l'organizzazione dei nodi dell'albero dev'essere fatta sulla base della chiave di ricerca che intendi utilizzare.

La ricerca su strutture dati di questo tipo è O(log n), perché visiti solo ed esclusivamente i nodi che ti portano verso la soluzione.

E' chiaro che se devi navigare per intero l'albero e non ti interessa l'ordinamento, tantovale usare una lista, o meglio ancora un'array.