Was bedeutet die 90/10-Regel zur Programmoptimierung?

67

Laut Wikipedia besagt die 90/10-Regel der Programmoptimierung, dass „90% der Programmausführungszeit für die Ausführung von 10% des Codes aufgewendet werden“ (siehe den zweiten Absatz hier ).

Ich verstehe das wirklich nicht. Was genau bedeutet das? Wie können 90% der Ausführungszeit darauf verwendet werden, nur 10% des Codes auszuführen? Was ist dann mit den anderen 90% des Codes? Wie können sie in nur 10% der Zeit ausgeführt werden?

Rakshith Ravi
quelle
50
Einige Teile des Codes werden möglicherweise häufiger ausgeführt als andere. Das ist es, wofür Loops sind. In der Praxis fast immer einige Teile ausgeführt Weise häufiger als andere.
Kilian Foth
147
Warten Sie, bis Sie die 90/10-Regel für die Dauer des Softwareprojekts hören: „90% des Projekts beanspruchen die ersten 90% der zugewiesenen Zeit. Die letzten 10% des Projekts werden die restlichen 90% der zugewiesenen Zeit in Anspruch nehmen. “
Paul D. Waite
3
Verwirrung hier: "Zeit wird für die Ausführung aufgewendet". Überlegen Sie a++; for(i=0;i<100;i++){b++;} for(i=0;i<100;i++){print(xyz);}. Sicher, die erste for-Schleife verbringt viel mehr Zeit als die erste Anweisung, aber die zweite for-Schleife verbringt ~ 1000x mehr Zeit als die erste for-Schleife, wird aber nicht ausgeführt . Es wird darauf gewartet, gedruckt zu werden . Es gibt also einen Unterschied zwischen der für die Ausführung aufgewendeten Zeit und der Zeit, für die der Code verantwortlich ist .
Mike Dunlavey
32
@ Paul_D._Waite Ich dachte, dass 90% des Projekts 90% der Zeit in Anspruch nehmen, 90% der verbleibenden Zeit weitere 90%, und so weiter, bis eine nicht konvergente Reihe zu dem Schluss kommt, dass es kein Projekt gibt jemals fertig gestellt oder in weniger als unendlicher Zeit vollständig entstört.
Nigel222
9
In praktischen Beispielen verwendeten einige von mir bearbeitete Codes (wissenschaftliche Modelle) eine große Menge an Code (~ 10 KB Zeilen), um das Modell einzulesen und einzurichten, und führten dann eine Schleife durch einige hundert Zeilen durch, um die eigentlichen Berechnungen durchzuführen. Aber diese kurze Schleife war n ^ 4 (drei Raumdimensionen, die durch viele tausend Zeitschritte iteriert wurden), daher dauerte die Berechnung Tage. Das tatsächliche Verhältnis war also wahrscheinlich eher 99% / 1% :-)
jamesqf

Antworten:

184

Hier spielen zwei Grundprinzipien eine Rolle:

  • Einige Codes werden viel häufiger ausgeführt als andere. Beispielsweise wird möglicherweise nie ein Fehlerbehandlungscode verwendet. Ein Teil des Codes wird nur ausgeführt, wenn Sie Ihr Programm starten. Anderer Code wird immer wieder ausgeführt, während Ihr Programm ausgeführt wird.
  • Manche Codes brauchen viel länger als andere. Beispielsweise wird eine einzelne Zeile, in der eine Abfrage in einer Datenbank ausgeführt oder eine Datei aus dem Internet abgerufen wird, wahrscheinlich länger dauern als Millionen mathematischer Operationen.

Die 90/10-Regel ist nicht wörtlich wahr. Es variiert je nach Programm (und ich bezweifle, dass es überhaupt eine Grundlage für die spezifischen Zahlen 90 und 10 gibt; jemand hat sie wahrscheinlich aus dem Nichts gezogen). Aber der Punkt ist, wenn Sie Ihr Programm schneller ausführen müssen, ist wahrscheinlich nur eine kleine Anzahl von Zeilen von Bedeutung, um dies zu erreichen. Das Erkennen der langsamen Teile Ihrer Software ist häufig der größte Teil der Optimierung.

