Gli algoritmi di ordinamento non basati sul confronto Zotti Paolo 62SI December 2001 email: [email protected] Struttura del Progetto IL PROGETTO E’ DIVISO IN 2 PARTI: RELAZIONE SOFTWARE - Linguaggio C++ Struttura della relazione ARGOMENTI ATTINENTI ALL’ORDINAMENTO Introduzione all’ordinamento Complessità degli algoritmi di ordinamento I numeri casuali Le liste concatenate (semplici e doppie) STUDIO DI 3 ALGORITMI DI ORDINAMENTO NON BASATI SUL CONFRONTO E LO SCAMBIO Counting Sort Radix Sort Bucket Sort TESTING DEGLI ALGORITMI Test sugli algoritmi di ordinamento Test sulla generazione di numeri casuali Cosa fa il software creato Input: Insieme di dati disordinato Ordinamento effettuato con: Counting Sort o Radix Sort o Bucket Sort Calcolo del tempo Output: Insieme di dati ordinato Struttura del software Il listato principale, Main, coordina tutto il programma State State Diagrams Class Diagrams Radix Sort Use Case UseClass Case Diagrams DiagramsSort Counting State State Diagrams Class Diagrams Bucket Sort Scenario Scenario Diagrams Class Diagrams Rand Main Component Component Diagrams Class Diagrams Liste Introduzione Buon giorno sono sign.alcune Cormen, il mago degli relazione. algoritmi. Vi Cominciamo aiuterò a capire subitoilmeglio con il contenuto definizioni di questa basilari IlQuesta tempo di aggirata calcolo difficoltà viene valutando il numero di Nel valutare tempo Esatto! Il tempo di calcolo di una operazioni inilordine didi calcolo T(n), è difficile quantificare con procedura è ilcioè costo complessivo grandezza, esprimendole esattezza il numero delle elementari in comeoperazioni limitazioni delladi funzione operazioni elementari eseguite. funzione della dimensione n dei T(n) al tendere all’infinito della dati in ingresso. dimensione n dei dati in ingresso. T(n) n Quantità dei dati Il tempo occorrente ad ordinare un insieme di dati, si puo’ rappresentare attraverso una funzione. La funzione T(n). Tempo La limitazione può essere: Il costo delle operazioni é valutato principalmente nel caso peggiore, perché presenta il vantaggio di garantire che l’algoritmo non richiederà mai per nessun dato in ingresso di dimensione n, un tempo maggiore. 2 O S Limitazione sup. e inf. equivalente Limitazione superiore Caso Peggiore Limitazione inferiore Caso Migliore Cosa è un algoritmo??? Input ALGORITMO Output Qualsiasi procedura definita che prende Un algoritmo é quindicomputazionale una sequenza diben passi computazionali alcuni valori, come inputnell'output. e produce alcuni valori, come output é che trasformano l'input chiamata algoritmo. Cosa è l’ordinamento? L'ordinamento, consiste nel disporre un gruppo di informazioni in ordine crescente o decrescente utilizzando un algoritmo di ordinamento. Insieme di dati disordinato ALGORITMO Di ordinamento Insieme di dati ordinato Chiave dell’ordinamento Struttura di dati chiavequando é quellasiparte InLagenere, esegue deiordinamento, dati che determina un come la posizione relativa dei vari chiave dell'ordinamento, elementi. Pertanto nelsi fa il cioè l'oggetto con cui confronto viene fra gliutilizzata elementi, confronto, viene utilizzata solo la solo una parte delle chiave ma, nello scambio informazioni disponibili. dei dati, viene trasferita l'intera struttura. Nome Cognome Data nascita Nome l Residenza Occupazione Hobby Religione Chiave Ora vi spiegherò gli algoritmi di ordinamento trattati in questa relazione. Passiamo allo studio del primo Sono tutti algoritmi che non basano il proprio funzionamento sul confronto e lo scambio di dati. algoritmo di ordinamento: Counting Sort Counting Sort: idea di base Counting Sort, si basa sull’ipotesi che ognuno degli “n” elementi in input sia un intero nell’intervallo da 1 a “k” ove “k” è un numero non troppo grande. Si determina, per ogni elemento x in input, il numero di elementi minori di x. Questa informazione può essere usata per porre l’elemento x, direttamente nella sua esatta posizione nell’array di output. Per es., se vi sono 10 elementi minori di x, x va messo in undicesima posizione nell’array di output. L’algoritmo deve gestire situazioni in cui alcuni elementi abbiano lo stesso valore, infatti non si vuole metterli tutti nella stessa posizione nell’array di output. Counting Sort: proprietà E’ veloce perché fa delle ipotesi sull’input, infatti, assume che l’input, consista di numeri interi in un piccolo intervallo. Stabile Risorse occorrenti: 3 array array A: array di dimensione n, contenente gli n numeri da ordinare: array B: array di dimensione n, contenente la sequenza degli n numeri ordinata Array C: array di dimensione k, temporaneo di lavoro, dove k é il massimo numero trovato in A Cosa significa stabile??? Un algoritmo è stabile quando elementi con lo stesso valore, Cioè, lo spareggio elementi con loordine stessoinvalore compaiono nell’arraytra di due input, nello stesso cui avviene secondo la regola per cui qualunque numero compaia compaiono in quello di output. per primo nell’array di input, appare per primo nell’array di output. Counting Sort: esempio Esecuzione di Counting Sort su un array di input A[ 8 ], dove ogni elemento di A é un intero positivo non più grande di k=6. A 1 2 3 4 5 6 7 8 3 6 4 1 3 4 1 4 B 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 input output C 1 2 3 4 5 6 0 0 0 0 0 0 Temporaneo di lavoro Si dimensiona l’array C, con il massimo numero “k” in A Counting Sort: prima fase 4 5 6 C 0 0 1 0 0 0 4 5 6 C 0 0 1 0 0 1 4 5 6 C 0 0 1 1 0 1 4 5 6 C 1 0 1 1 0 1 4 5 6 C 1 0 2 1 0 1 4 5 6 C 1 0 2 2 0 1 4 5 6 C 1 0 2 3 0 1 4 5 6 C 1 0 2 4 0 1 1 4 5 6 7 8 A 3 6 4 1 3 4 4 4 1 2 3 input Scorrendo tutto l’array partendo da A [ 1 ] fino ad arrivare ad A [ 8 ]; se il valore di un elemento in input é “ i ”, si incrementa C[ i ]. Così, alla fine C[ i ] contiene il numero di elementi di input uguali ad i per ciascun intero i=1,2,…,k. 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 Seconda fase: somma cumulata 4 5 6 C 1 0 2 4 0 1 1 2 3 prima Si determina per ciascun i = 1,2,…,k, quanti elementi dell'input sono minori o uguali ad i. Questo viene fatto determinando la somma cumulata degli elementi dell'array C[ ]. For x = 2 to 6 C [ i ] = C [ i ] + C [ i-1 ] 4 5 6 C 1 1 3 7 7 8 1 2 3 dopo Terza fase: sistemazione in B 4 5 6 7 8 A 3 6 4 1 3 4 1 4 1 2 3 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 3 4 5 6 C 1 1 3 7 7 8 B 1 2 input output Counting Sort: terza fase, prima iterazione A 1 2 3 4 5 6 7 3 6 4 1 3 4 4 O 4 5 6 C 1 1 3 7 7 8 1 B 2 3 8 4 1 2 3 4 5 6 7 8 0 0 0 0 0 0 4 0 Partendo dall’ultima posizione di A, si prende il numero contenuto in A [ 8 ] = 4. Guardiamo cosa è contenuto in C [ 4 ] = 7. Sistemiamo il 4 in B [ 7 ] Counting Sort: seconda iterazione A B 1 2 3 4 5 6 3 6 4 1 3 4 1 2 3 4 5 6 0 0 0 0 0 0 4 5 6 C 1 1 3 7 7 8 1 2 Qualcosa non funziona, così facendo perdiamo un dato. 3 7 O 8 4 4 7 8 4 0 Attenzione! A 1 2 3 4 5 6 3 6 4 1 3 4 7 8 4 4 OO Dobbiamo gestire il caso in cui gli elementi contenuti in A, non siano tutti distinti. Ripartiamo dall’inizio Per questo, decrementiamo C[4], in modo che alla prossima iterazione, nel caso di elementi non distinti, il numero si inserisca nell’array di output, nella sua corretta posizione. Prima Dopo 1 2 3 4 5 6 7 3 6 4 1 3 4 4 O 1 2 3 4 5 6 7 8 0 0 0 0 0 0 4 0 1 2 3 4 5 6 C 1 1 3 7 7 8 A B C 1 2 3 4 5 6 1 1 3 6 7 8 8 4 Counting Sort: terza fase, prima iterazione 1 2 3 4 5 6 7 3 6 4 1 3 4 4 O 1 2 3 4 5 6 7 8 0 0 0 0 0 0 4 0 3 4 5 6 C 1 1 3 7 7 8 A B 1 Dopo C 2 1 2 3 4 5 6 1 1 3 6 7 8 8 4 Partendo dall’ultima posizione di A, si prende il numero contenuto in A [ 8 ] = 4. Guardiamo cosa è contenuto in C [ 4 ] = 7. Sistemiamo il 4 in B [ 7 ] Decrementiamo C [ 4 ] Counting Sort: terza fase, seconda iterazione 1 2 3 4 5 6 3 6 4 1 3 4 1 2 3 4 5 0 0 0 0 0 3 4 5 6 C 1 1 3 6 7 8 A B 1 C 2 7 O 8 4 4 6 7 8 4 4 0 1 2 3 4 5 6 1 1 3 5 7 8 Counting Sort: terza fase, terza iterazione 1 2 3 4 5 3 6 4 1 3 1 2 3 4 0 0 0 0 3 4 5 6 C 1 1 3 5 7 8 A B 1 Dopo C 2 6 O 7 8 4 4 4 5 6 7 8 4 4 4 0 1 2 3 4 5 6 1 1 3 4 7 8 Situzione finale: array ordinato Continuando con queste iterazioni, alla fine otterremo un’array ordinato. B 1 2 3 4 5 6 7 8 1 1 3 3 4 4 4 6 Tempo impiegato da Counting Sort Tempo Abbiamo calcolato attraverso formule matematiche, che il tempo è lineare e quindi che Il limite superiore e inferiore si equivalgono cioè che il tempo impiegato nel caso peggiore (array ordinato in modo decrescente) equivale al tempo impiegato nel caso migliore (array ordinato in modo crescente). Questa è una caratteristica degli algoritmi di ordinamento non basati sul confronto. Ora dobbiamo verificare con dei test se il tempo calcolato equivale al tempo realmente impiegato dall’algoritmo. T= 2 ( k+n ) n La limitazione può essere: 2 O S Limitazione sup. e inf. equivalente Limitazione superiore Caso Peggiore Limitazione inferiore Caso Migliore Test Counting Sort Test Counting Sort Scopo del test, verificare e dimostrare 2 ipotesi, la prima: dato che questo algoritmo di ordinamento é basato sulla distribuzione e usa metodi, per ordinare l'insieme dei dati, non basati sul confronto e lo scambio, l'ordine dei numeri in input non dovrebbe influire sulle prestazioni dell'algoritmo; Prima ipotesi dimostrata Ordine dei numeri CASUALE L’ordine dei numeri non influisce sulle prestazioni CRESCENTE dell’algoritmo. 500 1000 1500 2000 2500 3000 3500 4000 Quantità numeri 4500 5000 Inf. time DECRESCENTE Test Counting Sort La seconda ipotesi da dimostrare è la seguente: il tempo necessario all'ordinamento cresca in modo lineare al crescere di n, dove n rappresenta la quantità dei numeri da ordinare. Verifica della linearità Ordine dei numeri Il tempo cresce in modo CASUALE lineare, all’aumentare della dimensione n dei dati in ingresso. CRESCENTE 500 1000 1500 2000 2500 3000 3500 4000 Quantità numeri 4500 5000 Inf. time DECRESCENTE Passiamo allo studio del prossimo algoritmo di ordinamento: Radix Sort Radix Sort IDEA DI BASE L‘idea, consiste nell'utilizzare un qualsiasi algoritmo di ordinamento, che ordini l'array usando come chiave di ordinamento la cifra meno significativa. Quando l'intero array è ordinato sulla cifra meno significativa, lo si ordina sulla seconda cifra meno significativa utilizzando un algoritmo stabile. Il processo continua finché i numeri sono stati ordinati su tutte le d cifre. A quel punto, i numeri sono completamente ordinati. Radix Sort Ossia: For X = 1 to N Usa un ordinamento stabile per ordinare l’intero array sulla cifra X Proprietà, particolarità e risorse utilizzate Proprietà: Stabilità: Se l'algoritmo utilizzato per l'ordinamento intermedio é stabile, cioè, ha la proprietà che numeri con lo stesso valore appaiono nell'array di output nello stesso ordine di ingresso, avremo alla fine un array ordinato. La stabilità dell’algoritmo di ordinamento intermedio è indispensabile. Particolarità: Radix Sort, ordina i numeri in modo contro intuitivo, cioè non naturale, ordinando prima sulla cifra meno significativa, poi sulla seconda cifra meno significativa, e così via fino alla cifra più significativa. Risorse hardware occorrenti: Quelle utilizzate dall’algoritmo di ordinamento intermedio Radix Sort: esempio Esecuzione di Radix Sort su un array di input A [ 7 ], dove ogni elemento di A é un intero positivo. 329 457 657 839 436 720 355 ARRAY ORIGINALE Radix Sort O 329 720 457 355 657 436 839 457 436 657 720 329 355 839 La prima operazione che deve eseguire RadixSort, é quella di effettuare l'ordine, usando come chiave di ordinamento, la cifra meno significativa dei numeri stessi. Logicamente, ad ogni ordinamento sulla chiave (cifra meno significativa), deve corrispondere uno spostamento di tutta la struttura (il numero in esame). Per questo, é importante che l'ordine intermedio venga eseguito da un algoritmo di ordinamento stabile. L’array al primo passaggio: i numeri risultano parzialmente ordinati. Radix Sort 720 O 720 355 329 436 436 457 839 657 355 329 457 839 657 la seconda operazione che deve eseguire RadixSort é quella di effettuare l'ordine, usando come chiave di ordinamento, la seconda cifra meno significativa L’array al secondo passaggio: i numeri risultano parzialmente ordinati. Radix Sort O720 329 329 355 436 436 839 457 355 657 457 720 657 839 la terza operazione che deve eseguire RadixSort é quella di effettuare l'ordine, usando come chiave di ordinamento, la terza cifra meno significativa L’array al terzo passaggio: i numeri risultano ordinati. Possiamo calcolare in anticipo i cicli da effettuare??? Quindi, in uninarray contenente n numeri interi interi Importante: questo caso, dato che i numeri composti ognuno di dcomposti cifre, occorrono d passaggi presi in analisi, sono da 3 cifre ciascuno,per ordinare completamente il vettore. sono sufficienti 3 passaggi per ottenere un ordine definitivo. Tempo impiegato da Radix Sort IL TEMPO E’ LINEARE. Il limite superiore e inferiore si equivalgono. Tempo 2(dxn) n Test Radix Sort Test Radix Sort Scopo del test, verificare e dimostrare 2 ipotesi, la prima: dato che questo algoritmo di ordinamento é basato sulla distribuzione e usa metodi, per ordinare l'insieme dei dati, non basati sul confronto e lo scambio, l'ordine dei numeri in input non dovrebbe influire sulle prestazioni dell'algoritmo; L’ordine dei numeri non influisce sul tempo Ordine dei numeri Radix Sort in un range [ 0 / (2^10)-1 ] e [ 0 / (2^31)-1 ] CASUALE 14 Cas (2^31)-1 Ord (2^31)-1 Inv (2^31)-1 Casi (2^10)-1 Ord (2^10)-1 Inv (2^10)-1 6 4 2 Quantità numeri 00 4500 5000 Inf. time 500 1000 1500 2000Quantita' 4000 3500 2500 3000 numeri x 1000 50 00 45 00 40 00 35 00 30 00 25 00 20 00 15 00 10 0 0 50 DECRESCENTE Decimi di secondo L’ordine dei numeri12non 10 influisce sulle prestazioni CRESCENTE dell’algoritmo. 8 Test Radix Sort Seconda ipotesi da dimostrare: il tempo necessario all'ordinamento cresca in modo lineare al crescere di n, dove n rappresenta la quantità dei numeri da ordinare. Verifica della linearità Cas (2^31)-1 Ord (2^31)-1 Inv (2^31)-1 Casi (2^10)-1 Ord (2^10)-1 Inv (2^10)-1 8 6 4 2 Quantità numeri 00 4500 5000 Inf. time 500 1000 1500 2000Quantita' 4000 3500 2500 3000 numeri x 1000 50 00 45 00 40 00 35 00 30 00 25 00 20 00 15 10 00 0 0 DECRESCENTE Radix Sort in un range [ 0 / (2^10)-1 ] e [ 0 / (2^31)-1 ] 10 50 CRESCENTE Decimi di secondo Ordine dei numeri Il tempo cresce in modo CASUALE lineare, all’aumentare 14 della dimensione n dei 12 dati in ingresso. Passiamo allo studio dell’ultimo algoritmo di ordinamento, cioè Bucket Sort Bucket Sort IDEA DI BASE (1) L'idea generale di Bucket Sort é quella di dividere un intervallo prefissato in n sotto intervalli di uguale dimensione, detti bucket (cestini), e quindi distribuire gli n elementi da ordinare nei rispettivi bucket. Esempio: ordine delle carte da ramino Il bucket cuori conterrà le carte di cuori Cuori quadri Il bucket quadri conterrà le carte di quadri 8 8 5 Il bucket fiori conterrà le carte di fiori 7 5 fiori picche 5 Il bucket picche conterrà le carte di picche Bucket Sort IDEA DI BASE L'idea generale di Bucket Sort é quella di dividere un intervallo prefissato in n sotto intervalli di uguale dimensione, detti bucket (cestini), e quindi distribuire gli n elementi da ordinare nei rispettivi bucket. Sotto l'assunzione che gli elementi dell'input siano uniformemente distribuiti nell'intervallo specificato, non ci si aspetta che molti numeri cadano nello stesso bucket. Per produrre l'output, si ordinano semplicemente i numeri di ogni bucket, con un algoritmo di ordinamento e quindi, si elencano gli elementi di ogni bucket prendendoli in ordine. Bucket Sort Cioè: 1) For X = 1 to N (N= quantità numeri in input) trova in quale bucket va inserito l’elemento array[x] e inseriscicelo 2) For X = 1 to numero bucket ordina il bucket [X] con un algoritmo di ordinamento 3) Concatena insieme i bucket [1]…bucket [2]… ……bucket [numero dei bucket] Bucket Sort Proprietà: BucketSort assume che l'input sia generato da un processo casuale che distribuisce gli elementi in modo uniforme sull'intervallo designato. Risorse hardware occorrenti: Il codice richiede un array, liste [ bucket ], di liste a doppio concatenamento, dove ogni elemento di liste [ bucket ] rappresenta un bucket. Bucket Sort: esempio Esecuzione di Bucket Sort su un array di input A [ 8 ], dove ogni elemento di A é un double positivo. Supponiamo di dividere l'intervallo [0…1], in 10 sotto intervalli di uguale dimensione, e quindi distribuire gli n elementi da ordinare nei bucket. A 0.78 0.17 Situazione iniziale 0.35 0.26 0.72 0.94 0.21 0.12 Prima operazione: distribuire I numeri Bucket 0 Bucket 1 A 0.78 0.12 0.17 Bucket 2 0.17 0.26 0.35 0.21 0.26 Bucket 3 0.35 0.72 Bucket 4 0.94 Bucket 5 0.21 0.12 Bucket 6 Bucket 7 0.78 0.72 Bucket 9 0.94 Bucket Sort La seconda operazione che deve eseguire Bucket Sort é quella di ordinare i numeri di ogni bucket, con un algoritmo di ordinamento “adatto”, in questo caso, visto che l'insieme numerico in input é composto da tipi double, si può utilizzare l’algoritmo di ordinamento Insert Sort. Secondo passaggio Ordinare I numeri Bucket 0 Bucket 1 Bucket 2 0.17 0.12 0.26 0.21 Bucket 3 Bucket 4 Bucket 5 Bucket 6 Bucket 7 Bucket 8 0.35 Bucket 9 0.94 0.78 0.72 Risultato dell’ordinamento in ogni bucket Bucket 0 Bucket 1 0.12 0.17 Bucket 2 0.21 0.26 Bucket 3 0.35 Bucket 4 Bucket 5 Bucket 6 Bucket 7 0.72 0.78 Bucket 9 0.94 Secondo passaggio: ordinare ogni Bucket con un algoritmo di ordinamento basato sul confronto Bucket 0 Bucket 1 Bucket 2 0.12 0.17 0.21 0.26 Bucket 3 Bucket 4 Bucket 5 Bucket 6 Bucket 7 Bucket 8 0.35 Bucket 9 0.94 0.72 0.78 Bucket Sort: terzo passaggio La terza ed ultima operazione da eseguire, é quella di concatenare insieme le liste (bucket) liste[0], liste[1], ..., liste[n-1] in quest'ordine copiando gli elementi nell'array originale ordinati[ ], ottenendo il seguente risultato: B 0.12 0.17 0.21 0.26 0.35 Array ordinato 0.72 0.78 0.94 Seconda operazione: ordinare I numeri in ogni bucket Bucket 1 0.12 0.17 Bucket 2 0.21 0.26 Bucket 3 0.35 B 0.12 Bucket 7 0.17 0.21 0.26 0.35 0.72 0.78 0.94 0.72 0.78 Bucket 9 0.94 Test Bucket Sort Precisazioni Per non uscire dall’argomento della relazione, cioè, gli algoritmi non basati sul confronto e lo scambio, e per sperimentare il comportamento di Bucket Sort con un algoritmo di ordinamento non basato sul confronto, ho deciso di usare come algoritmo di ordinamento intermedio, Radix Sort. Il range dei numeri in input è [0…(2^31)-1] Questo intervallo è stato diviso in 214.748 bucket Verificare e dimostrare che: dato che questo algoritmo di ordinamento é basato sulla distribuzione e usa metodi, per ordinare l'insieme dei dati, non basati sul confronto e lo scambio, l'ordine dei numeri in input non dovrebbe influire sulle prestazioni dell'algoritmo; L’ordine dei numeri non influisce sul tempo Ordine dei numeri Bucket Sort con Radix Sort in un range [ 0 / (2^31)-1 ] CASUALE 250 Secondi L’ordine dei numeri200 non influisce sulle prestazioni CRESCENTE 150 dell’algoritmo. Casuali Ordinati Inversi 100 DECRESCENTE 50 50 0 0 10 0 0 15 0 0 20 0 0 25 0 0 30 0 0 35 0 0 40 0 500 1000 1500 2000Quantita' 4000 3500 2500 3000 numeri x 1000 Quantità numeri 0 45 0 0 50 4500 0 5000 Inf. time 0 Era ovvio!!! Se l'algoritmo usato per l'ordinamento intermedio non è influenzato dall’ordine dei numeri in input, é ovvio che anche Bucket Sort non ne viene influenzato semplicemente perché questo algoritmo, non fa altro che ordinare ogni bucket con l’algoritmo di ordinamento intermedio Radix Sort. Verificare e dimostrare che: il tempo necessario all'ordinamento cresca in modo lineare al crescere di n, dove n rappresenta la quantità dei numeri da ordinare. IL TEMPO E’ LINEARE CRESCENTE Secondi Ordine dei numeri Il tempo cresce in modo CASUALE lineare, all’aumentare 250 della dimensione n dei dati in ingresso. 200 Bucket Sort con Radix Sort in un range [ 0 / (2^31)-1 ] Casuali Ordinati Inversi 150 100 DECRESCENTE 50 50 0 0 10 0 0 15 0 0 20 0 0 25 0 0 30 0 0 35 0 0 40 0 500 1000 1500 2000Quantita' 4000 3500 2500 3000 numeri x 1000 Quantità numeri 0 45 0 0 50 4500 0 5000 Inf. time 0 LOGICO! Il quello che ci si aspettava, Darisultato notare,era il notevole incremento temporale infatti SortSort, noncausato fa altro che rispettoBucket a Radix dallaordinare gestionei numeri presenti in ogni bucket,i bucket. usando delle liste che rappresentano l'algoritmo Radix Sort che ha un tempo di ordinamento lineare. Differenza con Radix Sort Radix Sort in un range [ 0 / (2^10)-1 ] e [ 0 / (2^31)-1 ] 14 Decimi di secondo 12 Cas (2^31)-1 Ord (2^31)-1 Inv (2^31)-1 Casi (2^10)-1 Ord (2^10)-1 Inv (2^10)-1 10 8 6 4 2 0 5 0 0 0 4 5 0 0 4 0 0 0 3 5 0 0 3 0 0 0 2 5 0 0 2 0 0 0 0 5 1 1 0 5 0 0 0 0 0 Quantita' numeri x 1000 Bucket Sort con Radix Sort in un range [ 0 / (2^31)-1 ] 250 Casuali Ordinati Inversi 150 100 50 Quantita' numeri x 1000 0 5 0 0 0 4 5 0 0 4 0 0 0 3 5 0 0 3 0 0 0 2 5 0 0 2 0 0 0 0 5 1 1 0 0 0 0 0 0 5 Secondi 200 Secondo Test Bucket Sort Premessa Si consideri il comportamento di un qualsiasi algoritmo di ordinamento basato sul confronto. Il tempo impiegato da questo algoritmo dipende pesantemente dall'ordine con cui i numeri sono memorizzati nei cestini e dalla quantità numerica presente in ognuno di essi. Nel caso peggiore (ordine inverso), assumendo che ci siano n elementi nel bucket dobbiamo scorrere n-1 elementi. Per ogni elemento occorre esaminare e spostare altri n-1 elementi, per cui risulta una complessità O(n^2), cioè il tempo non cresce in modo lineare ma esponenziale. Con una tale complessità, é conveniente che la presenza numerica in ogni cestino sia la più bassa possibile quindi maggiore è Il numero dei cestini minore sarà la presenza numerica in ognuno di essi e di conseguenza minore sarà il tempo di calcolo. Questo è lo scopo della distribuzione di Bucket Sort Insert Sort casuali SCOPERTA La conseguenza di questa affermazione é che Bucket checaso, Radix Sortessere ha un implementato tempo lineare con la 1 Sort, inVisto questo deve distribuzione diventa perché non di ci tempo solo cestino. A questo puntoassurda é solo una perdita interessa più nel checestino la distribuzione numerica ogni sistemare i numeri per poi ordinarli conin Radix sia la piùfarli bassa possibile Sort, écestino più intelligente ordinare direttamente da Radix Sort. Il tempo è e resterà sempre lineare. Verificare e dimostrare che: L’esperimento consiste nell’ordinare le stesse implementare l'algoritmo Bucket Sort usando per quantità numeriche, prima utilizzando un solo l'ordinamento intermedio un algoritmo non basato bucket e poi utilizzandoli tutti, osservando se il sul confronto è assurdo. tempo è lo stesso. Nessun testo analizzato, contiene spiegazioni riguardo alla fondamentale importanza di usare per l’ordinamento intermedio un algoritmo basato sul confronto e al contrario, dell’assurdità di usarne uno non basato sul confronto Invece usando Radix Sort Il notevole incremento temporale è causato dalla gestione delle liste( bucket). Bucket Sort con Radix Sort in un range [ 0 / (2^31)-1 ] 900 800 700 Secondi 600 1 Cestino 214748 Cestini 500 400 300 200 100 Quantità numeri 00 4500 5000 Inf. time 500 1000 1500 2000 Quantita' 4000 3500 2500 3000 numeri x 1000 50 00 45 00 40 00 35 00 30 00 25 00 20 00 15 00 10 50 0 0 Il tempo è sprecato in questa fase Bucket 0 Bucket 1 0.12 0.17 Bucket 2 0.21 0.26 Bucket 3 0.35 Bucket 4 Bucket 5 Bucket 6 Bucket 7 0.72 0.78 Bucket 9 0.94 Analisi teorica Escludendo il tempo utilizzato nella gestione delle liste e nella distribuzione degli n numeri nei cestini, le prestazioni devono essere equivalenti sia nel caso che si utilizzi 1 solo cestino, sia che si utilizzino tutti i cestini. L’ipotesi è dimostrata. Importante Note: Questo non significa che Bucket Sort è inutile, infatti é nato per ordinare sequenze numeriche in virgola mobile. Usando questo tipo di dati, non é possibile implementare per l'ordinamento intermedio, algoritmi come Counting Sort o Radix Sort, ma diventa necessario rivolgersi ad algoritmi che basano il loro funzionamento sul confronto e lo scambio. Infatti, implementando Bucket Sort con un algoritmo di questo tipo, il numero dei cestini influisce in maniera determinante sul tempo di calcolo perché maggiore é il numero dei cestini, minore sarà la distribuzione numerica in ognuno di essi e di conseguenza, minore sarà il tempo di calcolo. Test Bucket Sort A titolo di curiosità si osservi il prossimo grafico, che presenta Bucket Sort implementato con l'algoritmo di ordinamento intermedio Insert Sort. Per l'ordinamento di un insieme di numeri fino a circa 1 milione i tempi sono molto vicini allo zero, ma superando il milione di elementi il tempo di calcolo esplode. Infatti, quando la quantità di numeri é relativamente bassa, la distribuzione numerica in ogni cestino é di conseguenza molto bassa e Insert Sort deve eseguire un numero bassissimo di confronti e scambi. Quando la quantità di numeri presenti in ogni cestino comincia ad aumentare notevolmente, il tempo occorrente all'ordinamento cresce in modo esponenziale. Grafico I numeri casuali Il prossimo test viene effettuato per dimostrare che le sequenze numeriche create dal generatore di numeri casuali, siano effettivamente…..casuali. (forse!!!) Numeri casuali Scopo del test, verificare e dimostrare che: Il primo esperimento, é stato eseguito per verificare che il generatore di numeri casuali crei un insieme di numeri interi, effettivamente distribuiti nell'intervallo [0..2 ^(31-1)] Il generatore crea 20.000.000 di numeri e li riversa nei 214.748 bucket che utilizza l’algoritmo BucketSort; viene contata la quantità di numeri presente in ogni cestino. l'operazione viene ripetuta altre 2 volte. viene calcolata la media in ogni cestino, riportata sul grafico. Se il generatore di numeri casuali, crea numeri interi uniformemente distribuiti nell'intervallo prefissato, nei cestini dovremmo trovare quantità pi u o meno uguali di numeri. Grafico Presenza Numerica Nei Cestini 140 120 Presenze 80 60 40 20 Numero del Cestino 1E+05 99584 91924 84264 76604 68944 61284 53624 45964 38304 30644 22984 15324 7664 0 4 Presenze 100 Conclusioni Bucket Sort Radix Sort Counting Sort Insert sort Quick Sort Un algoritmo "efficiente" deve svolgere il suo compito in un tempo accettabile utilizzando le risorse a disposizione senza sprechi. Quindi uso intelligente delle risorse Questo non significa che Insert Sort, è un Architetture e dialgoritmi algoritmo scarsa utilità. Radix Sort Intel 286 Algoritmi ideatiInfatti per risolvere stesso algoritmo problema, si possono con loquesto spesso differiscono vistosamente ordinare i numeriperinquanto virgola mobile, cosa non riguarda la loro efficienza e queste differenze con glidella algoritmi analizzati in questa possono esserepossibile più significative differenza relazione. tra un calcolatore molto lento e un supercomputer.Ogni algoritmo ha il suo campo di Infatti, se proviamo ad ordinare 10.000.000 di applicazione numeri ordinati in modo decrescente, con Radix Sort, su un computer dotato di processore intel Insert 286, otterremo un tempo di ordinamento Sort estremamente basso, rispetto ad un ordinamento della stessa sequenza numerica, effettuato sul computer dell’Interprise, usando Insert Sort. Galaxy 10086 Algoritmi efficienti e hardware veloce Efficienza Miglior efficienza L'esempio precedente vuole dimostrare che: progettare algoritmi efficienti é importante quanto progettare sistemi hardware sempre più veloci; usare algoritmi specifici in base al problema da risolvere significa usare in modo intelligente le risorse e abbassare notevolmente i tempi di calcolo. “Sono due tessere dello stesso mosaico” The Best Quale algoritmo di ordinamento si é dimostrato il più efficiente in termini di utilizzo: delle risorse ? …e del tempo ? Sono tutti ottimi Radix Sort Radix Sort Counting Sort Bucket Sort Bucket Sort Counting Sort • Tutti gli algoritmi analizzati in questa ricerca sono degli ottimi "algoritmi di ordinamento", progettati in modo intelligente. Ognuno di questi è ottimo se usato in modo specifico. Uso Intelligente degli algoritmi Sono il più veloce, ma la mia limitazione di range mi penalizza pesantemente, quindi usatemi quando dovete ordinare numeri appartenenti ad un intervallo limitato, per es 0…2^10 • IDEA: Avere a disposizione un’ampia varietà di algoritmi da usare in modo appropriato a seconda del problema da risolvere Sono un po’ meno veloce di Counting Sort ma lavoro in qualsiasi Range Io devo lavorare solo con Radixmobile Sort elementi in virgola Counting Sort Bucket Sort La scelta dell’algoritmo dipende dal lavoro che si deve eseguire. THE END