[Avl-cvs] avl/docs relazione.dvi,1.4,1.5 relazione.tex,1.12,1.13
Brought to you by:
hetfield666,
jah2003
Menu
▾
▴
[Avl-cvs] avl/docs relazione.dvi,1.4,1.5 relazione.tex,1.12,1.13
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-18 17:43:56
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv9695 Modified Files: relazione.dvi relazione.tex Log Message: Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 Binary files /tmp/cvssIXmZB and /tmp/cvsd71kIt differ Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.12 retrieving revision 1.13 diff -C2 -d -r1.12 -r1.13 *** relazione.tex 18 Sep 2004 16:45:19 -0000 1.12 --- relazione.tex 18 Sep 2004 17:43:47 -0000 1.13 *************** *** 11,15 **** \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} ! \makeatletter \usepackage{babel} --- 11,15 ---- \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} ! \usepackage{fullpage} \makeatletter \usepackage{babel} *************** *** 262,266 **** 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} --- 262,266 ---- 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 malgrado le considerazioni precedenti. Proprio a questo sono dovuti i vantaggi che si ottengono ad utilizzare l'implementazione AVL. Tale implementazione infatti mantiene le stesse prestazioni nell'eseguire le tre operazioni principali indipendentemente dalla sequenza di input. \section{Macchina utilizzata} *************** *** 277,281 **** \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. --- 277,281 ---- \end{itemize} ! \section{Inserimento di una sequenza di valori casuali}\label{ins_cas} 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. *************** *** 283,291 **** 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 --- 283,291 ---- 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 esecuzione, 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=400pt]{ins_casuale} \end{center} \newpage *************** *** 304,309 **** 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\\ --- 304,309 ---- 80000&0.630000&0.210000\\ 90000&0.710000&0.240000\\ ! 100000&0.780000&0.280000\\ ! 110000&0.890000&0.300000\\ 120000&1.010000&0.320000\\ 130000&1.110000&0.360000\\ *************** *** 312,316 **** 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\\ --- 312,316 ---- 160000&1.390000&0.470000\\ 170000&1.500000&0.560000\\ ! 180000&1.620000&0.580000\\ 190000&1.720000&0.610000\\ 200000&1.850000&0.650000\\ *************** *** 340,344 **** 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\\ --- 340,344 ---- 360000&3.730000&1.410000\\ 370000&4.020000&1.380000\\ ! 380000&4.100000&1.450000\\ 390000&4.200000&1.590000\\ 400000&4.220000&1.610000\\ *************** *** 376,380 **** 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\\ --- 376,380 ---- 1500&0.010000&0.030000\\ 2000&0.010000&0.060000\\ ! 2500&0.010000&0.130000\\ 3000&0.010000&0.160000\\ 3500&0.010000&0.260000\\ *************** *** 396,402 **** ! \section{Inserimento di una sequenza di valori casuali} ! \section{Inserimento di una sequenza di valori decrescenti} \end{document} --- 396,468 ---- ! \section{Cancellazione di una sequenza di valori casuali} ! Per effettuare questo test si \`e prima dovuto costruire un albero in modo casuale seguendo le considerazioni fatte nel paragrafo \ref{ins_cas}. In seguito si \`e eseguita una sequenza di cancellazioni lunga $n$ di elementi presenti nell'albero che ha quindi cancellato tutti i nodi dell'albero. ! ! I risultati evidenziano come non ci sia una differenza rilevante tra le due implemetazioni, infatti entrambe le curve riportate seguono un andamento lineare con una pendenza maggiore nel caso di AVL. ! ! Anche in questo caso come in quello del paragrafo \ref{ins_cas} l'implementazione BST risulta leggermente pi\`u performante rimanendo asintoticamente identica. I motivi perché ci\`o accade sono gli stessi enunciati in precedenza. ! ! \begin{center} ! \includegraphics[width=420pt]{canc_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 ! 1000&0.000000&0.000000\\ ! 1500&0.010000&0.000000\\ ! 2000&0.010000&0.000000\\ ! 2500&0.010000&0.010000\\ ! 3000&0.010000&0.010000\\ ! 3500&0.010000&0.010000\\ ! 4000&0.020000&0.010000\\ ! 4500&0.020000&0.010000\\ ! 5000&0.030000&0.020000\\ ! 5500&0.030000&0.020000\\ ! 6000&0.030000&0.020000\\ ! 6500&0.030000&0.030000\\ ! 7000&0.030000&0.030000\\ ! 7500&0.040000&0.030000\\ ! 8000&0.040000&0.030000\\ ! 8500&0.040000&0.040000\\ ! 9000&0.040000&0.040000\\ ! 9500&0.050000&0.040000\\ ! \hline ! \end{tabular} ! \end{center} ! \section{Cancellazione di una sequenza di valori decrescenti} ! \begin{center} ! \includegraphics[width=420pt]{canc_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 ! 1000&0.000000&0.000000\\ ! 1500&0.010000&0.010000\\ ! 2000&0.010000&0.020000\\ ! 2500&0.010000&0.040000\\ ! 3000&0.010000&0.050000\\ ! 3500&0.020000&0.060000\\ ! 4000&0.020000&0.080000\\ ! 4500&0.020000&0.090000\\ ! 5000&0.020000&0.120000\\ ! 5500&0.030000&0.150000\\ ! 6000&0.030000&0.170000\\ ! 6500&0.030000&0.200000\\ ! 7000&0.040000&0.250000\\ ! 7500&0.040000&0.340000\\ ! 8000&0.040000&0.380000\\ ! 8500&0.040000&0.420000\\ ! 9000&0.050000&0.490000\\ ! 9500&0.050000&0.550000\\ ! \hline ! \end{tabular} ! \end{center} \end{document} |