Dies ist eine wichtige Erkenntnis und bedeutet, dass Entscheidungen, die für einen neuen Entwickler als nicht intuitiv erscheinen, häufig richtig sein können. Zum Beispiel:

  • Es gibt viele Codes, für die es sich nicht lohnt, "besser" zu werden , selbst wenn die Dinge dumm und simpel sind. Könnten Sie einen effizienteren Suchalgorithmus für die Anwendung XYZ schreiben? Ja, aber tatsächlich dauert ein einfacher Vergleich jedes Werts eine unbedeutende Zeit, obwohl es Tausende von Werten gibt. Es lohnt sich also einfach nicht. Es kann für neue Entwickler schwierig sein, unnötige Optimierungen zu vermeiden, da in ihrem Studiengang so viel Zeit für das Schreiben des "richtigen" (dh effizientesten) Algorithmus aufgewendet wurde. Aber in der realen Welt, ist der richtige Algorithmus jeder eine , die funktioniert und läuft schnell genug.
  • Änderungen, die Ihren Code viel länger und komplexer machen, können immer noch einen Leistungsgewinn bedeuten. In der Anwendung FOO kann es beispielsweise sinnvoll sein, Hunderte von Zeilen neuer Logik hinzuzufügen, um nur einen einzigen Datenbankaufruf zu vermeiden.

quelle
6
Insbesondere ist es bei Sortierfunktionen viel schneller (in Entwicklungszeit) und einfacher, ein dummes einfaches Algo in allen Fällen zum richtigen Ergebnis zu bringen, als ein elegantes Algo voll funktionsfähig und fehlerfrei zu machen. (Die einzigen Gründe, eine Art Algo außerhalb von Acadamea zu schreiben, sind, wenn Sie eine Bibliothek aufbauen oder auf einer Plattform ohne eine arbeiten ...)
StarWeaver,
5
Ich denke, Sie müssen den Link zu shouldioptimize.com hinzufügen :)
Ivan Kolmychek
13
Ich denke, die 90/10 stammt vom bekannten 80/20 Pareto-Prinzip. En.wikipedia.org/wiki/Pareto_principle
fernando.reyes
2
@StarWeaver Aus diesem Grund sind Sprachen wie C ++ wichtig, die das Schreiben supereffizienter Sortierungen so einfach oder einfacher machen als eine beschissene Blasensortierung. Solche "vorgefertigten" Algorithmen und Code können wirklich stark optimiert werden, ohne dass dies am Verwendungsort zu Komplexität führt.
Yakk
6
@IvanKolmychek Diese Seite ist irreführend. Sicher, diese Art der Kostenanalyse ist ein zu berücksichtigender Faktor, aber es gibt auch andere Faktoren wie die Benutzerfreundlichkeit. Sie können viel Geld sparen, indem Sie nicht optimieren, aber Sie können auch viel Geld verlieren, wenn die Leute Ihre Website frustriert verlassen.
jpmc26
21

Dies ist kein Naturgesetz, sondern eine Faustregel, die aus großer Erfahrung hervorgeht. Sie wird auch als 80/20-Regel bezeichnet und ist immer nur eine grobe Annäherung.

Schleifen, Zweige und andere Flusskontrolle.

An jedem Ort, an dem es ein Wenn gibt, gibt es einen Zweig, der häufiger verwendet wird als der andere Zweig. Daher wird mehr Ausführungszeit für die Ausführung dieses Teils des Programms und nicht des anderen Teils aufgewendet.

An jeder Stelle, an der eine Schleife mehrmals ausgeführt wird, wird mehr Code ausgeführt als der umgebende Code. Dadurch wird mehr Zeit dort verbracht.

