Lezione 1

Introduzione

Scopo di questa sessione di laboratorio e' di ripassare l'utilizzo del compilatore e delle chiamate a funzioni.

Verificheremo l'ordine di complessita` di alcuni algoritmi di ordinamento.

Verra` data particolare enfasi allo strutturare i programmi in modo da separarne le varie componenti e favorirne il riutilizzo.

Questa sessione prevede:

1. scrittura di una funzione per il riordinamento di un generico vettore
2. scrittura di un programma per la lettura ed il riordinamento di un vettore
3. valutazione del tempo di calcolo impiegato in funzione della dimensione del vettore e determinazione dell'ordine di complessita` di un algoritmo
4. compilazione separata e makefile
5. paragone del vostro algoritmo di ricerca con altri algoritmi
6. gestione dinamica della memoria.

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.

Imposteremo l'esercizio in modo avere una struttura molto modulare, che permettera` di confrontare facilmente tra di loro diversi algoritmi. Inoltre, per chi avra` tempo modificheremo il programma in modo da togliere la limitazione sul massimo numero di elementi del vettore

main

La strutture del main potrebbe essere la seguente:

#include <iostream>

using namespace std;

int main() {
   /* Dichiarazione delle variabili e dimensionamento del vettore di float */
   while ( 1 ) { 
   /* lettura dei dati ed inserimento nel vettore, terminando il ciclo
      alla fine dei dati in ingresso */
      cin >> v[i];
      if ( cin.eof() ) break;
      i++;
   /* si noti che il controllo sulla fine del file, deve essere fatto
      PRIMA di incrementare i */
   }
   /* invocazione della funzione di ordinamento 
    * per il momento la teniamo commentata, in modo da poter eseguire il 
    * programma per provarlo prima di aver pronto un algoritmo di ordinamento
    */
   // ordina(...); 
   /* stampa con del vettore dopo l'ordinamento */
   return 0; /* Bisogna fornire un valore di ritorno */
}

Una costruzione importante

   while ( 1 ) { 
   /* lettura dei dati ed inserimento nel vettore, terminando il ciclo
      alla fine dei dati in ingresso */
      cin >> v[i];
      if ( cin.eof() ) break;
      /* codice da ripetere per ogni riga */
   }

In C++ tutto e' una funzione, anche la semplice espressione 1 e` una funzione che ritorna il valore 1 che, essendo diverso da 0, corrisponde ad un valore vero. Lasciato a se stesso, il ciclo while(1) andrebbe avanti all'infinito tentando ogni volta di leggere un valore da cin.

Dopo aver tentato di leggere un nuovo valore, dobbiamo controllare se il programma e' arrivato alla fine del file. Quindi valutatiamo l'espressione cin.eof() che e' vera se si e' raggiunta la fine del file o falsa altrimenti. Nel caso sia vera interrompiamo il ciclo infinito con un break.

Nota Bene: l'oggetto cin sa di aver raggiunto la fine del file solo dopo aver tentato di leggere l'oggetto successivo all'ultimo. Quindi l'uscita dal ciclo deve essere fatta immediatamente dopo la lettura, prima di fare ogni operazione che assuma che la lettura sia stata effettuata correttamente (come aumentare di uno il numero di oggetti letti per esempio).

E' molto utile avere bene in mente come usare questa costruzione e strutture affini, dato che risultano utilizzabile nel 90% dei temi d'esame.

A questo punto compiliamo il programma e verifichiamo che funzioni correttamente la parte di input/output: facendo girare il programma, inseriamo un po' di dati e vediamo che al termine dell'input vengono stampati correttamente sullo schermo.

Nota Bene: Per generare un carattere di fine del file dal terminale, bisogna premere la combinazione di tasti Ctrl-D.

La funzione scambia

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

Quando usiamo l'approccio di tenere funzioni in file separati, conviene definire un header file scambia.h con la dichiarazione di tutte le funzioni contenute nel file. nel nostro caso sara` molto semplice, essendoci una sola funzione:

void scambia( float, float);

Per vedere come si comporta, dobbiamo costruire un programma principale per provare questa funzione, ad esempio un file provascambia.cxx contenente un programma principale molto semplice:

#include <iostream>
#include "scambia.h"

using namespace std;

int main() {
   float a, b;
   cout << "Primo numero?" << endl;
   cin  >> a;
   cout << "Secondo numero?" << endl;
   cin  >> b;
   scambia(a,b);
   cout << "Primo numero:   " << a << endl;
   cout << "Secondo numero: " << b << endl;
   return 0;
}

A questo punto si puo` compilare il programma ed eseguirlo:

g++ -o provascambia provascambia.cxx scambia.cxx
./provascambia

Il motivo di tale comportamente e` stato visto a lezione: la funzione scambia ha come argomento due valori, copie iniziali del contenuto delle variabili originali. Questi vengono scambiati all'interno della funzione, ma le variabili orginali non vengono intaccate.

