University » Corsi precedenti » ASD » 2005-06 » 22/05/06

Terza Esercitazione in Laboratorio

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 più 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 (facoltativo)

Gli algoritmi da implementare sono i seguenti:

• InsertionSort
• SelectionSort (facoltativo)
• MergeSort
• QuickSort
• Altri algoritmi ottenuti combinando i precedenti

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

• array già ordinati
• array ordinati in ordine inverso
• array casuali
• array casuali ma “parzialmente ordinati” (facoltativo)

Array con contatore di accessi

Implementare una 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:

• ArrayContatore(int n): costruttore. Costruisce un array di n elementi;
• void set(int i, double x): assegna x all’elemento i-esimo dell’array (equivalentemente al “classico” arr[i]=x);
• double get(int i): restituisce il contenuto dell’i-esimo elemento dell’array;
• long getCounter(): restituisce il numero di accessi effettuati all’array, in lettura o in scrittura;
• void resetCounter(): reimposta a 0 il contatore degli accessi effettuati.

Algoritmi di ordinamento

Implementare e testare gli algoritmi di ordinamento indicati in precedenza: InsertionSort, SelectionSort (facoltativo), MergeSort e QuickSort. Per ciascun algoritmo xxx, si consiglia di scrivere un metodo

static long xxxSort(ArrayContatore a, int i, int f)

che ordina il sottoarray di a compreso tra l’elemento di indice i e quello di indice f. Lo scopo è quello di favorire l’integrazione di diversi algoritmi di ordinamento.

Il metodo restituisce il numero di accessi effettuati all’array da ordinare, e ad eventuali altri array temporanei usati.

Generazione dell’input

Scrivere metodi per generare gli array di input:

• static ArrayContatore generaCresecente(int n): genera un array di n elementi, già ordinati in ordine crescente (per esempio, da 1 a n);
• static ArrayContatore generaDecresecente(int n): genera un array di n elementi, ordinati in ordine decrescente (per esempio, da n a 1);
• static ArrayContatore generaRandom(int n, double a, double b): genera un array con n elementi estratti casualmente con distribuzione uniforme nell’intervallo [a, b] (si suggerisce l’uso della classe java.util.Random, metodo nextDouble()).

Misure

Eseguire gli algoritmi su input di diversa taglia e diverse caratteristiche, compilando una tabella simile alla seguente:

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

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

Messa a punto

Mettere a punto un algoritmo con buone prestazioni pratiche, combinando gli algoritmi implementati in precedenza. Per esempio, implementare un QuickSort (o un MergeSort) che, nel caso base, faccia ricorso all’InsertionSort.

Facoltativo (ma consigliato!)

1. Scrivere un altro metodo static ArrayContatore generaSemiRandom(int n, double a, double b, double passo) per generare array “parzialmente ordinati”: array ottenuti sommando un array ordinato (i cui elementi iniziano da 0 e procedono con passo passo) ad un array random. Includere gli input generati da questo metodo nella tabellina.
2. Misurare i tempi di esecuzione degli algoritmi (cfr. l’esercitazione precedente) ed includerli nella tabellina.

Commenti dei visitatori

Accedi per lasciare commenti.