Betrachten Sie als Beispiel:

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

Hier print("Oh No!")läuft der Wille immer nur maximal einmal und oft nie, wohingegen der DoWork(i)Wille etwa eine Million Mal vorkommt.

Caleth
quelle
7
Wenn man es die 80/20-Regel nennt, kann dies zu Verwechslungen mit dem Pareto-Prinzip führen , das allgemeiner gilt als nur für die Programmierung. Vielleicht sind 90 und 10 nur praktische Zahlen, die diese Bedeutungsüberlappung nicht haben.
Trichoplax
29
Es ist eine Instanz des Pareto-Prinzipals. Beide Zahlenpaare sind gleichermaßen beliebig
Caleth
2
Es gibt eine mathematische Grundlage für die 80/20 Aufteilung im Pareto-Prinzip. Es sind nicht nur imaginäre Figuren, die "viel" und "wenig" darstellen.
Moyli
1
@Moyli - Ja, "Es gibt eine mathematische Grundlage für die 80/20 Aufteilung ...", aber in der realen Welt wird es niemals (zufällig in Ordnung, selten) genau 80/20 sein.
Kevin Fegan
2
@trichoplax hier gilt das pareto-prinzip sehr gut. 20% der Ursachen (die Codezeilen) verursachen 80% der Effekte (die Laufzeit)
njzk2
16

Schleifen.

Ich bin versucht dort anzuhalten! :-)

Betrachten Sie dieses Programm

1. do_something

2. loop 10 times
3.    do_another_thing

4.    loop 5 times
5.        do_more_stuff

Zeile 1 wird einmal ausgeführt, während Zeile 3 zehnmal ausgeführt wird. Jede Zeile der Reihe nach betrachten

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

Zwei Zeilen machen 83% der Ausführungszeit aus (vorausgesetzt, alle Zeilen benötigen ungefähr die gleiche Ausführungszeit. 40% des Programms benötigen also> 80%.

Bei größeren Beispielen aus der realen Welt steigt dieser Wert, sodass nur eine kleine Anzahl von Zeilen einen Großteil der Laufzeit ausmacht.

Die 90/10-Regel (oder wie manchmal gesagt 80/20) ist eine "Faustregel" - nur annähernd wahr.

Siehe auch Pareto-Prinzip

Nick Keighley
quelle
2
Anstatt zu sagen, dass dies nur annähernd der Fall ist, würde ich sagen, dass in vielen Fällen mindestens 90% der Zeit für die Ausführung eines winzigen Teils des Codes aufgewendet werden - höchstens 10%. Natürlich wäre es möglich, Programme zu haben, bei denen alle Teile ungefähr die gleiche Zeit für die Ausführung aufgewendet haben, aber das ist selten.
Supercat
+1 für die Bezugnahme auf das Pareto-Prinzip. Ausführlichere Erklärungen finden Sie in diesem fantastischen Vsauce-Video .
Radu Murzea
5

Da Sie nur nach der Ausführungszeit gefragt haben, könnte dieses Beispiel hilfreich sein:

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;
}

Wenn Sie es etwas ernst meinen, bedeutet dies, dass Sie im echten Code fast immer eine schwere Funktion in einer Schleife aufrufen (statt sleep(90);), während Sie in den restlichen 10% der Zeit einige Berechnungen in einem Durchgang durchführen.

Ein weiteres Beispiel ist die Fehlerbehandlung in einigen HA-Diensten. Jeder hochverfügbare Dienst ist so konzipiert, dass er unter normalen Bedingungen unendlich lange funktioniert . Es arbeitet normalerweise zu 99% in der Zeit, aber gelegentlich führt es im Fehlerfall eine Fehlerbehandlung und -wiederherstellung durch, die möglicherweise noch komplexer als der Dienst selbst ist.

