C++ nel dettaglio

Tutorial sul linguaggio C++

Le prime sezioni di questo tutorial trattano il materiale di base già presentato negli ultimi due moduli e forniscono ulteriori informazioni sui concetti avanzati. In questo modulo ci concentriamo sulla memoria dinamica e su ulteriori dettagli su oggetti e classi. Vengono introdotti anche alcuni argomenti avanzati, come ereditarietà, polimorfismo, modelli, eccezioni e spazi dei nomi. Li analizzeremo in seguito nel corso Advanced C++.

Design orientato agli oggetti

Questo è un eccellente tutorial sulla progettazione orientata agli oggetti. Applicheremo la metodologia presentata qui nel progetto di questo modulo.

Impara con l'esempio 3

In questo modulo ci concentriamo su come esercitarti con puntatori, progettazione orientata agli oggetti, array multidimensionali e classi/oggetti. Esamina i seguenti esempi. Non possiamo sottolineare abbastanza che la chiave per diventare un buon programmatore sia la pratica, la pratica, la pratica.

Esercizio 1: più pratica con i puntatori

Se hai bisogno di ulteriore pratica con i puntatori, consulta questa risorsa, che tratta tutti gli aspetti dei puntatori e fornisce molti esempi di programmi.

Qual è l'output del seguente programma? Non eseguire il programma, ma disegna l'immagine della memoria per determinare l'output. 

void Unknown(int *p, int num);
void HardToFollow(int *p, int q, int *num);

void Unknown(int *p, int num) {
  int *q;

  q = #
  *p = *q + 2;
  num = 7;
}

void HardToFollow(int *p, int q, int *num) {
  *p = q + *num;
  *num = q;
  num = p;
  p = &q;
  Unknown(num, *p);
}

main() {
  int *q;
  int trouble[3];

  trouble[0] = 1;
  q = &trouble[1];
  *q = 2;
  trouble[2] = 3;

  HardToFollow(q, trouble[0], &trouble[2]);
  Unknown(&trouble[0], *q);

  cout << *q << " " << trouble[0] << " " << trouble[2];
}

Dopo aver determinato manualmente l'output, esegui il programma per vedere se hai ragione.

Esercizio n. 2: esercitarti ancora con corsi e oggetti

Se hai bisogno di ulteriore pratica con classi e oggetti, qui trovi una risorsa che illustra l'implementazione di due piccole classi. Prenditi un po' di tempo per gli esercizi.

Esercizio 3: array multidimensionali

Prendi in considerazione il seguente programma: 

const int kStudents = 25;
const int kProblemSets = 10;

// This function returns the highest grade in the Problem Set array.
int get_high_grade(int *a, int cols, int row, int col) {
  int i, j;
  int highgrade = *a;

  for (i = 0; i < row; i++)
    for (j = 0; j < col; j++)
      if (*(a + i * cols + j) > highgrade)  // How does this line work?
        highgrade = *(a + i*cols + j);
  return highgrade;
}

int main() {
 int grades[kStudents][kProblemSets] = {
   {75, 70, 85, 72, 84},
   {85, 92, 93, 96, 86},
   {95, 90, 83, 76, 97},
   {65, 62, 73, 84, 73}
 };
 int std_num = 4;
 int ps_num = 5;
 int highest;

 highest = get_high_grade((int *)grades, kProblemSets, std_num, ps_num);
 cout << "The highest problem set score in the class is " << highest << endl;

 return 0;
}

In questo programma è presente una riga contrassegnata come "Come funziona questa linea?" - Riesci a capire? Qui puoi trovare la nostra spiegazione.

Scrivi un programma che inizializza un array di 3 dim e riempia il valore della terza dimensione con la somma di tutti e tre gli indici. Qui è disponibile la nostra soluzione.

Esercizio n. 4: esempio di progettazione OO estesa

Ecco un esempio di progettazione orientata agli oggetti dettagliato, che segue l'intero processo dall'inizio alla fine. Il codice finale è scritto nel linguaggio di programmazione Java, ma sarai comunque in grado di leggerlo a seconda dei progressi compiuti.

Prenditi il tempo necessario per esaminare tutto l'esempio. È un'ottima illustrazione del processo e degli strumenti di progettazione che lo supportano.

Test delle unità

Introduzione

