Qual è il significato della regola 90/10 di ottimizzazione del programma?

67

Secondo Wikipedia, la regola 90/10 di ottimizzazione del programma afferma che "il 90% del tempo di esecuzione di un programma viene impiegato nell'esecuzione del 10% del codice" (vedere il secondo paragrafo qui ).

Davvero non lo capisco. Cosa significa esattamente questo? Come si può spendere il 90% del tempo di esecuzione solo eseguendo il 10% del codice? E allora l'altro 90% del codice? Come possono essere eseguiti solo nel 10% delle volte?

    
posta Rakshith Ravi 25.10.2016 - 10:09
fonte

9 risposte

184

Ci sono due principi base in gioco qui:

  • Alcuni codici vengono eseguiti molto più spesso di altri codici. Ad esempio, alcuni codici di gestione degli errori potrebbero non essere mai utilizzati. Alcuni codici verranno eseguiti solo all'avvio del programma. L'altro codice verrà eseguito più e più volte durante l'esecuzione del programma.
  • Alcuni codici impiegano molto più a lungo di altri codici. Ad esempio, una singola riga che esegue una query su un database o un file da Internet richiederà probabilmente più tempo di milioni di operazioni matematiche.

La regola 90/10 non è letteralmente vera. Varia a seconda del programma (e dubito che ci sia qualche base per i numeri specifici 90 e 10, qualcuno probabilmente li ha tirati fuori dal nulla). Ma il punto è, se hai bisogno che il tuo programma funzioni più velocemente, probabilmente solo un numero limitato di righe è significativo per farlo accadere. Identificare le parti lente del tuo software è spesso la parte più importante dell'ottimizzazione.

Questa è un'informazione importante, e significa che le decisioni che sembrano controintuitive per un nuovo sviluppatore possono spesso essere corrette. Ad esempio:

  • C'è un sacco di codice che non vale il tuo tempo per rendere "migliore" , anche se sta facendo le cose in modo stupido e semplicistico. Potresti scrivere un algoritmo di ricerca più efficiente per l'applicazione XYZ? Sì, ma in realtà un semplice confronto di ogni valore richiede una quantità trascurabile di tempo, anche se ci sono migliaia di valori. Quindi non ne vale la pena. Può essere difficile per i nuovi sviluppatori evitare l'ottimizzazione non necessaria, perché nel loro programma di laurea è stato dedicato molto tempo alla scrittura dell'algoritmo "corretto" (che significa più efficiente). Ma nel mondo reale, l'algoritmo corretto è qualsiasi che funzioni e funzioni abbastanza velocemente.
  • Le modifiche che rendono il tuo codice molto più lungo e più complesso possono ancora essere un vantaggio in termini di prestazioni. Ad esempio, nell'applicazione FOO potrebbe valere la pena aggiungere centinaia di righe di nuova logica, solo per evitare una singola chiamata al database.
risposta data 25.10.2016 - 10:31
fonte
21

Questa non è una legge della natura, ma una regola empirica nata da una vasta esperienza. È anche conosciuta come la regola 80/20, ed è sempre e solo un'approssimazione approssimativa.

Loop, rami e altro controllo del flusso.

Ogni luogo che ha un if, avrai un ramo che viene preso più spesso dell'altro ramo. Quindi più tempo di esecuzione è dedicato all'esecuzione di quella parte del programma, e non l'altra parte.

Ogni luogo che ha un ciclo che viene eseguito più di una volta, hai un codice che viene eseguito più del codice circostante. Quindi più tempo è trascorso lì.

Ad esempio, prendi in considerazione:

def DoSomeWork():
    for i in range(1000000):
        DoWork(i)
    except WorkExeption:
        print("Oh No!")

Qui print("Oh No!") verrà eseguito sempre al massimo una volta e spesso mai, mentre DoWork(i) si verificherà circa un milione di volte.

    
risposta data 25.10.2016 - 10:33
fonte
16

Loop.

Sono tentato di fermarsi qui! : -)

Considera questo programma

1. do_something

2. loop 10 times
3.    do_another_thing

4.    loop 5 times
5.        do_more_stuff

La riga 1 viene eseguita una volta mentre la riga 3 viene eseguita 10 volte. Guardando ogni riga a sua volta

1 1   0.8%
2 10  8.3%
3 10  8.3%
4 50 41.3%
5 50 41.3%

Due linee rappresentano l'83% del tempo di esecuzione (supponendo che tutte le linee impieghino circa lo stesso tempo per essere eseguite. Quindi il 40% del programma richiede > 80%.

