stima empirica delle prestazioni

valutazione empirica delle prestazioni: stima o misura?

• si misurano le prestazioni di di un'implementazione dell'algoritmo
• si procede dalla misura alla stima delle prestazioni dell'algoritmo astraendo (per quanto possibile) dall'influenza di caratteristiche specifiche dell'implementazione
• a tale scopo è spesso necessaria un'analisi del codice, per:
  • capire quali parti siano più critiche per le prestazioni (ad es., cicli più interni)
  • capire se tali criticità siano dovute all'algoritmo o all'implementazione
• problema inerente della stima empirica: dipendenza dall'implementazione
  • per la correttezza metodologica del confronto empirico delle prestazioni di diversi algoritmi, si richiede che le implementazioni abbiano la stessa accuratezza
• 1^o errore frequente nella scelta di un algoritmo:
  • sottovalutare l'importanza delle prestazioni
• 2^o errore frequente nella scelta di un algoritmo:
  • sopravvalutare l'importanza delle prestazioni

analisi degli algoritmi:
motivazioni e obiettivi

• a che serve l'analisi delle prestazioni degli algoritmi:
  • confrontare algoritmi diversi per uno stesso problema
  • stimare le prestazioni di algoritmi indipendentemente dal linguaggio di programmazione e dall'ambiente operativo
  • ottimizzare eventuali parametri degli algoritmi
• cosa serve per l'analisi delle prestazioni degli algoritmi:
  • alcuni (pochi) concetti matematici fondamentali (v. appresso)
  • analisi disponibili in letteratura per algoritmi di ampia applicabilità
• problemi inerenti dell'analisi degli algoritmi:
  • stima approssimata (quella esatta può essere difficile)
  • algoritmi diversi possono avere prestazioni incomparabili (ad es. con ampie e diverse fluttuazioni al variare dell'input)
• quali analisi sono rilevanti:
  • caso medio: si assume che l'input sia generato casualmente
  • caso peggiore: analizzare algoritmo e dati, per determinare l'input appropriato

velocità di crescita delle funzioni

assunto: dipendenza delle prestazioni dell'algoritmo da un parametro primario N

(uno solo, per semplicità e senza perdita di generalità)

il tempo di esecuzione ("costo" più significativo degli algoritmi nella maggior parte dei casi) tipicamente cresce come una delle seguenti funzioni di N, e la rispettiva crescita si dice:

• 1 : costante (crescita zero)
• log N : logaritmica
• N : lineare
• N log N : poco più che lineare ("linearitmica"?)
• N² : quadratica
• N³ : cubica
• 2^N : esponenziale

valori di funzioni comuni

l'andamento, per un campione di valori, di funzioni comunemente incontrate mostra che il loro confronto per piccoli valori di N può essere anche molto diverso da quello per grandi valori di N, determinato dalla velocità di crescita asintotica delle funzioni considerate:

N.B. la fattibilità pratica di un algoritmo è notevolmente sensibile all'ordine di grandezza del tempo di esecuzione: 10⁵ secondi ∼ 1 giorno, 10⁸ secondi ∼ 3 anni

proprietà della funzione logaritmo

definizione: funzione inversa dell'esponenziale

ovvero, log_b x è l'esponente da dare a b per ottenere x :

• b^{log_b x} = x
• log_b b^x = x

dalla definizione discendono le proprietà:

• reciprocità :   log_b a = 1 / log_a b
• additività :     log_b xy = log_b x + log_b y ,     log_b (x /y) = log_b x - log_b y

notazione per basi speciali:

• logaritmo naturale :   ln x = log_e x = ∫₁ ^x dt/t
• logaritmo binario :     lg x = log₂ x

un'applicazione delle approssimazioni intere del logaritmo binario:

• per la codifica binaria di N+1 oggetti distinti occorrono ⌊lg N⌋+1 = ⌈lg(N+1)⌉ bit

esercizi

1. dimostrare che ⌊ lg N ⌋ + 1 = ⌈ lg(N+1) ⌉   per ogni intero positivo N > 0
2. il testo (Sedgewick, 2003, p. 41) propone due metodi simili, espressi da rispettive istruzioni C++, per il calcolo del più piccolo intero maggiore di lg N :
   • for (lgN = 0; N > 0; lgN++, N /= 2) ;
   • for (lgN = 0, t = 1; t < N; lgN++, t += t) ;
   dimostrare che i due metodi non sono equivalenti; più precisamente, trovare e correggere l'errore nel secondo metodo, posto che il valore della variabile intera lgN debba essere, all'uscita dal ciclo, il più piccolo intero maggiore di lg N