I test sono una parte fondamentale del processo di progettazione del software. Un test delle unità è un particolare tipo di test che verifica la funzionalità di un singolo modulo di codice sorgente.Il test delle unità viene sempre eseguito dall'ingegnere e solitamente viene eseguito contemporaneamente alla programmazione del modulo. I test driver utilizzati per testare le classi Composer e Database sono esempi di test delle unità.

I test delle unità hanno le seguenti caratteristiche. Ha…

  • testare un componente in modo isolato
  • sono deterministici
  • in genere viene mappata su una singola classe
  • evita dipendenze da risorse esterne, ad esempio database, file, reti
  • l'esecuzione rapida
  • possono essere eseguite in qualsiasi ordine

Esistono framework e metodologie automatizzati che forniscono supporto e coerenza per il test delle unità nelle grandi organizzazioni di software engineering. Esistono alcuni sofisticati framework di test delle unità open source, di cui parleremo più avanti in questa lezione. 

I test che vengono eseguiti come parte del test delle unità sono illustrati di seguito.

In un mondo ideale, testiamo quanto segue:

  1. L'interfaccia del modulo viene testata per assicurare che le informazioni fluiscano correttamente in entrata e in uscita.
  2. Le strutture di dati locali vengono esaminate per verificare che i dati vengano archiviati correttamente.
  3. Le condizioni dei confini vengono testate per garantire che il modulo funzioni correttamente in corrispondenza dei limiti che limitano o limitano l'elaborazione.
  4. Testiamo i percorsi indipendenti nel modulo per assicurarci che ogni percorso, e quindi ogni istruzione del modulo, venga eseguito almeno una volta. 
  5. Infine, dobbiamo verificare che gli errori vengano gestiti correttamente.

Copertura del codice

In realtà, non possiamo ottenere una "copertura del codice" completa con i nostri test. La copertura del codice è un metodo di analisi che determina quali parti di un sistema software sono state eseguite (coperte) dalla suite dello scenario di test e quali non sono state eseguite. Se cerchiamo di raggiungere il 100% di copertura, impiegheremo più tempo a scrivere test delle unità che a scrivere il codice effettivo. Valuta la possibilità di ideare test delle unità per tutti i percorsi indipendenti tra i seguenti. Questo può diventare rapidamente un problema esponenziale.

In questo diagramma, le linee rosse non vengono testate, mentre le linee non colorate vengono testate.

Invece di cercare di coprire il 100%, ci concentriamo su test che aumentano la nostra certezza che il modulo funzioni correttamente. Testiamo aspetti quali:

  • Richieste nulle
  • Test dell'intervallo, ad esempio test con valori positivi/negativi
  • Casi limite
  • Casi di errore
  • Test dei percorsi con maggiori probabilità di essere eseguiti la maggior parte delle volte

Framework test delle unità

La maggior parte dei framework di test delle unità utilizza le asserzioni per testare i valori durante l'esecuzione di un percorso. Le asserzioni sono istruzioni che verificano se una condizione è vera. Il risultato di un'asserzione può essere successo, errore non irreversibile o errore irreversibile. Dopo l'esecuzione di un'asserzione, il programma continua normalmente se il risultato è un errore o un errore non irreversibile. In caso di errore irreversibile, la funzione attuale viene interrotta.

I test consistono in codice che configura lo stato o manipola il modulo, insieme a una serie di asserzioni che verificano i risultati previsti. Se tutte le asserzioni in un test hanno esito positivo, ovvero restituiscono true, il test ha esito positivo, altrimenti non riesce.

Uno scenario di test contiene uno o più test. Raggruppamo i test in scenari di test che riflettono la struttura del codice testato. In questo corso, utilizzeremo CPPUnit come framework di test delle unità. Con questo framework possiamo scrivere test delle unità in C++ ed eseguirli automaticamente, generando un report sull'esito positivo o negativo dei test.

Installazione CPPUnit

Scarica il codice CPPUnit da SourceForge. Individua una directory adeguata e inserisci il file tar.gz al suo interno. Quindi, inserisci i seguenti comandi (in Linux, Unix), sostituendo il nome del file cppunit appropriato: 

gunzip filename.tar.gz
tar -xvf filename.tar

