Lezione 2

Introduzione

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

L'esercizio

Poi dovrete sperimentare il programma sui dei file di diversa dimensione per verificare come il tempo impiegato per il riordinamento varia con la dimensione effettiva del vettore e stimare quindi l'ordine di complessita` dell'algoritmo.
Per chi ha tempo si potra' anche confrontare diversi algoritmi.

Infine vedremo come organizzare la compilazione nel caso di progetti complessi.

main

La strutture del main potrebbe essere la seguente:

#include <iostream>

void ordina( int , float[] );

int main() {
   /* Dichiarazione delle variabili e dimensionamento del vettore di float */
   while ( cin >> v[i] ) { /* lettura dei dati ed inserimento nel vettore */
   }
   ordina(...); /* invocazione della funzione di ordinamento */
   /* stampa con del vettore dopo l'ordinamento */
   return 0; /* Bisogna fornire un valore di ritorno */
}

Per una dichiarazione sono importanti solo i tipi degli argomenti e del valore di ritorno. Tuttavia dare un nome agli argomenti puo` 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 piu' semplice:
int ordina(int N, float v[]);
e' gia' abbastanza autoesplicativa.

Una volta scritto il programma principale possiamo provare a compilarlo. Non possiamo pero' fornire un eseguibile, perche' ci manca un'implementazione della funzione ordina (ovvero qualcosa che dica al compilatore come tale funzione e' fatta). Quindi dobbiamo fermarci allo stadio di semplice compilazione del g++:
g++ -c ordinamenti.cxx
che crea un file oggetto, ordinamenti.o.

Una costruzione importante

while ( cin>>v[i] ) {
/* codice da ripetere per ogni riga */

In C++ tutto e' una funzione ed ogni funzione ha un suo valore di ritorno (al limite di tipo void).

Quando usiamo l'operatore >> in realtà stiamo invocando una funzione che effettua le seguenti operazioni:

1. legge da cin un valore e lo inserisce nella variabile v[i];
2. restituisce come valore di ritorno cin, oppure 0 se l'operazione di lettura fallisce.

Quindi, dopo aver valutato l'espressione cin<<v[i], il programma riceve il valore di ritorno che, se la lettura e` riuscita e` cin, diverso da 0 e quindi vero, secondo le convezioni del C. Se la lettura non e` riuscita, invece e` 0, quindi falso.

Ora, noi vogliamo andare avanti a leggere il file fin tanto che e` possibile, e, quando la condizione diventa falsa perche' si e` raggiunta la fine del file o si e` incontrato un errore, terminare la lettura e proseguire con le operazioni successive del programma.

La costruzione mostrata quindi fa quello di cui abbiamo bisogno ma con una struttura abbastanza compatta, utile nel caso di letture di dati molto semplici.
Come esercizio, provate a scrivere lo stesso ciclo in una forma equivalente, magari con piu` istruzioni, ma piu` leggibile, usando i vari metodi degli stream (eof(), good(), bad()...).
E' molto utile avere bene in mente come usare questa costruzione e strutture affini, dato che risultano utilizzabile nel 90% dei temi d'esame.

Nota Bene:

La funzione ordina

void scambia( float& a, float& b ) {
  float temp;
  temp=a;
  a=b;
  b=temp;
}

g++ -c scambia.cxx

Usando l'approccio di tenere funzioni separate, conviene definire un header file scambia.h con la dichiarazione della funzione:

void scambia( float&, float&);

#include "scambia.h"

void ordina(int N, float v[]) {
 /*
  * codice e manipolazione di v
  */
}

Anche questo file, da solo non puo` dare un eseguibile, quindi anche in questo caso bisognera` fermare il g++ dopo la compilazione:
g++ -c algoritmo.cxx
che crea un file algoritmo.o.

La costruzione dell'eseguibile

Test del programma

Per far leggere i file al programma, non e` necessario modificarlo, ma basta ricordarsi l'utilizzo degli operatori di ridirezione > e <:

• < nomefile, indica alla shell di usare il file nomefile come standard input per il comando da eseguire;
• > nomefile, indica alla shell di usare il file nomefile come standard output per il comando da eseguire.

Tempo di esecuzione

time

./algoritmo < file10000.dat > file10000ord.dat   0.12s user 0.00s system 81% cpu 0.147 total

Verificate come si comporta il tempo di CPU variando il numero di dati da 10000 a 100000 e provate a vedere se il comportamento corrisponde a quanto ci si può attendere intuitivamente. Per fare una previsione, ragionate su come scala il numero di confronti da fare in base alla dimensione del vettore originale. Nella maggior parte degli algoritmi che ci si puo` inventare senza ragionarci troppo su, si vede che questo numero e` O(N²)

gprof

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
100.00      0.06     0.06        1    60.00    60.00  ordina(int, float*)
  0.00      0.06     0.00   393323     0.00     0.00  scambia(float&, float&)
  0.00      0.06     0.00        1     0.00     0.00  _GLOBAL__I_main
  0.00      0.06     0.00        1     0.00     0.00  __static_initialization_and_destruction_0(int, int)

La colonna cumulative seconds da` il tempo impiegato nella funzione e nelle sottofunzioni da essa chiamate. La colonna self seconds da` il tempo impiegato solo nella funzione stessa. Sono poi indicate il numero totale di chiamate ed il tempio medio impiegato per rispondere ad una chiamata.

Siccome gprof e` piu` accurato di time, ripetete l'ultimo passo del punto precedente.

Un po' d'ordine: il makefile

Questi vantaggi pero` hanno come prezzo una maggiore complessita` della procedura di compilazione.

Con tre 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 piu` complessa procedura di compilazione e` quella di utilizzare un makefile.

Il makefile e` un normale file di testo (potete crearlo con nedit, l'importante e`che abbia esattamente questo nome). Esso contiene l'informazione di cosa e` 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 sara` fatto cosi':

ordinamenti.o : ordinamenti.cxx
	g++ -c -pg ordinamenti.cxx

scambia.o : scambia.cxx
	g++ -c -pg scambia.cxx

algoritmo.o : algoritmo.cxx
	g++ -c -pg algoritmo.cxx

algoritmo : ordinamenti.o scambia.o algoritmo.o
	g++ -o algoritmo -pg ordinamenti.o scambia.o algoritmo.o

Una volta scritto il makefile, il comando
make target
cerca nella directory corrente tale file, al suo interno cerca il target richiesto ed esegue le regole (possono anche esserci piu` 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 cosi' via.
Nel nostro caso, se dopo aver compilato algoritmo, modificassimo una riga di ordinamenti.cxx, allora per ricreare la nuova versione di algoritmo, bastera` fare:
make algoritmo
ed il make provvedera` a ricompilare ordinamenti.o, ma non algoritmo.o perche` non e` 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.

Altri algoritmi

• simple.cxx
• bubblesort.cxx
• quicksort.cxx

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'e` nessun output, se differiscono, la lista delle differenze viene presentata.

Qual e` il programma piu` efficiente? Dovreste accorgevi che quicksort ha una complessita` pari a NlogN.
Come si compara il vostro algoritmo a bubblesort o a simple che sono entrambi di complessita` N²?
Riuscite a capire come funziona quicksort?

Relazione