Sergey
quelle
Schön, ich hatte gehofft, jemand würde dieses extreme Beispiel posten, das den Unterschied deutlich zeigt.
Djechlin
3

Die Argumentation von 90/10 bedeutet, dass ein kleiner Teil Ihres Codes wiederholt oder häufiger verwendet wird als andere. Dies wird oft verwendet, um vorzuschlagen, dass Sie 90% Ihres Entwicklungs- / Optimierungsaufwands auf diese 10% Ihres Codes konzentrieren sollten.

Denken Sie an ein normales Textverarbeitungsprogramm wie Microsoft Word oder OpenOffice :

  • Der Einstellungsdialog wird nicht oft verwendet.
  • Die Unterprogramme, die Zeichen zeichnen, werden ständig verwendet.

Dieses Sprichwort wird auch in den Managementwissenschaften verwendet ... Dies ist eine Lektion für das Leben selbst ... Das heißt: Konzentrieren Sie den größten Teil Ihrer Bemühungen, um mehr Ergebnisse zu erzielen.

Lucas
quelle
6
Wenn Microsoft Word einfach ist, was ist ein Beispiel für ein komplexes?
Peter Mortensen
@PeterMortensen das macht keinen Sinn.
The Great Duck
@PeterMortensen Emacs, offensichtlich.
Muru
2

Stellen Sie sich ein Programm wie dieses vor:

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"

Beachten Sie, dass es hier 11 Zeilen gibt, von denen 3 die for-Schleife sind. Wie viel Zeit wird für diesen kleinen Teil des Codes aufgewendet? Ein bisschen, während die anderen 8 Zeilen nur ein einzelnes Zeichen drucken. Beachten Sie daher, dass einige Codes zwar kurz sind, Sie jedoch nicht wissen, wie oft sie ausgeführt werden und wie viel Zeit sie in Anspruch nehmen.

JB King
quelle
0

Neben dem Schleifen, wie in anderen großartigen Antworten erwähnt, gibt es auch DRY-Prinzipien, die berücksichtigt werden müssen. Gut geschrieben, hat objektorientierter Code viele wiederverwendbare Teile. Die Teile, die per Definition wiederverwendet werden, werden mindestens doppelt so oft verwendet wie etwas, das nur einmal ausgeführt wird. Wenn Sie über viel OO-Code verfügen, können Sie möglicherweise einige Klassen und Methoden mehrmals und einige andere Codeteile nur einmal wiederverwenden.

Wie bereits in anderen Antworten erwähnt, ist es wahrscheinlich besser, den häufig verwendeten Code mit größerem Aufwand zu verbessern, als den Code zu verbessern, der nur ein einziges Mal verwendet wird.

Marshall Tigerus
quelle
2
Sie könnten eine Menge Code wiederverwenden, aber alles könnte selten ausgeführt werden (obwohl es immer noch von entscheidender Bedeutung ist).
Peter Mortensen
@PeterMortensen "entscheidend, aber nicht oft" ist nicht dasselbe wie "fast jede Sekunde wiederverwendet und so schnell wie möglich sein müssen"
The Great Duck
@TheGreatDuck und ich glaube nicht, dass er das gemeint hat. Weil Sie Code haben können , der selten ausgeführt wird, der aber so schnell wie möglich ausgeführt werden soll. Nehmen wir zum Beispiel die Fehlerbehebung. Je nach Anwendung kann es eine Weile dauern (5 Minuten, eine Stunde, möglicherweise mehr), bis das System wieder betriebsbereit ist. Wenn jedoch beispielsweise ein Flugsystem auf einen Fehler stößt, möchten Sie dies wirklich so schnell wie möglich tun. Denn wenn nicht, wird es im wahrsten Sinne des Wortes "untergehen" und "abstürzen".
VLAZ
Dies scheint zu implizieren, dass DRY OO erfordert, was natürlich nicht wahr ist. Die Wiederverwendung wird ebenfalls durch kostenlose Funktionen usw. erleichtert
underscore_d
@vlaz das ist wahr, aber die Sache ist, dass in einem Flugzeug .... ALLES muss schnell laufen.
The Great Duck
0

