Lezione 1

Scopo di questa sessione di laboratorio è di ripassare l'utilizzo del compilatore e delle chiamate a funzioni. Verrà  data particolare enfasi allo strutturare i programmi in modo da separarne le varie componenti e favorirne il riutilizzo.

Verificheremo anche l'ordine di complessità  di alcuni algoritmi di ordinamento.

In questa sessione impareremo:

1. a scrivere una funzione per il riordinamento di un generico vettore
2. a leggere da file un numero arbitrario di valori
3. a valutare del tempo di calcolo impiegato in funzione della dimensione del vettore e determinare l'ordine di complessità  di un algoritmo

1. separazione del codice in diversi files
2. passaggio di argomenti per referenza
3. ripasso dell'utilizzo di un makefile

Indice

1. L'esercizio
2. Libreria di algoritmi di ordinamento
3. Il programma principale
4. Misura del tempo di esecuzione
5. Compilazione parziale
6. Altri algoritmi
7. Appendice
   1. Strutture
   2. Ordinamento di strutture
   3. ROOT in interattivo

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 che effettua il riordinamento dovrà essere scritta in un file a parte, in modo che si possa compilare separatamente e costituire la base di una libreria che contenga diversi algoritmi di ordinamento.

Poi dovrete sperimentare il programma sui dei file di diversa dimensione e misurare il tempo impiegato per il riordinamento di vettori dimensione diversa. Dalla dipendenza osservata, si può stimare l'ordine di complessità  dell'algoritmo, ovvero con che legge il tempo di esecuzione aumenta all'aumentare della dimensione del problema. Possiamo anticipare che gli algoritmi di ordinamento più elementari di solito hanno ordine di complessità  N², mentre quelli più performanti hanno ordine NlogN.

Libreria di algoritmi di ordinamento

1. un header file dal suffisso .h con la dichiarazione di tutte le funzioni;
2. un file sorgente, dal suffisso .cxx (o .C) con l'implementazione delle funzioni.

La funzione scambia

#include "ordinamenti.h"

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

Mentre nell'header file va messa la sua dichiarazione:

void scambia( double, double);

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 "ordinamenti.h"

using namespace std;

int main() {
   double 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;
}

#include "ordinamenti.h"

A questo punto si può compilare il programma ed eseguirlo:

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

Il motivo di tale comportamente è che 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:

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

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

void scambia( double*, double*);

void scambia( double&, double&);

scambia(&a,&b);

scambia(a,b);

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 più simile a quella del normale passaggio di una variabile. L'utilizzo dei puntatori inoltre richiede di cambiare la sintassi del programma principale, usando l'operatore & (indirizzo di). Questa modifica non è invece necessaria se si usano dei riferimenti.

In generale è meglio passare riferimenti e limitarsi ai puntatori solo nel caso si voglia accedere a di vettori (come per l'algoritmo di ordinamento). Nel seguito scegliete una delle due sintassi e proseguite l'esercizio, utilizzandola in maniera coerente.

La funzione ordina

void ordina(int, double*);

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, double *vettore);

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

A questo punto possiamo passare all'implementazione della funzione ordina, scrivendola nel file ordinamenti.cxx. La sua struttura sarà  del tipo:

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

  for (int i=0; i<N; i++) { ... }

La strutture del main potrebbe essere la seguente:

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

using namespace std;

int main() {
   /* Dichiarazione delle variabili e dimensionamento del vettore di double */
   while ( cin >> v[i] ) { 
   /* lettura dei dati ed inserimento nel vettore, terminando il ciclo
      alla fine dei dati in ingresso */
      i++;
   }
   ordina(...); 
   /* stampa del vettore dopo l'ordinamento */
   return 0; /* Bisogna fornire un valore di ritorno */
}

Una costruzione importante

   while ( cin >> v[i] ) { 
   ...
   }

In C++ tutto è una funzione, anche la semplice espressione

cin >> v[i]

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).