Se utilizzi Windows, potresti dover trovare un'utilità per estrarre i file tar.gz. Il passaggio successivo consiste nella compilazione delle librerie. Passa alla directory cppunit. Qui è disponibile un file INSTALL che fornisce istruzioni specifiche. In genere, devi eseguire:

./configure
make install

In caso di problemi, consulta il file INSTALL. In genere, le librerie si trovano nella directory cppunit/src/cppunit. Per verificare che la compilazione abbia funzionato, vai alla directory cppunit/examples/simple e digita "make". Se tutto viene compilato correttamente, non devi fare altro.

C'è un eccellente tutorial disponibile qui. Segui questo tutorial e crea la classe dei numeri complessi e i test delle unità associate. La directory cppunit/examples contiene diversi esempi aggiuntivi.

Perché devo farlo???

Il test delle unità è fondamentale nel settore per diversi motivi. Uno dei motivi per cui hai già familiarità è questo: abbiamo bisogno di un modo per controllare il nostro lavoro durante lo sviluppo del codice. Anche quando stiamo sviluppando un programma molto piccolo, istintivamente scriveremo una sorta di controllo o driver per assicurarci che il nostro programma faccia ciò che ci si aspetta.

Per una lunga esperienza, gli ingegneri sanno che le probabilità che un programma funzioni al primo tentativo sono molto basse. I test delle unità si basano su questa idea rendendo i programmi di test autoverificati e ripetibili. Le asserzioni sostituiscono l'ispezione manuale dell'output. Inoltre, poiché è facile interpretare i risultati (il test ha esito positivo o negativo), i test possono essere eseguiti più volte, fornendo una rete di sicurezza che rende il codice più resiliente al cambiamento.

Mettiamolo in pratica: la prima volta che invii il codice completo in CVS, funziona perfettamente. E continua a funzionare perfettamente per un po' di tempo. Poi un giorno, qualcun altro modificherà il tuo codice. Prima o poi qualcuno potrà violare il tuo codice. Pensi che se ne accorgano da soli? Non probabile. Tuttavia, quando scrivi i test delle unità, esistono sistemi che possono eseguirli automaticamente ogni giorno. Questi sono chiamati sistemi di integrazione continua. Quindi, quando il tecnico X non risolve il tuo codice, il sistema gli invierà email indesiderate finché non lo risolverà. Anche se l'ingegnere X sei TU!

Oltre ad aiutarti a sviluppare software e quindi a mantenerlo sicuro di fronte ai cambiamenti, i test delle unità:

  • Crea una specifica eseguibile e la documentazione che rimane sincronizzata con il codice. In altre parole, puoi leggere un test delle unità per conoscere il comportamento supportato dal modulo.
  • Permette di separare i requisiti dall'implementazione. Dal momento che stai sostenendo un comportamento visibile esternamente, hai l'opportunità di pensarci esplicitamente invece di combinare idee su come implementarlo.
  • Supporta la sperimentazione. Se disponi di una rete di sicurezza a cui comunicare quando interrompi il comportamento di un modulo, è più probabile che tu decida di provare e riconfigurare i tuoi progetti.
  • Migliora i tuoi progetti. Scrivere test delle unità accurati richiede spesso di rendere il codice più testabile. Il codice testabile è spesso più modulare di quello non testabile.
  • Mantiene alta la qualità. Un piccolo bug in un sistema critico può far perdere a un'azienda milioni di dollari o, peggio ancora, la soddisfazione o la fiducia degli utenti. La rete di sicurezza offerta dai test delle unità riduce questa possibilità. Individuando tempestivamente i bug, consentono ai team di QA di dedicare del tempo a scenari di errore più sofisticati e difficili, invece di segnalare errori evidenti.

Dedica un po' di tempo a scrivere i test delle unità utilizzando CPPUnit per l'applicazione di database Composer. Fai riferimento alla directory cppunit/examples/ per assistenza.

Come funziona Google

Introduzione

Immagina un monaco nel Medioevo che guarda le migliaia di manoscritti negli archivi del suo monastero."Dov'è quella di Aristotele..."

biblioteca del monastero

Per sua fortuna, i manoscritti sono organizzati per contenuto e con simboli speciali per facilitare il recupero delle informazioni contenute in ciascuno. Senza questa organizzazione, sarebbe molto difficile trovare il manoscritto pertinente.

