Laboratorio di Programmazione 2

proff. A. Andreazza, E. Spoletini

Universita' degli Studi di Milano

Anno Accademico 2001/2002

Lezione 2

Introduzione

Scopo di questa sessione di laboratorio e' di fare pratica con la definizione di funzioni e delle tecniche per la misura dell'efficienza di diversi algoritmi. Infine verranno dati alcuni suggerimenti su alcuni approcci alla gestione di progetti in C, tipici nei sistemi UNIX.
Questa sessione prevede:
  1. scrittura di un programma per la lettura ed il riordinamento di un vettore
  2. scrittura di una funzione per il riordinamento di un generico vettore
  3. valutazione del tempo di calcolo impiegato in funzione della dimensione del vettore
  4. paragone del vostro algoritmo di ricerca con altri algoritmi
  5. compilazione separata e makefile

Avvisi:

  1. Purtroppo saremmo costretti a continuare a collegarci a labmaster in modo testo. Peccato, ma ve la siete cavata già abbastanza bene.
  2. In compenso non ci sono più parole magiche da digitare (unset DISPLAY, export TERM=vt100), questi comandi verranno eseguiti automaticamente al momento del collegamento.
  3. Vi ricordo che quest'aula può essere utilizzata anche per esercitazioni personali. Controllate il calendario della settimana per sapere quando è disponibile.
  4. Quando riempite i formulari, ricordatevi di cliccare sul pulsante Invia per registrarne il contenuto sul server. Se volete cambiare le risposte, basta che mettiate i vostri nomi nel campo relativi e clicchiate su Recupera.
  5. Siccome state usando un account comune, posizionatevi nella sottodirectory che avete creato la volta scorsa.

L'esercizio

L'esercizio consiste nello scrivere un programma che legge dei numeri reali (max 100000), li immagazzina in un vettore, chiama una funzione che riordina il vettore ed infine stampa il vettore riordinato. La funzione dovrà essere scritta in un file a parte, in modo che si possa facilmente sostituire e compilare separatamente.
Poi dovrete sperimentare il programma sui file file1000.dat, file2000.dat... per verificare come il tempo impiegato per il riordinamento varia con la dimensione effettiva del vettore.
Per chi ha tempo si potrà anche confrontare diversi algoritmi.
Infine vedremo come organizzare la compilazione nel caso di progetti complessi.

main

Per semplicità potremmo scrivere il main in un file ordinamenti.c.
La strutture del main potrebbe essere la seguente: 
#include <stdio.h>
int ordina( int , float[] );
int main() {
  /* Dichiarazione delle variabili e dimensionamento del vettore di float */
  while ( scanf( ... )!=EOF ) {
  /* lettura dei dati ed inserimento nel vettore */
  }
  ordina(...);
  /* invocazione della funzione */
  /* stampa con printf del vettore dopo l'ordinamento */
  return 0; /* Bisogna fornire un valore di ritorno */
}
La seconda riga è una dichiarazione della funzione ordina. Con essa indichiamo al compilatore che ordina è una funzione che ha come primo argomento un intero e come secondo argomento un vettore di float. Essa resituisce un valore intero. Una dichiarazione dice come una funzione appare, non come è fatta. Il compilatore ha bisogno solo di questa informazione, per il momento.
Per una dichiarazione sono importanti solo i tipi degli argomenti e del valore di ritorno. Tuttavia dare un nome agli argomenti può aiutare l'utente a capire cosa attendersi dalla funzione. Ad esempio la riga potrebbe essere anche scritta esplicitamente come: 
int ordina(int NumeroDiComponenti, float vettore[]);
ed in tal caso si capisce cosa indicano entrambi gli argomenti. Ma anche la più semplice: 
int ordina(int N, float v[]);
è già abbastanza autoesplicativa.
Una volta scritto il programma principale possiamo provare a compilarlo. Non possiamo però fornire un eseguibile, perché ci manca un'implementazione della funzione ordina (ovvero qualcosa che dica al compilatore come tale funzione è fatta). Quindi possiamo fermarci allo stadio di semplice compilazione del gcc:
gcc -c ordinamenti.c
che crea un file oggetto, ordinamenti.o.

La funzione ordina

L'implementazione della funzione ordina può essere fatta in un file separato. Supponiamo per semplicità che si chiami algoritmo.c. La sua struttura sarà del tipo: 
int ordina(int N, float v[]) {
  /* 
   * codice e manipolazione di v
   */
  return N; /* dobbiamo fornire un qualche valore di ritorno */
}
A questo punto, all'interno della funzione,N e v sono oggetti noti, con il loro corretto valore e non c'è bisogno di inizializzarli né di dichiarli. Gli elementi del vettore v possono essere indirizzati nel modo usuale: v[0], v[1], ... v[N-1]. Nella vostra funzione ci saranno probabilmente dei cicli for per accedere agli elementi di v:
  for (i=0; i<N; i++) { ... }
e degli scambi dove opportuno:
  temp=v[i]; v[i]=v[j]; v[j]=temp;
Anche questo file, da solo non può dare un eseguibile, quindi anche in questo caso bisognerà fermare il gcc dopo la compilazione:
gcc -c algoritmo.c
che crea un file algoritmo.o.

La compilazione

Per costruire l'eseguibile bisogna mettere insieme tutte le parti. Al gcc è possibile fornire direttamente dei file oggetto. Il gcc in tal caso effettua solo lúltimo stadio della compilazione, ovvero l'invocazione del linkeri
gcc -o algoritmo ordinamenti.o algoritmo.o
Potremmo anche rifare la compilazione dall'inizio con
gcc -o algoritmo ordinamenti.c algoritmo.c
ma questo è un po' uno spreco.
 

