Vai al contenuto
Topos Uranos
Italiano

Il costo di un algoritmo

Riepilogo

Fin qui il corso ha giudicato gli algoritmi in base a una sola domanda: fanno ciò che dicono? Questa lezione aggiunge la seconda, che decide se un programma corretto serve in pratica: quanto costa? Il costo si misura prima senza orologio, contando quante volte si esegue l’operazione dominante, e risulta essere una funzione della dimensione nn dei dati. Di questa funzione non importa il valore per un nn dato, ma come cresce: una tabella di nn, nlog⁡nn \log n, n2n^2 e 2n2^n mostra che le differenze tra algoritmi, invisibili con dieci dati, diventano abissi con un milione. La notazione OO si presenta come abbreviazione di questi ordini di crescita, senza definizione formale, con esempi già visti nel corso: Euclide, logaritmico; la somma di un vettore, lineare; confrontare tutte le coppie, quadratico; Fibonacci ingenuo, esponenziale. Poi si misura con l’orologio di <chrono>, std::chrono::steady_clock, e si impara perché una sola misura inganna, perché si misura con ottimizzazione e senza sanitizer, e come si confronta una misura con una previsione: raddoppiando nn, un algoritmo lineare raddoppia il suo tempo e uno quadratico lo quadruplica.

Obiettivi di apprendimento

  1. Contare le operazioni dominanti di un algoritmo con uno o due cicli in funzione della dimensione nn dei dati.
  2. Classificare un algoritmo come costante, logaritmico, lineare, nlog⁡nn \log n o quadratico, e prevedere come cambia il suo tempo raddoppiando nn.
  3. Misurare il tempo di esecuzione con std::chrono::steady_clock e confrontare la misura con la previsione.
  4. Scegliere tra due algoritmi per una data dimensione dei dati, giustificando la scelta con l’ordine di crescita.

Contare le operazioni

La seconda domanda

Le lezioni Progettare cicli corretti e Ricorsione hanno insegnato a dimostrare che un algoritmo è corretto: che termina e che il suo risultato soddisfa la postcondizione. Ora, la lezione Algoritmi numerici ha mostrato due test di primalità ugualmente corretti, uno con circa nn divisioni e l’altro con circa n\sqrt{n}, e la lezione Ricorsione, due modi corretti di calcolare F30F_{30}, uno con 2 692 5372\,692\,537 chiamate e l’altro con 29 somme. Se è così, la correttezza non basta per scegliere: tra due algoritmi corretti, uno può rispondere in un istante e l’altro non terminare prima che la risposta abbia smesso di importare. La seconda domanda che si pone a un algoritmo è, pertanto, quanto costa.

Il costo si potrebbe misurare con un orologio, e la quarta sezione lo farà. Ma il tempo di un’esecuzione dipende dalla macchina, dal compilatore, dalle sue opzioni e da ciò che il computer sta facendo nello stesso momento; da esso non segue nulla sull’algoritmo su un’altra macchina. Ciò che non dipende da nulla di tutto questo è il numero di passi che l’algoritmo compie. Ne segue la prima decisione di questa lezione: misurare il costo contando, e lasciare l’orologio per verificare il conto.

La dimensione e l’operazione dominante

Contare tutti i passi (ogni somma, ogni confronto, ogni incremento dell’indice, ogni accesso alla memoria) sarebbe noioso e inutile, perché quasi tutti accompagnano un passo principale in proporzione fissa. Si sceglie, pertanto, l’operazione dominante: quella che si esegue almeno tante volte quanto qualsiasi altra, a meno di un fattore costante, e che per questo le rappresenta tutte. Nella somma degli elementi di un vettore è la somma; nella ricerca di un massimo, il confronto; in un test di primalità, la divisione. Il numero di volte in cui si esegue si esprime in funzione della dimensione dell’input, che si chiama nn: il numero di elementi del vettore, il numero che si verifica, il numero di cifre.

Un ciclo semplice che scorre un vettore di nn elementi e compie con ciascuno una quantità fissa di lavoro esegue la sua operazione dominante nn volte. Il massimo di un vettore non vuoto, invece, comincia con il primo elemento come candidato e confronta ciascuno degli altri: n−1n - 1 confronti. La differenza tra nn e n−1n - 1 è reale, ma, come si vedrà nella terza sezione, non cambia nulla di ciò che importa.

Il caso peggiore

Alcuni algoritmi non eseguono sempre lo stesso numero di operazioni con dati della stessa dimensione. La ricerca di un valore in un vettore, scorrendolo fino a trovarlo, fa un solo confronto se il valore è nella prima posizione e nn se non c’è. Per parlare del suo costo si sceglie una delle due situazioni, e la scelta abituale è il caso peggiore: il numero massimo di operazioni tra tutti gli input di dimensione nn. La ragione è la stessa per cui un contratto si scrive per tutti gli input che soddisfano la precondizione: il caso peggiore è una garanzia, e il caso migliore, una speranza. Sicché la ricerca lineare costa nn confronti nel caso peggiore, e quando questa lezione dice «il costo» senz’altro, intende quello del caso peggiore.

Cicli annidati

La lezione Cicli ha insegnato a contare le iterazioni di due cicli annidati. Se quello interno fa sempre mm iterazioni per ciascuna delle nn di quello esterno, il corpo interno si esegue n⋅mn \cdot m volte. Se quello interno dipende da quello esterno, si somma riga per riga. Il caso che compare più spesso lavorando con collezioni è quello di tutte le coppie: confrontare ogni elemento con ciascuno di quelli che lo seguono, come quando si cerca se un vettore ha ripetuti.

Programma in C++
#include <print>​int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6}: {:>10} confronti; n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}
Output
n =     10:         45 confronti; n(n - 1)/2 = 45n =    100:       4950 confronti; n(n - 1)/2 = 4950n =   1000:     499500 confronti; n(n - 1)/2 = 499500n =  10000:   49995000 confronti; n(n - 1)/2 = 49995000

Il contatore prende il posto del confronto che farebbe l’algoritmo reale. Nell’iterazione ii del ciclo esterno, quello interno va da i+1i + 1 a n−1n - 1 e fa n−1−in - 1 - i iterazioni; sicché il totale è (n−1)+(n−2)+⋯+1+0(n - 1) + (n - 2) + \cdots + 1 + 0, la somma della lezione Cicli:

∑i=0n−1(n−1−i)=n(n−1)2\sum_{i=0}^{n-1} (n - 1 - i) = \frac{n(n - 1)}{2}

L’output conferma la formula per ogni dimensione. Il contatore è long long perché, a partire da un nn di circa sessantacinquemila, il numero di coppie supera il massimo di int (a 32 bit su questa piattaforma), e la formula moltiplica dopo aver convertito per la stessa ragione: il contatore di un algoritmo quadratico trabocca molto prima dei dati.

Si osservi già ciò che la terza sezione generalizzerà: moltiplicando nn per 10, i confronti si moltiplicano per circa 100. Con dieci dati, 45 confronti; con diecimila, quasi cinquanta milioni.