Con esempi più grandi del mondo reale, questo aumenta in modo tale che solo una piccola quantità di linee rappresenta gran parte del tempo di esecuzione.

La regola 90/10 (o come talvolta è stata messa 80/20) è una "regola del pollice" - solo approssimativamente vera.

Vedi anche il principio di Pareto

    
risposta data 25.10.2016 - 10:57
fonte
5

Come hai chiesto solo sul tempo di esecuzione, questo esempio potrebbe essere utile:

int main() {
    sleep(90); // approximately 10% of the program.
    // other 90% of the program:
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    return 0;
}

Se vuoi essere un po 'più serio, significa che nel codice della vita reale si chiama quasi sempre una funzione pesante in un ciclo (anziché sleep(90); ), mentre il resto il 10% delle volte si esegue qualche passaggio singolo calcoli.

Un altro esempio è la gestione degli errori in alcuni servizi HA. Qualsiasi servizio altamente disponibile è progettato per funzionare infinito quantità di tempo in condizioni normali. Funziona normalmente per il 99% del tempo, ma occasionalmente, in caso di errore, esegue alcuni errori di gestione e ripristino, che possono essere anche più complessi dal punto di vista logico.

    
risposta data 25.10.2016 - 10:25
fonte
3

Il ragionamento 90/10 significa che una piccola parte del tuo codice sarà ripetuta o utilizzata più di altre. Questo è spesso usato per suggerire che dovresti concentrare il 90% del tuo sforzo di sviluppo / ottimizzazione in questo 10% del tuo codice.

Pensa a un normale processore di testo, come Microsoft Word o OpenOffice :

  • La finestra di dialogo delle preferenze, non è molto utilizzata;
  • Le subroutine che disegnano caratteri vengono utilizzate sempre.

Questo detto è anche usato nelle scienze della gestione ... Questa è una lezione per la vita stessa ... Significato: concentrati la maggior parte dei tuoi sforzi dove ti dà più risultati.

    
risposta data 25.10.2016 - 16:10
fonte
2

Immagina un programma come questo:

print "H"
print "e"
print "l"
print "l"
print "o"
for i=0 to 1,000,000
    print "How long now?"
next
print "B"
print "y"
print "e"

Notate come ci sono 11 linee qui dove 3 su 11 sono il ciclo for, dove viene impiegato quanto tempo su questo pezzo di codice piuttosto piccolo? Un po 'mentre le altre 8 linee stanno semplicemente stampando un singolo carattere. Quindi, fai attenzione che mentre alcuni codici potrebbero essere brevi, questo non ti dice quanto spesso viene eseguito e quanto tempo ci vuole.

    
risposta data 25.10.2016 - 10:30
fonte
0

Oltre al ciclo, come menzionato da altre grandi risposte, ci sono anche dei principi ASCIUTTI da considerare. Ben scritto, il codice Object Oriented ha molte parti riutilizzabili. Le parti che vengono riutilizzate, per definizione, vengono utilizzate almeno due volte più spesso di qualcosa che viene eseguita una sola volta. Se hai un sacco di codice OO, potresti potenzialmente riutilizzare alcune classi e metodi molte volte, e qualche altro pezzo di codice solo una volta.

Come accennato in altre risposte, è probabilmente meglio spendere sforzi per rendere il codice che viene utilizzato più spesso meglio del miglioramento del codice che viene utilizzato solo una volta.

    
risposta data 25.10.2016 - 18:11
fonte
0

Questa non è una regola, è solo un tizio che ha modificato Wikipedia con un paio di numeri tirati fuori dal nulla e l'ha definita una regola. Paragonare con il principio di Pareto, che è più saldamente stabilito in altri contesti. Mi piacerebbe vedere quali ricerche sono state fatte (se ce ne sono state) sulla precisione di questa "regola".

Ma fondamentalmente la risposta alla tua domanda è, alcuni codici vengono eseguiti molto più frequentemente di altri codici. I loop sono spesso la ragione di questo. Altre ragioni sono chiamate che richiedono tempo, ad es. a risorse esterne come servizi Web o supporti di archiviazione.

    
risposta data 26.10.2016 - 20:59
fonte
0

È una reinterpretazione del "principio di Pareto", che afferma "per molti eventi, circa l'80% degli effetti proviene dal 20% delle cause.", noto anche come la regola 80/20. Questa regola è principalmente applicata all'economia, quindi ha senso che sarebbe stata pensata per la programmazione.

È solo uno schema che è stato osservato per un lungo periodo di tempo.

Ecco un video molto bello su pattern come questo, e spiega anche il principio di Pareto.

link

    
risposta data 29.10.2016 - 06:52
fonte

Leggi altre domande sui tag