Quelle est la signification de la règle d’optimisation de programme 90/10?

67

Selon Wikipedia, la règle d'optimisation de programme 90/10 stipule que "90% du temps d'exécution d'un programme est consacré à l'exécution de 10% du code" (voir le deuxième paragraphe ici ).

Je ne comprends vraiment pas cela. Qu'est-ce que cela veut dire exactement? Comment peut-on consacrer 90% du temps d'exécution à l'exécution de 10% du code? Qu'en est-il des autres 90% du code alors? Comment peuvent-ils être exécutés dans seulement 10% du temps?

Rakshith Ravi
la source
50
Certaines parties du code peuvent être exécutées plus souvent que d'autres. C'est à cela que servent les boucles, après tout. En pratique, certaines pièces sont presque toujours exécutées beaucoup plus souvent que d’autres.
Kilian Foth
147
Attendez d’entendre la règle 90/10 pour la durée du projet logiciel: «90% du projet occupera les 90% premiers du temps alloué; les derniers 10% du projet occuperont les 90% restants du temps imparti ».
Paul D. Waite
3
Confusion ici: "le temps est passé à exécuter". Tenez compte a++; for(i=0;i<100;i++){b++;} for(i=0;i<100;i++){print(xyz);}. Bien sûr, la première boucle for dépense beaucoup plus que la première déclaration, mais la seconde, une boucle perd environ 1000 fois plus de temps que la première, mais ne s'exécute pas . Il le passe en attente d'impression . Il y a donc une différence entre le temps passé à l' exécution et le temps dont le code est responsable .
Mike Dunlavey
32
@ Paul_D._Waite Je pensais que 90% du projet prenait 90% du temps, 90% de ce qui restait prenait 90% du temps, et ainsi de suite dans une série non convergente jusqu'à la conclusion qu'aucun projet n'est jamais terminé ou complètement corrigé en moins de temps infini.
nigel222
9
Pour des exemples pratiques, quelques codes sur lesquels j'ai travaillé (modèles scientifiques) utilisaient une grande quantité de code (environ 10 000 lignes) pour lire et configurer le modèle, puis effectuaient une boucle de quelques centaines de lignes pour effectuer les calculs réels. Mais cette boucle courte était n ^ 4 (trois dimensions d'espace itérées par plusieurs milliers de pas de temps), le calcul a donc pris plusieurs jours. Donc, le ratio réel était probablement plus
proche de

Réponses:

184

Il y a deux principes de base en jeu ici:

  • Certains codes sont exécutés beaucoup plus souvent que d’autres. Par exemple, certains codes de traitement des erreurs peuvent ne jamais être utilisés. Certains codes seront exécutés uniquement lorsque vous démarrez votre programme. L'autre code sera exécuté à plusieurs reprises pendant l'exécution de votre programme.
  • Certains codes prennent beaucoup plus de temps à exécuter que d'autres. Par exemple, une seule ligne qui exécute une requête sur une base de données ou extrait un fichier d'Internet prendra probablement plus de temps que des millions d'opérations mathématiques.

La règle 90/10 n'est pas littéralement vraie. Cela varie selon les programmes (et je doute que les chiffres 90 et 10 soient fondés; quelqu'un les a probablement tirés au hasard). Mais si vous voulez que votre programme soit plus rapide, seul un petit nombre de lignes est important pour y parvenir. Identifier les parties lentes de votre logiciel est souvent la partie la plus importante de l'optimisation.

Il s’agit là d’un élément important. Cela signifie que les décisions qui semblent contre-intuitives pour un nouveau développeur peuvent souvent être correctes. Par exemple:

  • Il y a beaucoup de code pour lequel il ne vaut pas la peine que vous passiez à l'amélioration , même si vous faites les choses d'une manière simpliste et stupide. Pourriez-vous écrire un algorithme de recherche plus efficace pour l'application XYZ? Oui, mais en réalité, une simple comparaison de chaque valeur prend une quantité de temps triviale, même s'il existe des milliers de valeurs. Donc ça ne vaut tout simplement pas la peine. Il peut être difficile pour les nouveaux développeurs d'éviter une optimisation inutile, car leur programme d'études consacrait beaucoup de temps à l'écriture de l'algorithme "correct" (ce qui signifie le plus efficace). Mais dans le monde réel, le bon algorithme est celui qui fonctionne et fonctionne assez vite.
  • Les modifications qui rendent votre code beaucoup plus long et plus complexe peuvent encore être gagnantes en performances. Par exemple, dans l’application FOO, il peut être utile d’ajouter des centaines de lignes de nouvelle logique, simplement pour éviter un seul appel à la base de données.

