venerdì 24 giugno 2011

Sul valore dell'ottimizzazione

Ciao a tutti, oggi voglio parlarvi del valore dell'ottimizzazione, soprattutto algoritmica.

Oggi ho avuto l'occasione di riprendere in mano un vecchio script Python che era utile per calcolare Dijkstra su un grafo definito in un file CSV.

La prima versione: O(2(N^4-N^3))
La prima versione aveva una complessità computazione esagerata, e ora vi spiego perchè:
1) Dijkstra ha complessità O(n^2)
2) I percorsi possibili, escludendo quelli da un nodo a se stesso, in un grafo sono le disposizioni di n elementi di classe 2, ovvero n(n-1)
3) Dato che l'algoritmo necessita, per poter generare un report, sia della distanza minima sia del percorso minimo, Dijkstra viene ricalcolato 2 volte.
Totale: 2n^2*(n(n-1))=2(n^2(n^2-n))=2(n^4-n^3)

Il costo è un tantino troppo alto!
Dato che il costo, come potete benissimo osservare, è troppo alto, mi è venuto in mente che si potevano ottimizzare le chiamate alla funzione calcolante Dijkstra, potendo quindi (dato che aggiorna oggetti globali, quindi sempre accessibili) risparmiare calcolo inutile. Ma come?
Semplice, Dijkstra non necessita di un punto di terminazione (ovvero un parametro che indichi il nodo di arrivo), visitando così tutto il grafo.
Da questa premessa, è facile arrivare alla seconda versione del programma.

Seconda versione: O(n^3)
Ora il costo è nettamente diminuito, dato che ora è possibile evitare di ricalcolare Dijkstra.
In pratica ora il calcolo viene eseguito solo N volte, quindi n*n^2=n^3

Un pesantissimo test: grafo da 120 nodi
Con questo test (generato in maniera del tutto casuale) ho testato i tempi.


questo è il risultato della vecchia versione
C:\Users\delta\Desktop\RoadRagePythonVersion>road_rage.py enormeFileCSV.csv
2011-06-24 11:18:19.192000
28560
2011-06-24 11:23:42.812000

C:\Users\delta\Desktop\RoadRagePythonVersion> 



questo è il risultato della nuova versione
C:\Users\delta\Desktop\RoadRagePythonVersionOptNoParallel>road_rage.py enormeFileCSV.csv
2011-06-24 11:19:22.604000
120
2011-06-24 11:19:34.927000

C:\Users\delta\Desktop\RoadRagePythonVersionOptNoParallel>


Come avrete notato, la seconda versione richiama Dijkstra 120 volte e ci mette ben 12 secondi a macinare il tutto, mentre la vecchia versione fa 28560 chiamate a Dijkstra e utilizza quasi 5 minuti e mezzo per portare a termine il proprio lavoro.


Quindi potete osservare che l'ottimizzazione dei propri progetti è la parte migliore del lavoro, oltre che necessaria! L'ottimizzazione dovrebbe essere però fatta nella fase di progettazione, dove il codice non è ancora stato scritto e si ha tutto il tempo per riflettere sulle possibili ottimizzazioni e l'utilizzo delle strutture dati corrette, permettendo quindi di scrivere codice già ottimizzato.


Stay tuned!


(prossimamente caricherò le due versioni del programma e il file csv, attendete prego :D)