Tempo di esecuzione

Per prima cosa si può verificare che il programma funzioni correttamente, inserendo un piccolo numero di dati a mano. Successivamente si possono utilizzare i file file#####.dat che trovate nella home directory. Gli algoritmi di ordinamento di solito hanno un tempo di esecuzione che cresce più che linearmente con la quantità di dati. Anzi, dato il vostro algoritmo, come vi aspettate che il suo tempo di esecuzione cambi con l'aumento dei dati?

time

Il programma time:
time comando
permette di avere un riassunto del tempo utilizzato per eseguire comando, sia il tempo totale che quello effettivo di CPU (che di solito è molto minore, perché le due CPU di labmaster stanno servendo quasi una trentina di utenti). Siccome comando può contenere gli operatori di ridirezione studiati la volta scorsa, potete leggere l'input da file e scaricare l'output su un altro file.
Verificate come si comporta il tempo di CPU variando il numero di dati da 1000 a 10000. Quanto vi aspettereste per 100000 dati? Se vi viene più di un minuto di CPU, è meglio che non proviate a verificare, altrimenti rischiate di bloccare la macchina per tutti gli altri utenti.

gprof

Il difetto di time è che non permette di vedere i dettagli delle singole funzioni, ma a noi non interessa il tempo necessario per eseguire il nostro programma, ma solo quello richiesto dalla funzione ordina (ovvero dal nostro algoritmo di ordinamento). Per avere questo livello di dettaglio (profiling) si può utilizzare il programma gprof, che però richiede di modificare l'eseguibile, ponendo l'opzione -pg ad ogni passo della compilazione:
gcc -pg -c ordinamenti.c
gcc -pg -c algoritmo.c
gcc -pg -o algoritmo ordinamento.o algoritmo.o
Se adesso il programma algoritmo viene eseguito normalmente con
./algoritmo < inputfile > outputfile
oltre al normale file di output, viene creato uno speciale file gmon.out che contiene le informazioni di profiling. Questo file può essere interpetato dal comando gprof,
gprof ./algoritmo gmon.out
che crea una serie di tabelle che forniscono per ogni funzione quante volte è stata chiamata, il tempo impiegato in essa...
Siccome gprof è più accurato di time, ripetete l'ultimo passo del punto precedente.

Un po' d'ordine: il makefile

Qual è il vantaggio che abbiamo ottenuto nel dividere il programma in diversi file? Per prima cosa, se dobbiamo cambiare qualcosa nel formato dell'output o nell'algoritmo di ordinamento, ci basta modificare solo quella funzione, senza doverci rileggere tutto il programma. In più, dopo la modifica, non dobbiamo ricompilare tutto, ma solo il file modificato. Infine, se un nostro amico ci chiede di provare la nostra funzione,  non dobbiamo passargli tutto il programma, ma solo un file.
Questi vantaggi però hanno come prezzo una maggiore complessità della procedura di compilazione.
Con due soli file, sia i vantaggi che gli svantaggi sono minimi, ma non appena si ha a che fare con un progetto che contiene anche solo una decina di funzioni, entrambi gli aspetti diventano significativi e la tecnica per superare parzialmente gli svantaggi della più complessa procedura di compilazione è quella di utilizzare un makefile.
Il makefile contiene l'informazione di cosa è necessario fare per compilare ogni  parte del programma, codificata in un insieme di regole per creare dei file a partire da altri. Nel nostro caso il makefile sarà fatto cosí:

Schema del makefile

Il comando
make target
cerca nella directory corrente un file chiamato makefile, al suo interno cerca il target richiesto ed esegue le regole (possono anche esserci più righe di regole per un target, ma una sola riga di target:dipendenze) ad esso associate. Il make controlla anche che i file da cui dipende il target siano aggiornati e, se non lo sono, provvede ad invocare le regole che servono a ricrearli e cosí via.
Nel nostro caso, se dopo aver compilato algoritmo, modificassimo una riga di ordinamenti.c, allora per ricreare la nuova versione di algoritmo, basterà fare:
make algoritmo
ed il make provvederà a ricompilare ordinamenti.o (ma non algoritmo.o perché non è necessario) e poi a creare di nuovo l'eseguibile.
In tal modo una modifica al codice del programma si propaga nel modo che richiede il minimo sforzo di compilazione.
Provate a costruire il makefile ed a verificare quanto detto.
P.S.: un tipico giochino è quello di chiedere al calcolatore make love. Analizzate le implicazioni filosofiche della risposta.

Altri algoritmi

La creazione del makefile completa la parte obbligatoria dell'esercizio. Chi ha tempo può procedere ad un passo successivo, il confronto tra diversi algoritmi.
Un primo confronto (fattibile solo con il time) è quello di vedere quanto veloce è il vostro algoritmo rispetto al sort che si poteva usare la volta scorsa.
In più potete scaricare alcuni file contenenti diverse implementazioni della funzione ordina: Modificate il makefile in modo da poter creare degli eseguibili con queste funzioni.
Verificate che l'uscita dei diversi programmi sia identica. Per confrontare due file, basta dare il comando:
diff file1 file2
se i due file sono identici non c'è nessun output, se differiscono, la lista delle differenze viene presentata.
Qual è il programma più efficiente?
Come si compara il vostro algoritmo a bubblesort o a simple?
Osereste provare quicksort su un file di 100000 dati?
Riuscite a capire come funziona quicksort? Purtroppo c'è un sacco di C che non avete ancora fatto a lezione.
 

Relazione

Come al solito, prima di lasciare l'aula, siete pregati di riempire un piccolo formulario con domande relative allo svolgimento dell'esercizio.