È molto utile avere bene in mente come usare questa costruzione e strutture affini, dato che compaiono spesso nei temi d'esame.

A questo punto compiliamo il programma:

g++ -o provaordinamenti provaordinamenti.cxx ordinamenti.cxx

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

Misura del tempo di esecuzione

Quando siete sicuri che il programma funziona, potete fargli leggere dei dati da file. Potete trovare dei file già  pronti in /home/comune/lab2/datafiles, con il nome fileN.dat, dove N indica il numero di elementi nel file.

Per far leggere i file al programma, non è 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.

Il comando time

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

./provaordinamenti < file10000.dat > file10000ord.dat  0.92s user 0.00s system 99% cpu 0.926 total

Nota bene: il numero a cui siamo interessati è il tempo allocato all'utente (user).

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.

Provate a mettere le coppie di valori numero di punti e tempo di esecuzione in un file, e poi utilizzare i valori raccolti per disegnare un grafico di ROOT e poi provare a fare un fit polinomiale.

Il seguente programma permette di costruire e disegnare un grafico, sia fornendo i punti ad uno ad uno da terminale, che leggendo i dati in un file:

#include <iostream>

#include "TApplication.h"
#include "TGraph.h"

using namespace std;

// Questo programma crea un grafico leggendo delle
// coppie di valori x ed y dallo standard input o 
// da un file.

int main(int argc, char* argv[]) {
  TApplication myApp("myApp",0,0);
  TGraph *myGraph;
  if ( argc==1 ) {
    // nessun argomento da linea di comando:
    // inserire i punti dallo standard input.
    // (Ctrl-D per terminare)
    double x, y;
    int i=0;
    myGraph = new TGraph();
    while ( cin >> x >> y ) {
      myGraph->SetPoint(i,x,y);
      i++;
    }
  } else if ( argc==2 ) {
    // come primo argomento viene dato il nome di un file:
    // crea il grafico in base ai dati nel file.
    myGraph = new TGraph(argv[1]);
  } else {
    // se il numero di argomenti è diverso da 1 o 2, 
    // stampa l'informazione su come usare il programma.
    cerr << "Usage: " << argv[0] << " [nomefile]" << endl; 
    return -1;
  }
  myGraph->Draw("AL*");
  myApp.Run();
  return 0;
}

1. inserire le istruzioni per compilare questo programma nel makefile
2. usare questo programma per costruire un grafico dei dati raccolti
3. modificarlo per fare un fit ai dati con un polinomio di secondo grado e stampare a video i valori dei parametri ottenuti
4. in base ai parametri osservati, stimate quanto tempo ci metterebbe il vostro algoritmo a riordinare 1000000 di elementi?

Nota bene: per avere un riassunto degli oggetti principali di ROOT e dei relativi metodi, potete consultare la tabella riassuntiva

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 però 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 è 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 può 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 perché 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 è molto esplicativo. In più il compilatore dice sempre a quale riga del file sorgente è presente un errore. Tranne nel caso in cui ci si sia dimenticati un ; al termine di una riga, nel qual caso l'informazione può 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

Anziché 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 ordinamenti.cxx 
g++ -c provaordinamenti.cxx 
g++ -o provaordinamenti provaordinamenti.o ordinamenti.o 

Qual è 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 più, dopo la modifica, non dobbiamo ricompilare tutto, ma ricreare il file oggetto solo della funzione modificata e ripetere la procedura di link che solitamente è molto più 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 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. 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 è questione di decine di secondi.

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

Un po' d'ordine: il makefile