Se vogliamo scambiare effettivamente le variabili originali, dobbiamo passare invece dei valori, delle referenze alle locazioni di memoria in cui questi valori sono immagazzinati. Questo si puo` fare in C++ in due modi:

1. usando dei puntatori;
   in tal caso scambia.cxx assume la forma:

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

   e scambia.h:

   void scambia( float*, float*);

2. usando dei riferimenti.
   in tal caso scambia.cxx assume la forma:

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

   e scambia.h:

   void scambia( float&, float&);

Si noti la piccola differenza di sintassi tra le due implementazioni: esse sono praticamente equivalenti, ma l'utilizzo dei riferimenti invece che dei puntatori ha una forma molto piu` simile a quella del normale passaggio di una variabile. L'utilizzo dei puntatori inoltre richiede di cambiare la sintassi del programma principale invocando scambia con:

scambia(&a,&b);

La funzione ordina

void ordina(int, float*);

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:

void ordina(int NumeroDiComponenti, float *vettore);

void ordina(int N, float v[]);

A questo punto possiamo passare all'implementazione della funzione ordina. Scriviamola in un file dal nome algoritmo.cxx. La sua struttura sara` del tipo:

#include "scambia.h"

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

A questo punto, dobbiamo modificare il programma principale in ordinamenti.cxx per include ordina.h ed inserire un'opportuna chiamata alla funzione ordina.

Possiamo procedere a compilare il programma completo:

g++ -o algoritmo ordinamenti.cxx algoritmo.cxx scambia.cxx

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

time ./algoritmo < file10000.dat > file10000ord.dat 

./algoritmo < file10000.dat > file10000ord.dat  0.92s user 0.00s system 99% cpu 0.926 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²)

Provate a mettere i valori raccolti in un grafico di ROOT e poi provare a fare un fit polinomiale. Come ripasso di ROOT, ecco una macro di esempio:

{
TGraph grafico; 
grafico.SetPoint(0,10000.,????);   // tempo per 10000 punti
grafico.SetPoint(1,20000.,????);   // tempo per 20000 punti
.
.
.
grafico.SetPoint(9,100000.,????);  // tempo per 100000 punti
grafico.Fit("pol2"); // esegui il fit con un polinomio di secondo grado
grafico.Draw("A*");  // disegna i punti del grafico e la funzione risultante
// recupera un puntatore alla funzione di fit e stampa i parametri
TF1* equazione=grafico.GetFunction("pol2"); 
cout << "L'equazione del grafico e': " << equazione->GetParameter(0)
     << " + " << equazione->GetParameter(1) << " * N"
     << " + " << equazione->GetParameter(2) << " * N^2" << endl;
}

In base ai parametri osservati, stimate quanto tempo ci metterebbe il vostro algoritmo a riordinare 1000000 di elementi.

Compilazione parziale

Nella maggior parte degli esercizi dell'anno passato, si procedeva scrivendo tutto in un file e compilando direttamente l'eseguibile, ma l'aver tenuto separati i file, ci permette di usare una strategia diversa per arrivare a costruire un eseguibile.

