|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-18 16:45:32
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv28906 Modified Files: relazione.dvi relazione.pdf relazione.tex Added Files: ins_casuale.eps ins_casuale.png ins_crescente.eps ins_crescente.png Log Message: --- NEW FILE: ins_crescente.eps --- %!PS-Adobe-3.0 EPSF-3.0 %%Creator: (ImageMagick) %%Title: (ins_crescente.eps) %%CreationDate: (Sat Sep 18 18:36:08 2004) %%BoundingBox: 0 0 1016 716 %%HiResBoundingBox: 0 0 1016 716 %%DocumentData: Clean7Bit %%LanguageLevel: 1 %%Pages: 1 %%EndComments %%BeginDefaults %%EndDefaults %%BeginProlog % % Display a color image. The image is displayed in color on % Postscript viewers or printers that support color, otherwise % it is displayed as grayscale. [...60861 lines suppressed...] DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDC end %%PageTrailer %%Trailer %%EOF --- NEW FILE: ins_crescente.png --- (This appears to be a binary file; contents omitted.) Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.11 retrieving revision 1.12 diff -C2 -d -r1.11 -r1.12 *** relazione.tex 17 Sep 2004 12:29:45 -0000 1.11 --- relazione.tex 18 Sep 2004 16:45:19 -0000 1.12 *************** *** 1,3 **** ! \documentclass[12pt]{report} \usepackage{enumerate} --- 1,3 ---- ! \documentclass[12pt,fullpage]{report} \usepackage{enumerate} *************** *** 246,261 **** \chapter{Conclusioni}\label{Conclusioni} Nei test effettuati, ripetendo numerose volte la costruzione di alberi AVL e BST, e poi applicandovi numerose modifiche casuali di tipo inserimento e cancellazione si è notato come la differenza tra le due implementazioni sia davvero minima e poco percettibile. Se si considera la differenza di costi (uno lineare, l'altro logaritmico) questo risultato appare impossibile. In realtà il risultato è giustificabile con diversi punti: \begin{itemize} ! \item il generatore di numeri casuali, in realtà non è puramente casuale. E' un limite di quasi tutti i sistemi operativi e processori attuali ! \item la misurazione delle prestazione non è accurata, il programma realizzato è soggetto a scheduler e quindi non è garantito che il sistema operativo assegni al programma le stesse risorse in ogni momento ! \item la quantità di numeri generata e la loro grandezza non è in grado si mettere in seria difficoltà i processori attuali e le differenze di tempo sono minime ! \item non è sicuro che l'implementazione proposta sia la più performante in entrambi i casi. L'uso di strutture dati differenti, compilatori e ottimizzazioni specifiche per architetture e sistemi operativi potrebbe in qualche modo sbilanciare a favore di una implementazione l'esito dei test. ! \item la misurazione del tempo impiegato è effettuata tramite chiamate alla funzione "clock()" e il calcolo della differenza tra i due istanti di misurazione. L'accuratezza della differenza non è quindi assicurata. \item Nel test comparativo si usano numeri estratti casualmente, ma non gli stessi per entrambi gli alberi. \end{itemize} Alla luce del lavoro effettuato si possono trarre le seguenti conclusioni: ! gli alberi AVL, teoricamente molto più veloci dei semplici BST nelle tre operazioni fondamentali di ricerca, cancellazione e inserimento, nella pratica sono risultati leggermente performanti (e talvolta anche più lenti!) ma con prestazioni al di sotto dell'aspettiva, fermo restando che dei test più accurati, quantità di input maggiori e specificatamente disegnati per gli AVL possano smentire i risultati ottenuti. ! Va sempre considerato anche l'aspetto delle costanti: utilizzando dei set di numeri non immensi, un costo logaritmico, ma con una costante moltiplicativa grande può risultare superiore ad un costo lineare. ! Considerando che nell'implementazione proposta gli alberi AVL derivano dagli alberi BST è possibile che ci sia un overhead dovuto proprio all'esecuzione di questo codice. \end{document} --- 246,402 ---- \chapter{Conclusioni}\label{Conclusioni} Nei test effettuati, ripetendo numerose volte la costruzione di alberi AVL e BST, e poi applicandovi numerose modifiche casuali di tipo inserimento e cancellazione si è notato come la differenza tra le due implementazioni sia davvero minima e poco percettibile. Se si considera la differenza di costi (uno lineare, l'altro logaritmico) questo risultato appare impossibile. + In realtà il risultato è giustificabile con diversi punti: \begin{itemize} ! \item La misurazione delle prestazione non è accurata, il programma realizzato è soggetto a scheduler e quindi non è garantito che il sistema operativo assegni al programma le stesse risorse in ogni momento. ! \item La quantità di numeri generata e la loro grandezza non è in grado si mettere in seria difficoltà i processori attuali e le differenze di tempo sono minime. ! \item L'uso di strutture dati differenti (per l'implementazione con AVL rispetto a quella con BST), compilatori e ottimizzazioni specifiche per architetture e sistemi operativi potrebbe in qualche modo sbilanciare a favore di una implementazione l'esito dei test. ! \item La misurazione del tempo impiegato è effettuata tramite chiamate alla funzione "clock()" e il calcolo della differenza tra i due istanti di misurazione. L'accuratezza della differenza non è quindi assicurata. \item Nel test comparativo si usano numeri estratti casualmente, ma non gli stessi per entrambi gli alberi. + \item Come verr\`a detto pi\`u avanti un albero BST generato con sequenze casuali di valori e sottoposto ad operazioni casuali di inserimento e cancellazione avr\`a mediamente l'aspetto di un albero bilanciato pur non rispettando questa definizione. \end{itemize} + Alla luce del lavoro effettuato si possono trarre le seguenti conclusioni: ! gli alberi AVL, teoricamente molto più veloci dei semplici BST nelle tre operazioni fondamentali di ricerca, cancellazione e inserimento, nella pratica sono risultati leggermente pi\`u performanti (e talvolta anche più lenti!). ! ! Va sempre considerato anche l'aspetto delle costanti: utilizzando sequenze di input di dimensioni non eccessivamente elevate, un costo logaritmico, ma con una costante moltiplicativa grande può risultare superiore ad un costo lineare. ! ! Nei paragrafi seguenti sono riportati e commentati i valori dei tempi di esecuzione espressi in funzione della dimensione dell'input (che nel seguito verr\`a indicata con $n$). Si noter\`a che, per quanto detto sopra, nei casi medi non ci saranno sostanziali differenze tra le due implementazioni. Se invece si forza il software a lavorare in condizioni particolari si notano i vantaggi di utilizzare un algoritmo pi\`u efficiente a scapito delle considerazioni precedenti. ! ! \section{Macchina utilizzata} ! ! Nell'analizzare i tempi di esecuzione riportati nei paragrafi seguenti è opportuno considerare che essi sono stati ottenuti eseguendo il software sempre sulla stessa macchina ed in condizioni il pi\`u possibile prossime a quelle ideali. ! ! Si \`e cercato cio\`e di tenere in esecuzione solo i processi necessari per l'esecuzione dell'applicativo di test in modo da disporre di un maggior quantitativo di memoria e di non essere soggetti a scheduling da parte del sistema operativo. ! ! La macchina utilizzata \`e cos\`i configurata: ! \begin{itemize} ! \item CPU: AMD Athlon 600 MHz ! \item RAM: 256 Mb 100MHz CL2 ! \item Sistema operativo: Linux v2.6.9-rc2 ! \end{itemize} ! ! \section{Inserimento di una sequenza di valori casuali} ! ! L'inserimento di una sequenza di valori casuali \`e il caso che pi\`u si avvicina a quello medio. In questo caso infatti i valori della sequenza vengono scelti casualmente tra quelli di un insieme finito di cardinalit\`a $k$ in modo che la probabilit\`a che venga utilizzata una tra le possibili permutazioni degli elementi di tale insieme sia costante e pari a $\frac{1}{k!}$ il che equivale a dire che ogni sequenza di input \`e equiprobabile. ! ! Dal grafico si nota che le curve crescono linearmente con il crescere della dimensione dell'input. Il risultato di certo non stupisce per quanto riguarda gli alberi BST. L'andamento della curva relativa agli AVL \`e dovuto al fatto che, anche se l'operazione predominante nell'inserimento \`e quella di ricerca, ci sono altre operazioni che influiscono in maniera minima (con costo cio\`e di $O\left(1\right)$ ) ma significativa sul costo totale. Tali operazioni sono quelle di rotazione e di aggiornamento del fattore di bilanciamento in ogni nodo. ! ! \`E interessante notare che la curva relativa agli AVL, oltre che avere un andamento simile a quella relativa ai BST, rispetto a quest'ultima presenta anche una pendenza maggiore, il che significa che il tempo di esecuzone, al crescere della dimensione dell'input, cresce pi\`u velocemente nell'implementazione con AVL piuttosto che in quella con i BST. ! ! Questo risultato \`e giustificato dal fatto che un albero di ricerca costruito utilizzando l'implementazione BST inserendo una sequenza casuale di valori ha un'altezza media $h$ pari ad $h=O\left(lg\left(n\right)\right)$ (.........................) uguale cio\`e all'altezza di un albero costruito utilizzando l'implementazione AVL (con la differenza che questo presenta tale valore di altezza per tutte le sequenze di input). L'albero BST ha inoltre il vantaggio di non dover eseguire le operazioni di rotazione e aggiornamento del fattore di bilanciamento. ! \begin{center} ! \includegraphics[width=420pt]{ins_casuale} ! \end{center} ! \newpage ! \begin{center} ! \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} ! \hline ! \textbf{Dimensione dell'input}&\textbf{Tempo Avl (s)}&\textbf{Tempo Bst (s)}\\ ! \hline ! 10000&0.050000&0.020000\\ ! 20000&0.110000&0.040000\\ ! 30000&0.190000&0.070000\\ ! 40000&0.260000&0.080000\\ ! 50000&0.350000&0.110000\\ ! 60000&0.420000&0.130000\\ ! 70000&0.520000&0.170000\\ ! 80000&0.630000&0.210000\\ ! 90000&0.710000&0.240000\\ ! 100000&0.780000&0.290000\\ ! 110000&0.890000&0.280000\\ ! 120000&1.010000&0.320000\\ ! 130000&1.110000&0.360000\\ ! 140000&1.200000&0.420000\\ ! 150000&1.280000&0.440000\\ ! 160000&1.390000&0.470000\\ ! 170000&1.500000&0.560000\\ ! 180000&1.620000&0.560000\\ ! 190000&1.720000&0.610000\\ ! 200000&1.850000&0.650000\\ ! 210000&1.920000&0.670000\\ ! 220000&2.040000&0.690000\\ ! 230000&2.140000&0.760000\\ ! 240000&2.280000&0.790000\\ ! 250000&2.430000&0.890000\\ ! 260000&2.500000&0.900000\\ ! 270000&2.630000&0.950000\\ ! 280000&2.750000&0.990000\\ ! \hline ! \end{tabular} ! \end{center} ! \begin{center} ! \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} ! \hline ! \textbf{Dimensione dell'input}&\textbf{Tempo Avl (s)}&\textbf{Tempo Bst (s)}\\ ! \hline ! 290000&2.910000&1.090000\\ ! 300000&3.030000&1.170000\\ ! 310000&3.260000&1.120000\\ ! 320000&3.290000&1.210000\\ ! 330000&3.410000&1.270000\\ ! 340000&3.480000&1.330000\\ ! 350000&3.610000&1.350000\\ ! 360000&3.730000&1.410000\\ ! 370000&4.020000&1.380000\\ ! 380000&3.940000&1.450000\\ ! 390000&4.200000&1.590000\\ ! 400000&4.220000&1.610000\\ ! 410000&4.370000&1.700000\\ ! 420000&4.480000&1.700000\\ ! 430000&4.670000&1.800000\\ ! 440000&4.830000&1.770000\\ ! 450000&4.990000&1.870000\\ ! 460000&5.020000&1.880000\\ ! 470000&5.150000&1.950000\\ ! 480000&5.370000&2.050000\\ ! 490000&5.310000&2.120000\\ ! \hline ! \end{tabular} ! \end{center} ! ! ! \section{Inserimento di una sequenza di valori crescenti} ! ! L'inserimento di una sequenza di valori sempre crescenti in un albero binario rappresenta il caso peggiore (insieme a quello di inserimento di valori sempre decrescenti) se si sta utilizzando un'implementazione semplice BST ma non influisce in modo significativo nel caso in cui si utilizzi un'implementazione AVL. In questo caso, infatti, un albero BST degenera in una lista nella quale l'inseriemnto di un nuovo valore viene fatto sempre in coda e che quindi presenta un costo di inserimento pari a $O\left(n\right)$ ! ! Il grafico avvalora quanto detto. Infatti la curva relativa agli AVL si presenta con un andamento grossomodo costante, ovvero logaritmico mentre quella relativa ai BST cresce in maniera lineare con una pendenza molto elevata facendo in modo che la prima curva sia sempre minore della seconda anche per dimensioni di input non troppo elevate. ! ! \begin{center} ! \includegraphics[width=420pt]{ins_crescente} ! \end{center} ! \newpage ! \begin{center} ! \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} ! \hline ! \textbf{Dimensione dell'input}&\textbf{Tempo Avl (s)}&\textbf{Tempo Bst (s)}\\ ! \hline ! 500&0.000000&0.010000\\ ! 1000&0.000000&0.020000\\ ! 1500&0.010000&0.030000\\ ! 2000&0.010000&0.060000\\ ! 2500&0.020000&0.130000\\ ! 3000&0.010000&0.160000\\ ! 3500&0.010000&0.260000\\ ! 4000&0.020000&0.280000\\ ! 4500&0.020000&0.340000\\ ! 5000&0.020000&0.420000\\ ! 5500&0.030000&0.520000\\ ! 6000&0.030000&0.640000\\ ! 6500&0.030000&0.730000\\ ! 7000&0.030000&0.940000\\ ! 7500&0.040000&1.130000\\ ! 8000&0.040000&1.210000\\ ! 8500&0.040000&1.420000\\ ! 9000&0.040000&1.620000\\ ! 9500&0.050000&1.810000\\ ! \hline ! \end{tabular} ! \end{center} ! ! ! \section{Inserimento di una sequenza di valori casuali} ! ! \section{Inserimento di una sequenza di valori decrescenti} ! \end{document} Index: relazione.pdf =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.pdf,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 Binary files /tmp/cvsA2MeHE and /tmp/cvsSWFM4r differ Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 Binary files /tmp/cvsIHYkCP and /tmp/cvs5lsB5C differ --- NEW FILE: ins_casuale.png --- (This appears to be a binary file; contents omitted.) --- NEW FILE: ins_casuale.eps --- %!PS-Adobe-3.0 EPSF-3.0 %%Creator: (ImageMagick) %%Title: (ins_casuale.eps) %%CreationDate: (Sat Sep 18 18:27:41 2004) %%BoundingBox: 0 0 1016 716 %%HiResBoundingBox: 0 0 1016 716 %%DocumentData: Clean7Bit %%LanguageLevel: 1 %%Pages: 1 %%EndComments %%BeginDefaults %%EndDefaults %%BeginProlog % % Display a color image. The image is displayed in color on % Postscript viewers or printers that support color, otherwise % it is displayed as grayscale. [...60861 lines suppressed...] DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDC end %%PageTrailer %%Trailer %%EOF |