Il makefile è un normale file di testo (potete crearlo con nedit, l'importante è che abbia esattamente questo nome). Esso 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. 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 sarà fatto così:

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

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

provaordinamenti : provaordinamenti.o ordinamenti.o
	g++ -o provaordinamenti provaordinamenti.o ordinamenti.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 più 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 così via.

Nel nostro caso, se dopo aver compilato provaordinamenti, modificassimo una riga di ordinamenti.cxx, allora per ricreare la nuova versione di provaordinamenti, basterà fare:
make provaordinamenti
ed il make provvederà a ricompilare provaordinamenti.o, ma non ordinamenti.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.

Per confrontare il vostro algoritmo con altri, potete scaricare qui di seguito alcuni file contenenti diverse implementazioni di algoritmi di ordinamento:

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

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

provaquicksort : provaquicksort.o ordinamenti.o 
        g++ -o provaquicksort provaquicksort.o ordinamenti.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'è nessun output, se differiscono, la lista delle differenze viene presentata.

Qual è il programma più efficiente? Dovreste accorgevi che quicksort ha una complessità pari a NlogN.

Come si compara il vostro algoritmo a bubblesort o a simple che sono entrambi di complessità N²?

Potrebbe essere un lavoro interessante modificare il programma per fare i grafici in modo che legga un numero arbitrario di file e poi disegni i grafici sovrapposti, in modo da poterli confrontare visivamente.

Provate a sviluppare una soluzione, se non ci riuscite, studiate questo esempio, che mostra anche come cambiare i marker ed i colori dei grafici e settare la scala di grafici in base al valore massimo e minimo dei vari istrogrammi. Se avete fatto tutto correttamente il grafico risultante dovrebbe essere come:

dove la riga nera è l'algoritmo simple, quella rossa bubblesort, quella verde quicksort.

Appendice

struct studente {
  int matricola;
  int voto;
};

Dopo che è stata definita, la nuova struttura può essere considerata semplicemente un nuovo tipo di dato e si possono istanziare strutture singole, puntatori a struttura, vettori di strutture con una sintassi identica a quella dei tipi didati predefiniti:

studente a;
studente *b;
studente c[10000];

a = *b;

a.matricola = b->matricola;
a.voto = b->voto;

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

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

Nota Bene il C++ distingue le funzioni in base al nome ed agli argomenti quindi le due funzioni scambia che abbiamo definito (per double e per studente) possono convivere nello stesso file header e nello stesso file sorgente.

Un esempio di funzione che utilizza l'algoritmo di quicksort per ordinare gli studenti in ordine decrescente di voto e, per studenti con lo stesso voto, in ordine crescente di matricola, è la seguente:

void OrdinaPerVoto( int N, studente v[]) {
  int i, j;
  studente separator;
  if (N<2) return;
  separator = v[N/2];  
  i=0;
  j=N-1;
  while (j>i) {
    while ( v[i].voto>separator.voto || 
	    (v[i].voto==separator.voto && v[i].matricola<separator.matricola)
	    ) i++;
    while ( v[j].voto<separator.voto || 
	    (v[j].voto==separator.voto && v[j].matricola>separator.matricola) 
	    ) j--;
    if (i<j) {
      scambia( v[i], v[j] );
      i++;
    }
  } 
  OrdinaPerVoto(i,v);
  OrdinaPerVoto(N-i,v+i);
}

L'unica piccola difficoltà è che ora, dal file bisogna leggere tutte le componenti di ogni struttura.

Successivamente scrivere una funzione che riordini il file, semplicemente in ordine cresente di numero di matricola.

ROOT in interattivo

Una delle caratteristiche di ROOT è che non consiste solo di una libreria, ma dispone di un interprete interattivo che permette di eseguire direttamente istruzioni in C++.

Per accedere a ROOT in modo interattivo, date da terminale il comando
root
e, dopo una schermata di initializzazione, vi viene dato un prompt dei comandi. Il programmino che è stato fatto per fare il grafico ed il fit dello stesso, può essere sostituito da poche istruzione date a questo prompt. Se indichiamo con nomeFile il nome del file in cui avete scritto le coppie di punti da graficare, potete fare il grafico, disegnarlo e farne il fit con un polinomio di secondo grado dando semplicemente le seguenti istruzioni:

TGraph *myGraph=new TGraph("dati.dat")
myGraph->Draw("AL*")
myGraph->Fit("pol2")

.q