Seconda Esercitazione in Laboratorio


Introduzione

In questa esercitazione ci proponiamo di implementare alcuni algoritmi di ordinamento, e di studiarne sperimentalmente le prestazioni, con lo scopo di “mettere a punto” un algoritmo di ordinamento il piu' efficiente possibile nella pratica.

Per valutare l’efficienza sperimentale di un algoritmo su un determinato input consideriamo due misure:

  1. il numero di accessi all’array da ordinare;
  2. il tempo di esecuzione dell’algoritmo

Algoritmi di ordinamento

Gli algoritmi da testare sono i seguenti:

Di tali algoritmi viene gia' fornita una implementazione da utilizzare per i test disponibile qui.

Array con contatore di accessi

L'array dei dati da ordinare viene gestito attraverso la classe ArrayContatore. Un oggetto di tipo ArrayContatore rappresenta un array di double, e conta il numero di accessi effettuati, in lettura o in scrittura, ai suoi elementi. La classe deve offrire i seguenti metodi pubblici:

Una implementazione e' disponibile qui

Algoritmi di generazione dei dati

Gli algoritmi saranno valutati su array di input con diverse caratteristiche:

Per ottenere tali dati si puo' utilizzare questa classe che fornisce i seguenti metodi:

Predisposizione dell'ambiente Java per l'allocazione di memoria

Il comportamento predefinito della Java VM permette di allocare al massimo 256 MB di memoria.

Avendo la necessita' di allocare array che occupano una grande quantita' di memoria potrebbe essere opportuno modificare tale limite di allocazione.

Per fare cio' occorre specificare sulla linea di comando che avvia java le opzioni -Xms e -Xmx che fissano dimensione minima e massima riservata a Java.

Per esempio il comando java -Xmx512M -Xms512M miaClasse permette di avviare la classe miaClasse con 512MB di RAM.

Nel caso di utilizzi un IDE, si puo' ottenere lo stesso risultato modificando opportunamente le opzioni di configurazione che regolano l'invocazione della Java VM.

Misurare le prestazioni

Utilizzando l'ordinamento mediante InsertionSort e un array di 100.000 elementi generati randomicamente, realizzare un metodo che stampi su console il numero di accessi al vettore (ricordando di effettuare un reset prima di iniziare l'ordinamento) e il tempo di esecuzione (effettuando una differenza dei tempi ottenuti mediante la funzione System.currentTimeMillis() che fornisce il tempo corrente)

Testare la correttezza del metodo (utilizzando un apposito main).

Verificare inoltre sperimentalmente l'andamento quadratico dell'algoritmo in funzione di n (utilizzare valori di n opportunamente distribuiti tra 10 e 1.000.000).

La precisione del timer e' sufficiente ad apprezzare il tempo di esecuzione?

Comparare le prestazioni (Facoltativo)

Ripetere le misure utilizzando tutti algoritmi su input di diversa taglia e diverse caratteristiche, compilando una tabella simile alla seguente (con l'annotazione sia dei tempi di esecuzione che del numero di accessi all'array):

  Input 1 Input 2 ...
Algoritmo 1 ... ... ...
Algoritmo 2 ... ... ...
... ... ... ...

Si suggeriscono i seguenti valori per n: 75, 25.000, 1.000.000.

Generazione di un insieme semi-ordinato (Facoltativo)

Creare un metodo con la seguente signature: in grado di generare un array contenente un insieme semiordinato di double.
Per ottenere cio' si puo' procedere per passi:
  1. Generare un vettore ordinato (crescente) di valori da 1 a n
  2. Effettuare un numero di scambi pari al 5% del totale degli elementi tra coppie random di caselle dell'array
In pratica una volta generato il vettore iniziale ordinato, occorre iterare il lancio di 2 dati (con valori tra 0 e n-1) e scambiare le celle con indice risultante.
Il numero di volte in cui si effettuano gli scambi deve essere pari al 5% di n.
Utilizzare poi questo algoritmo di generazione per misurare le performance dei vari algoritmi di ordinamento.

QuickSort e scelta del Pivot

La scelta del pivot puo' influenzare le performance del quicksort.
Modificare l'algoritmo del quicksort in modo da scegliere il pivot secondo le seguenti strategie:

Verificare le performance su input ordinato crescente e random per le varie strategie utilizzate.

Per evitare continue modifiche si consiglia di aggiungere un paramento intero alla funzione di ordinamento con QuickSort per la scelta della politica di scelta del pivot.

(Facoltativo) Ideare ed implementare un proprio criterio di scelta del pivot tenendo conto che la scelta del minimo o del massimo valore portano ad un forte decadimento delle prestazioni.

Messa a punto del QuickSort

Mettere a punto un algoritmo con buone prestazioni pratiche, combinando insieme gli algoritmi di sorting visti in precedenza.
In particolare implementare una versione del QuickSort che, nel caso base, con dimensioni inferiori ad una data soglia s, faccia ricorso all'InsertionSort.
Comparare le prestazioni del QuickSort comparato su un input randomico (n=100.000) al variare di s=50,100, .... Una volta individuato il valore di s opportuno, comparare le prestazioni del QuickSort cosi' modificato con il MergeSort utilizzando sempre un input random.

Messa a punto degli ordinamenti (Facoltativo)

Ripetere gli stessi passi del punto precedente combinando insieme due algoritmi a scelta.

Soluzione