la source
6
Il est à noter que, avec des fonctions telles que le tri, il est beaucoup plus rapide (dans le temps de développement) et plus facile de faire un simple imbécile faire la bonne chose dans tous les cas que d’obtenir un élégant élégant entièrement fonctionnel et sans image. (Les seules raisons d'écrire une sorte d'algo en dehors de l'acadamea sont si vous construisez une bibliothèque ou travaillez sur une plate-forme sans aucune…)
StarWeaver
5
Je pense que vous devez ajouter le lien à shouldioptimize.com :)
Ivan Kolmychek
13
Je pense que le 90/10 vient du célèbre principe de 80/20 de Pareto fr.wikipedia.org/wiki/Pareto_principle
fernando.reyes
2
@StarWeaver C'est pourquoi les langages qui rendent l'écriture super efficace aussi facile ou plus facile qu'une sorte de bulle de merde sont importants, comme le C ++. De tels algorithmes et codes "préemballés" peuvent être très fortement optimisés sans causer de complexité au point d'utilisation.
Yakk
6
@ IvanKolmychek Ce site est trompeur. Bien sûr, ce type d'analyse des coûts est un facteur à prendre en compte, mais il existe d'autres facteurs tels que l'expérience utilisateur. Vous pourriez économiser beaucoup d'argent en n'optimisant pas, mais vous pourriez également perdre beaucoup de revenus si les utilisateurs quittaient votre site frustrés.
Jpmc26
20

Ce n'est pas une loi de la nature, mais une règle empirique née d'une vaste expérience. Elle est également connue sous le nom de règle des 80/20 et n’est qu’une approximation approximative.

Boucles, branches et autres contrôles de flux.

Chaque lieu ayant un if, vous aurez une branche prise plus souvent que l’autre. Ainsi, une plus grande partie du temps d’exécution est consacrée à l’exécution de cette partie du programme et non de l’autre.

Chaque endroit qui a une boucle qui s'exécute plus d'une fois, vous avez un code qui est exécuté plus que le code environnant. Ainsi, on passe plus de temps là-bas.

À titre d'exemple, considérons:

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

Ici, la print("Oh No!")volonté ne fonctionnera jamais plus d'une fois, et souvent jamais, alors DoWork(i)qu'elle se produira environ un million de fois.

Caleth
la source
7
L'appeler la règle des 80/20 peut entraîner une confusion avec le principe de Pareto , qui s'applique plus largement que la programmation. Peut-être que 90 et 10 ne sont que des nombres pratiques qui ne se chevauchent pas.
Trichoplax
29
C'est un exemple du principal de Pareto. Les deux paires de nombres sont également arbitraires
Caleth
2
La division 80/20 du principe de Pareto repose sur une base mathématique. Ce ne sont pas juste des figures imaginaires pour représenter "beaucoup" et "un peu".
Moyli
1
@Moyli - Oui, "Il existe une base mathématique à la scission 80/20 ...", mais dans le monde réel, elle ne sera jamais (OK, par coïncidence, rarement) exactement.
Kevin Fegan
2
@trichoplax le principe de pareto s'applique très bien ici. 20% des causes (les lignes de code) causent 80% des effets (le temps d'exécution)
njzk2
16

Boucles.

Je suis tenté de m'arrêter là! :-)

Considérez ce programme

1. do_something

2. loop 10 times
3.    do_another_thing

4.    loop 5 times
5.        do_more_stuff

La ligne 1 est exécutée une fois tandis que la ligne 3 est exécutée 10 fois. En regardant chaque ligne à tour de rôle

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