Das ist keine Regel, das ist nur ein Typ, der Wikipedia mit ein paar Zahlen überarbeitet hat und es als Regel bezeichnet hat. Vergleichen Sie mit dem Pareto-Prinzip, das in anderen Zusammenhängen fester verankert ist. Ich würde gerne sehen, welche Untersuchungen zur Genauigkeit dieser "Regel" durchgeführt wurden (falls vorhanden).

Grundsätzlich lautet die Antwort auf Ihre Frage jedoch: Manche Codes werden viel häufiger ausgeführt als andere. Loops sind oft der Grund dafür. Andere Gründe sind zeitaufwändige Anrufe, z. B. zu externen Ressourcen wie Webservices oder Speichermedien.

Brad Thomas
quelle
Es ist eine legitime Sache, die Menschen als Faustregel verwenden.
The Great Duck
Wenn Sie vermuten, dass dies als Faustregel weit verbreitet ist, wäre ich auch daran interessiert, Beweise dafür zu sehen! Oder ist das nur eine andere Meinung, die aus dem Nichts gezogen, aber als sachlich impliziert wurde?
Brad Thomas
Wenn Sie tatsächlich lesen Wikipedia - Artikel würden Sie das Zitat verwiesen , dass durch die Fragesteller hat dieses Zitat hat: amazon.com/Every-Computer-Performance-Book-Computers/dp/... Ich habe persönlich nie gesehen in Gebrauch ist , aber dein post ist meiner meinung nach unhöflich und abweisend rübergekommen, also habe ich geantwortet. Offensichtlich sind 10% eine Zahl, die jemand erfunden hat. Ich kann es machen, was ich will, indem ich mein Programm ineffizient mache. Ob es sich jedoch um einen Begriff handelt, der in der Softwaretechnik verwendet wird, ist eindeutig unbestreitbar, da hier so viele Menschen mit seiner Existenz einverstanden sind.
Die große Ente
Nun, ich werde das Buch nicht kaufen, nur um die Forschung zu sehen, auf die es angeblich verweist ... können Sie ein Zitat daraus posten, das die Beweise zeigt? Oder haben Sie tatsächlich keine gesehen?
Brad Thomas
1
@BradThomas: Gegen die Theorie, dass die 90-10-Regel von jemandem erfunden wurde, der Wikipedia redigierte, spricht der Umstand, dass sie viele Jahre vor der Existenz von Wikipedia mit den Nummern 90 und 10 häufig zitiert wurde. Das eigentliche Prinzip ist nicht, dass genau 10% des Codes 90% der Laufzeit ausmachen, sondern dass in den meisten Programmen ein kleiner Teil des Codes - 10% oder weniger - einen so großen Teil der Laufzeit ausmacht. -90% oder mehr, dass selbst eine Verbesserung der Leistung dieses kleinen Teils des Codes um 10% die Gesamtausführungszeit um mehr als das 1000-fache reduzieren würde.
Supercat
0

Es ist eine Neuinterpretation des "Pareto-Prinzips", das besagt, dass "für viele Ereignisse ungefähr 80% der Auswirkungen von 20% der Ursachen stammen", auch bekannt als die 80/20-Regel. Diese Regel bezieht sich hauptsächlich auf die Wirtschaft, daher ist es sinnvoll, sie für die Programmierung neu zu definieren.

Es ist nur ein Muster, das über einen langen Zeitraum beobachtet wurde.

Hier ist ein sehr schönes Video zu Mustern wie diesem und es erklärt auch das Pareto-Prinzip.

https://www.youtube.com/watch?v=fCn8zs912OE&ab_channel=Vsauce

imnota4
quelle