Sintesi e sfide: dati composti

Riepilogo

Questa lezione chiude la sesta unità del corso, dedicata ai dati composti. Ricostruisce la catena dei concetti che va dalla sequenza indicizzata al record, passando per la sequenza che cresce, il costo di un algoritmo, la ricerca e l’ordinamento e le tabelle; separa ciò che di tutto questo vale in qualsiasi linguaggio da ciò che è proprio di C++; raccoglie il comportamento indefinito dell’unità, con ciò che ferma la libreria, ciò che ferma il sanitizer e ciò che nessuno segnala; ripete nella sua valutazione d’uscita le abilità della valutazione d’ingresso; e termina con sei sfide che combinano l’unità intera.

Obiettivi di apprendimento

Rappresentare collezioni ed entità con il tipo adeguato (array, vettore, tabella o record), e giustificare la scelta con la forma dei dati.
Elaborare collezioni con algoritmi corretti, scritti a mano e giustificati con un invariante, o presi dalla libreria rispettandone le precondizioni.
Stimare il costo di un algoritmo contandone le operazioni dominanti, e verificare la stima con una misura.
Riconoscere il comportamento indefinito dell’unità (l’accesso fuori dai limiti, il riferimento invalidato, il punto medio che trabocca, la precondizione della libreria violata) e riscrivere il programma senza di esso.
Separare, in ciò che si è appreso nell’unità, ciò che vale in qualsiasi linguaggio da ciò che è proprio di C++.

Ciò che l’unità ha ottenuto

L’unità si era proposta di insegnare a rappresentare collezioni di dati e a elaborarle con gli algoritmi di base, stimando quanto costano. Ci è riuscita appoggiandosi solo su ciò che l’introduzione ha dichiarato di dare per scontato: i cicli con invariante, le funzioni e le loro modalità di passaggio, l’aritmetica degli interi. Il programma dei punteggi, che con cinque variabili taceva i dati in eccesso, si scrive ora con un vettore; e la domanda sui pareggi, che con tutte le coppie richiedeva minuti per un milione di dati, si risolve ordinando e confrontando i vicini.

Array

La lezione Array ha presentato std::array, la sequenza di dimensione fissa, i cui indici contano da zero perché sono offset. Ha stabilito che l’indice $i$ è valido se e solo se $0 \leq i < n$ , che ogni accesso con [] richiede di dimostrarlo con l’invariante del ciclo, e che l’accesso fuori dai limiti è comportamento indefinito, che .at() trasforma in un arresto definito; ha introdotto std::size_t e ha insegnato a leggere gli array C.

Vettori

La lezione Vettori ha presentato la sequenza che cresce con push_back e ha stabilito quando occorre conservare una serie: se qualche decisione su un dato dipende da dati successivi. Ha stabilito le scansioni canoniche (accumulare, filtrare, trasformare) con i loro invarianti e le loro abbreviazioni nella libreria (std::ranges::count, std::ranges::max, std::ranges::fold_left), la regola del passaggio di un vettore, e la differenza tra dimensione e capacità, da cui seguono il costo costante in media di push_back e l’invalidazione dei riferimenti quando il vettore trasloca.

Il costo di un algoritmo

La lezione Il costo di un algoritmo ha aggiunto la seconda domanda: contare l’operazione dominante nel caso peggiore, classificare per ordine di crescita, prevedere l’effetto del raddoppio di $n$ e misurare con std::chrono::steady_clock, con ottimizzazione, senza sanitizer, ripetendo e prendendo la mediana.

Cercare e ordinare

La lezione Cercare e ordinare ha giustificato la ricerca binaria con il suo invariante e la sua misura; ha scritto l’ordinamento per selezione e quello per inserimento, contandone i confronti; ha presentato gli algoritmi della libreria ranges con la precondizione dell’ordine, che nessuno controlla; e ha calcolato quando conviene ordinare prima di cercare.

Tabelle

La lezione Tabelle ha scorso le tabelle per righe e per colonne, ha calcolato la trasposta e il prodotto di matrici, con il suo costo cubico, ha contato vicini senza uscire dai bordi e ha conservato una tabella in un vettore piatto con l’indice $i \cdot \mathit{columns} + j$ .

Record

La lezione Record ha sostituito i vettori paralleli con lo struct, con un valore iniziale in ogni campo; ha insegnato a passare e restituire record, a ordinarli e cercarli per un campo con una proiezione, a ordinare per più criteri con std::ranges::stable_sort e a modellare un problema con record che contengono record e vettori.