Per fare questo pero` ci conviene ripassare come funziona la compilazione di un programma.

La compilazione

1. il preprocessore,
2. il compilatore vero e proprio,
3. il linker.

Il preprocessore di fatto effettua delle sostituzioni letterali all'interno del programma, definite da alcune direttive, riconoscibili perche' iniziano con un #.
La direttiva #include inserisce nel file in corso di compilazione il testo di un altro file, di solito un file che contiene le dichiarazioni delle funzioni da usare (come iostream per esempio).

Invece una direttiva
#define PIGRECO 3.1415196
sostituisce tutte le sequenze di caratteri P,I,G,R,E,C,O incontrate nel testo con la sequenza di caratteri 3,.,1,4,1,5,1,9,6, e risulta un modo pratico di inserire delle costanti.
Il #define puo' anche venire usato per definire delle sostituzioni contenti delle parti variabili, ad esempio
#define FUNC(A) sin(A)/A
sostituisce espressioni come FUNC(xyx) con sin(xyz)/xyz.  Questa e' una direttiva molto utile, ma anche subdola: FUNC(x+y) da' il risultato che vi aspettate? Come fare per avere il risultato corretto?

Il compilatore trasforma il codice che abbiamo scritto in una sequenza di istruzioni comprensibili per la macchina (file oggetto). A volte puo' essere utile terminare la compilazione dopo questa fase, utilizzando l'opzione -c del compilatore:
g++ -c -o nomefileoggetto nomefilesorgente
Se il compilatore non riesce a capire che istruzioni generare perche' il file sorgente non rispetta le regole del C++, esso fornisce un errore di sintassi e non crea il file oggetto. Il testo degli errori di sintassi e' molto esplicativo. In piu' il compilatore dice sempre a quale riga dell file sorgente e' presente un errore. Tranne nel caso in cui ci si sia dimenticati un ; al termine di una riga, nel qual caso l'informazione puo' anche risultare piuttosto criptica.

Il linker si preoccupa di aggiungere l'informazione di tutte le funzioni utilizzate dal file oggetto e non implementate esplicitamente al suo interno. Il linker viene chiamato se si invoca il g++ senza l'opzione -c:
g++ -o nomeeseguibile [lista file sorgente] [lista file oggetto] -lfilelibreria1 -lfilelibreria2...

Il comando g++ prevede molte opzioni, che si possono mettere tutte prima del -o. Una particolarmente consigliata e' l'opzione -Wall che scrive un sacco di messaggi su tutte le cose che, sebbene perfettamente legali in C++, suonano un po' strane al compilatore. Questi messaggi chiamati warnings sono molto utili per mettere in evidenza al momento della compilazione molti errori di logica.
 

La costruzione passo passo

Anziche' costruire direttamente l'eseguibile come indicato in precedenza, potremmo svolgere singolarmente i passi indicati, creando dapprima tutti i file oggetto e poi facendone il link:

g++ -c scambia.cxx 
g++ -c ordinamenti.cxx 
g++ -c algoritmo.cxx 
g++ -o algoritmo ordinamenti.o algoritmo.o scambia.o 

Qual e` il vantaggio che abbiamo ottenuto nel dividere il programma in diversi file e compilarli separatamente?

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 piu`, dopo la modifica, non dobbiamo ricompilare tutto, ma ricreare il file oggetto solo della funzione modificata e ripetere la procedura di link che solitamente e` molto piu` veloce della compilazione.

Infine, se un nostro amico ci chiede di provare la nostra funzione, non dobbiamo passargli tutto il programma, ma solo il file che la contiene.

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. Se qualcuno di voi ha provato a compilare a casa il sorgente di ROOT, si sara` reso conto che la compilazione intera del pacchetto richiede parecchie decine di minuti, mentre ricompilare solo un file dopo una modifica e` questione di decine di secondi.

Per ovviare almento parzialmente agli svantaggi della piu` complessa procedura di compilazione, la soluzione standard e` quella di utilizzare un makefile.

Un po' d'ordine: il 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. In pratica potete pensarlo come una sorta di blocco di appunti in cui vi scrivete come si fa a produrre il risultato finale attraverso tutti i passi intermedi.

Nel nostro caso il makefile sara` fatto cosi':

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

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

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

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

Una volta scritto il makefile, il comando
make target
di fatto va a leggere il nostro "blocco degli appunti" ed esegue le istruzioni che gli abbiamo dato:

1. cerca nella directory corrente il makefile,
2. 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.
3. 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

Per capire l'utilita` del sistema di tenere separate tutte le funzioni utilizzate potete toccare con mano quanto sia facile provare un diverso algoritmo di ordinamento. Potete scaricare qui di seguito alcuni file contenenti diverse implementazioni della funzione ordina:

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

quicksort.o : quicksort.cxx
        g++ -c quicksort.cxx

quicksort : quicksort.o ordinamenti.o scambia.o
        g++ -o quicksort ordinamenti.o quicksort.o scambia.o

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²?

Limitazione sulla lunghezza del vettore

La funzione ordina puo` funzionare su un vettore di lunghezza qualunque. E' nel programma principale che abbiamo una limitazione massima alla lunghezza del vettore.

Questa limitazione puo` venire superata utilizzando la gestione dinamica della memoria in C++, mediante gli operatori new e delete.

Si puo` modificare il programma principale nel seguente modo

1. definire una dimensione iniziale del vettore
   int size=1000;
2. inizializzare il puntatore v ad un'area di memoria pari a size numeri di tipo float
   float *v = new float[size];
3. all'interno del ciclo di input, bisogna controllare che non si sia raggiunta la dimensione massima del vettore
   if ( i>=size )
   e, se questo succede, bisogna provvedere ad allocare maggior spazio:
   1. allocare un vettore di dimensione doppia
      float *tmp = new float[2*size];
   2. copiare il vecchio vettore su quello nuovo
      for (int j=0; j<size; j++) tmp[j]=v[j];
   3. rilasciare la zona di memoria corrispondente al vecchio vettore
      delete v;
   4. ed infine far puntare v alla nuova zona di memoria ed aggiornare il valore della dimensione del vettore:
      v=tmp;
      size*=2;

Provare ad implementare il procedimento sopra descritto e verificare che dia il risultato corretto, al prezzo di una penalizzazione nel tempo di esecuzione.

Relazione