L'attività di archiviazione e recupero di informazioni scritte da raccolte di grandi dimensioni è denominata Recupero informazioni (IR). Questa attività è diventata sempre più importante nel corso dei secoli, in particolare con le invenzioni come la carta e la macchina da stampa. Un tempo era un luogo in cui erano occupate solo poche persone. Tuttavia, centinaia di milioni di persone ogni giorno si impegnano a recuperare le informazioni quando utilizzano un motore di ricerca o eseguono ricerche sul computer.

Guida introduttiva al recupero di informazioni

gatto con il cappello

Il dottor Seuss ha scritto 46 libri per bambini in 30 anni. I suoi libri parlavano di gatti, mucche ed elefanti, di chi è, di chi sogghigna e del lorax. Ricordi quali creature erano in quale storia? A meno che tu non sia un genitore, solo i bambini possono raccontarti quale serie di storie di Dr. Seuss contiene queste creature:

(COW e BEE) o CROWS

Applicheremo alcuni modelli classici di recupero delle informazioni per risolvere questo problema.

Un approccio ovvio è la forza bruta: ottieni tutte le 46 storie di Dr. Seuss e inizia a leggere. Per ogni libro, individua quelli che contengono le parole COW e BEE e, allo stesso tempo, cerca i libri che contengono la parola CROWS. I computer sono molto più veloci di noi. Se abbiamo tutto il testo dei libri di Dr. Seuss in formato digitale, ad esempio sotto forma di file di testo, possiamo semplicemente grep tra i file. Per una piccola collezione come i libri del Dr. Seuss, questa tecnica funziona bene.

Tuttavia, ci sono molte situazioni in cui ne abbiamo bisogno di più. Ad esempio, la raccolta di tutti i dati attualmente online è troppo grande per essere gestita da grep. Inoltre, non vogliamo solo i documenti che corrispondono alla nostra condizione, ci siamo abituati a classificarli in base alla loro pertinenza.

Un altro approccio oltre a grep è creare un indice dei documenti di una raccolta prima di eseguire la ricerca. Un indice in formato IR è simile a un indice sul retro di un libro di testo. Creiamo un elenco di tutte le parole (o termini) di ogni storia di Dr. Seuss, escludendo parole come "il", "e" e altri collegamenti, preposizioni e così via (questi sono chiamati stop-word). Rappresentiamo queste informazioni in modo da facilitare la ricerca dei termini e l'identificazione delle notizie in cui si trovano.

Una possibile rappresentazione è una matrice con le notizie nella parte superiore e i termini elencati su ogni riga. Il numero "1" in una colonna indica che il termine compare nella storia di quella colonna.

tabella di libri e parole

Possiamo visualizzare ogni riga o colonna come un vettore di bit. Il vettore di bit di una riga indica in quali storie compare il termine. Il vettore di bit di una colonna indica quali termini compaiono nella storia.

Tornando al nostro problema originale:

(COW e BEE) o CROWS

Prendiamo i vettori di bit per questi termini e prima eseguiamo un AND a livello di bit, quindi eseguiamo un OR a livello di bit sul risultato.

(100001 e 010011) o 000010 = 000011

La risposta: "Mr. Brown può Muu! Puoi?" e "The Lorax". Questa è un'illustrazione del modello di recupero booleano, che è un modello a "corrispondenza esatta".

Supponiamo di dover espandere la matrice in modo da includere tutte le storie del Dr. Seuss e tutti i termini pertinenti al loro interno. La matrice aumenterebbe notevolmente e un'osservazione importante è che la maggior parte delle voci sarebbe 0. Una matrice probabilmente non è la migliore rappresentazione per l'indice. Dobbiamo trovare un modo per memorizzare solo quelli.

Alcuni miglioramenti

La struttura utilizzata nella tecnologia IR per risolvere questo problema si chiama indice invertito. Conserviamo un dizionario di termini e, per ogni termine, abbiamo un elenco che registra i documenti in cui si trovano. Questo elenco è chiamato elenco pubblicazioni. Un elenco collegato singolarmente funziona bene per rappresentare questa struttura come mostrato di seguito.

Se non hai familiarità con gli elenchi collegati, cerca su Google "elenco collegato in C++" e troverai molte risorse che spiegano come crearne uno e come utilizzarlo. Approfondiremo questo aspetto in un modulo successivo.

