Laboratorio di Informatica: Algoritmi e Strutture Dati
a.a. 1999/2000
Progetto n. 2
Data: 02.03.2000
Data consegna relazioni: 13.04.2000
- Si vuole ottimizzare il codice di Quicksort, per ottenere un programma di ordinamento il piu' veloce possibile. Si vuole pertanto eseguire il "code-tuning" del programma gia' sviluppato. Per far cio':
- si rimuova la ricorsione, sostituendo la ricorsione di coda con iterazione e quella non di coda con una gestione esplicita della pila
- si eliminino dall'interno dei cicli tutte le istruzioni che non sono assolutamente necessarie (calcolo di sotto-espressioni aritmetiche, etc.)
- si esprimano i comandi condizionali (if-then-else) in modo che, se possibile, un singolo test assembler sia in grado di scegliere tra i due rami;
- ecc.
Nella relazione finale si mostri chiaramente la percentuale di tempo guadagnata con tali modifiche rispetto al codice presentato con la relazione n. 1.
E’ ammesso l’uso dei seguenti linguaggi di programmazione: Pascal, C, C++, Java.
Si deve consegnare una relazione analitica che comprenda:
- obiettivi dell’esperimento;
- metodologia dell’esperimento;
- strumenti usati;
- tabelle e grafici riepilogativi e comparativi;
- conclusioni;
- listati completi.
I gruppi possono contenere al piu’ tre componenti.