Deux lignes représentent 83% du temps d'exécution (en supposant que toutes les lignes prennent à peu près le même temps. Donc, 40% du programme prend> 80%.

Avec des exemples plus grands et plus réels, ce nombre augmente, de sorte que seule une petite quantité de lignes représente une grande partie de l'exécution.

La règle 90/10 (ou comme parfois 80/20) est une "règle empirique" - approximativement vraie.

Voir aussi le principe de Pareto

Nick Keighley
la source
2
Au lieu de dire que ce n'est que approximativement vrai, je dirais que dans de nombreux cas, au moins 90% du temps sera consacré à l'exécution d'une infime fraction du code, au maximum 10%. De toute évidence, il serait possible d’avoir des programmes dans lesquels toutes les parties passent à peu près le même temps d’exécution, mais c’est rare.
Supercat
+1 pour référencer le principe de Pareto. Des explications plus détaillées peuvent être vues dans cette fantastique vidéo de Vsauce .
Radu Murzea
5

Comme vous avez posé des questions sur l'heure d'exécution uniquement, cet exemple peut être 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;
}

Pour être un peu plus sérieux, cela signifie que dans le code réel, vous appelez presque toujours une fonction lourde dans une boucle (au lieu de sleep(90);), tandis que les 10% restants effectuent des calculs en une seule passe.

Un autre exemple est la gestion des erreurs dans certains services de haute disponibilité. Tout service hautement disponible est conçu pour fonctionner dans un temps infini dans des conditions normales. Il fonctionne normalement pendant 99% du temps, mais occasionnellement, en cas d'erreur, il exécute des opérations de traitement et de récupération des erreurs, qui peuvent être encore plus complexes logiquement que le service lui-même.

Sergey
la source
Bien, j'espérais que quelqu'un posterait cet exemple extrême, qui montre clairement la différence.
Djechlin
3

Le raisonnement 90/10 signifie qu'une petite partie de votre code sera répétée ou utilisée plus que d'autres. Ceci est souvent utilisé pour suggérer que vous devriez concentrer 90% de vos efforts de développement / optimisation dans ces 10% de votre code.

Pensez à un traitement de texte normal, comme Microsoft Word ou OpenOffice :

  • La boîte de dialogue des préférences n’est pas très utilisée;
  • Les sous-routines qui dessinent des caractères sont utilisées tout le temps.

Ce dicton est également utilisé dans les sciences de gestion ... Ceci est une leçon de la vie elle-même ... Sens: concentrez la plupart de vos efforts là où vous donne plus de résultats.

Lucas
la source
6
Si Microsoft Word est simple, quel est un exemple complexe?
Peter Mortensen
@PeterMortensen cela n'a aucun sens.
Le grand canard
@PeterMortensen Emacs, évidemment.
Muru
2

Imaginez un programme comme celui-ci:

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"

Remarquez comment il y a 11 lignes ici où 3 des 11 sont la boucle for, où combien de temps est consacré à ce morceau de code plutôt petit? Un peu, alors que les 8 autres lignes n’impriment qu’un seul caractère. Ainsi, sachez que, même si certains codes sont courts, ils ne vous disent pas à quelle fréquence il est exécuté ni combien de temps cela prend.

JB King
la source
0

En plus des boucles, comme mentionné par d’autres bonnes réponses, il ya aussi des principes DRY à prendre en compte. Bien écrit, le code orienté objet comporte de nombreuses parties réutilisables. Les pièces réutilisées, par définition, sont utilisées au moins deux fois plus souvent qu’une chose exécutée une seule fois. Si vous avez beaucoup de code OO, vous pourriez potentiellement réutiliser plusieurs classes et méthodes plusieurs fois, et quelques autres morceaux de code une seule fois.

Comme mentionné dans d'autres réponses, il est probablement préférable de consacrer plus d'efforts à l'amélioration du code utilisé plus souvent qu'à l'amélioration du code utilisé une seule fois.