Tieni presente che utilizziamo gli ID documento (DocIDs) anziché il nome della notizia. Inoltre, ordiniamo questi DocID per facilitare l'elaborazione delle query.

Come elaboriamo una query? Per il problema originale, prima troviamo l'elenco delle pubblicazioni di COW, poi l'elenco delle pubblicazioni ABE. Poi "li uniamo":

  1. Inserisci gli indicatori in entrambi gli elenchi ed esplora contemporaneamente i due elenchi di post.
  2. Ad ogni passaggio, confronta il DocID a cui puntano entrambi i puntatori.
  3. Se sono uguali, inserisci il DocID in un elenco di risultati, altrimenti fai avanzare il puntatore che punta al docID più piccolo.

Ecco come possiamo creare un indice invertito:

  1. Assegna un DocID a ciascun documento che ti interessa.
  2. Per ogni documento, identifica i termini pertinenti (tokenzza).
  3. Per ogni termine, crea un record costituito dal termine, dal docID in cui si trova e da una frequenza nel documento. Tieni presente che, se un determinato termine è presente in più documenti, possono esservi più record.
  4. Ordina i record per termine.
  5. Crea il dizionario e l'elenco di pubblicazioni elaborando i singoli record per un termine e combinando anche i più record per i termini che appaiono in più documenti. Crea un elenco collegato di DocID (in ordine). Ogni termine ha anche una frequenza, ovvero la somma delle frequenze di tutti i record di un termine.

Il progetto

Trova diversi documenti di testo non crittografato lunghi che puoi utilizzare per sperimentare. Il progetto consiste nel creare un indice invertito a partire dai documenti, utilizzando gli algoritmi descritti in precedenza. Dovrai inoltre creare un'interfaccia per l'input delle query e un motore per elaborarle. Puoi trovare un partner di progetto nel forum.

Ecco un possibile processo per completare questo progetto:

  1. La prima cosa da fare è definire una strategia per identificare i termini nei documenti. Fai un elenco di tutte le stop-word che ti vengono in mente e scrivi una funzione che legga le parole nei file, li salvi ed elimini le stop-word. Potrebbe essere necessario aggiungere altre stopword al tuo elenco mentre esamini l'elenco dei termini di un'iterazione.
  2. Scrivi scenari di test CPPUnit per testare la funzione e un makefile per riunire tutto per la build. Controlla i file in CVS, soprattutto se collabori con partner. Ti consigliamo di cercare come rendere disponibile la tua istanza CVS ai tecnici remoti.
  3. Aggiungi l'elaborazione per includere i dati sulla posizione, ossia quale file e dove si trova un termine nel file? Potresti voler calcolare un calcolo per definire il numero di pagina o il numero di paragrafo.
  4. Scrivi scenari di test CPPUnit per testare questa funzionalità aggiuntiva.
  5. Crea un indice invertito e archivia i dati sulla posizione nel record di ogni termine.
  6. Scrivere altri scenari di test.
  7. Progetta un'interfaccia per consentire a un utente di inserire una query.
  8. Utilizzando l'algoritmo di ricerca descritto sopra, elabora l'indice invertito e restituisce i dati sulla posizione all'utente.
  9. Assicurati di includere scenari di test anche per questa parte finale.

Come abbiamo fatto per tutti i progetti, utilizza il forum e la chat per trovare i partner di progetto e condividere idee.

Una funzionalità extra

Una fase di elaborazione comune in molti sistemi IR è chiamata stemming. L'idea principale alla base dello stemming è che gli utenti che cercano informazioni su "recupero" saranno interessati anche ai documenti che contengono informazioni contenenti "recupero", "recuperato", "recupero" e così via. I sistemi possono essere suscettibili di errori a causa di una scarsa radice dell'associazione, pertanto la procedura è un po' complessa. Ad esempio, un utente interessato al "recupero di informazioni" potrebbe ricevere un documento intitolato "Informazioni sui Golden Retriever" a causa della ricerca di radici. Un algoritmo utile per lo stemming è l'algoritmo Porter.

Applicazione: vai dove vuoi!

Dai un'occhiata a questa un'applicazione di questi concetti all'indirizzo Panoramas.dk.