Marshall Tigerus
la source
2
Vous pouvez réutiliser beaucoup de code, mais tout cela peut être exécuté rarement (tout en restant crucial).
Peter Mortensen
@PeterMortensen "crucial mais pas souvent" n'est pas la même chose que "réutilisé presque toutes les secondes et ayant besoin d'être aussi rapide que possible"
The Great Duck
@TheGreatDuck et je ne pense pas que ce soit ce qu'il voulait dire. Parce que vous pouvez avoir du code exécuté rarement, mais que vous voulez que cela se produise le plus rapidement possible. Par exemple, prenons la récupération après erreur. Selon l’application, il peut être utile de prendre un certain temps (5 minutes, une heure, peut-être plus) pour que le système soit à nouveau opérationnel. Cependant, si, par exemple, un système de vol rencontre une erreur, vous le voulez vraiment le plus rapidement possible. Parce que si ça ne marche pas, ça va "tomber" et "s'écraser" dans un sens très littéral.
VLAZ
Cela semble impliquer que DRY nécessite OO, ce qui n'est bien sûr pas vrai. La réutilisation est également facilitée par les fonctions gratuites, etc.
underscore_d
@vlaz c'est vrai, mais le problème, c'est que dans un avion ... TOUT doit courir vite.
Le grand canard
0

Ce n'est pas une règle, c'est juste un type qui a édité Wikipédia avec quelques chiffres tirés de nulle part et appelé cela une règle. Comparez avec le principe de Pareto, qui est plus fermement établi dans d'autres contextes. J'aimerais voir quelles recherches ont été effectuées (le cas échéant) sur l'exactitude de cette "règle".

Mais fondamentalement, la réponse à votre question est que certains codes sont exécutés beaucoup plus souvent que d’autres. Les boucles en sont souvent la raison. D'autres raisons sont des appels chronophages, par exemple vers des ressources externes telles que des services Web ou des supports de stockage.

Brad Thomas
la source
C'est une chose légitime que les gens utilisent en règle générale.
Le grand canard
Si vous suggérez que cette règle est couramment utilisée, j'aimerais bien voir des preuves à ce sujet également! Ou est-ce simplement une autre opinion tirée de nulle part mais sous-entendue factuelle?
Brad Thomas
Si vous lisez réellement l'article de Wikipédia, vous constaterez que la citation mentionnée par le demandeur comporte cette citation: amazon.com/Every-Computer-Performance-Book-Computers/dp/… je ne l'ai jamais vue personnellement en cours d'utilisation, mais votre message a été jugé impoli et rejetant à mon avis, j'ai donc répondu. De toute évidence, 10% est un chiffre inventé par quelqu'un. Je peux en faire le nombre que je veux en rendant mon programme inefficace. Toutefois, qu’il s’agisse ou non d’un terme utilisé en génie logiciel, cela n’est manifestement pas discutable, vu le nombre de personnes qui y souscrivent.
Le grand canard
Eh bien, je ne suis pas sur le point d'aller acheter le livre juste pour voir la recherche à laquelle il est censé faire référence ... pouvez-vous en faire une citation qui montre les preuves? Ou en avez-vous vu aucun?
Brad Thomas
1
@BradThomas: La preuve contre la théorie selon laquelle la règle 90-10 a été inventée par quelqu'un qui a édité Wikipédia est qu'elle a été largement citée, avec les chiffres 90 et 10, de nombreuses années avant la création de Wikipedia; Le vrai principe ne veut pas dire que 10% du code représente 90% du temps d'exécution, mais que dans la plupart des programmes, une petite partie du code - 10% ou moins , représente une si grande partie du temps d'exécution- -90% ou plus qu'une amélioration même de 10% des performances de cette petite partie du code réduirait le temps d'exécution total de plus qu'une amélioration de 1 000 fois.
Supercat
0

Il s'agit d'une réinterprétation du "principe de Pareto", selon lequel "pour de nombreux événements, environ 80% des effets proviennent de 20% des causes", également appelée règle des 80/20. Cette règle s’appliquant principalement à l’économie, il est donc logique qu’elle soit utilisée à des fins de programmation.

C'est simplement une tendance qui a été observée sur une longue période.

Voici une très belle vidéo sur de tels modèles, qui explique également le principe de Pareto.

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

imnota4
la source