À quelle fréquence craignez-vous combien de cas devront être traités?

Question

Si vous possédez les éléments suivants:

$var = 3; // we'll say it's set to 3 for this example
if ($var == 4) {
    // do something
} else if ($var == 5) {
    // do something
} else if ($var == 2) {
    // do something
} else if ($var == 3) {
    // do something
} else {
    // do something
}

Si, disons, 80% du temps $ var est égal à 3, vous inquiétez-vous du fait qu'il traverse 4 cas si avant de trouver le cas réel?

Je pense que sur un petit site, ce n'est pas un gros problème, mais qu'en est-il lorsque cette déclaration est exécutée 1 000 fois par seconde?

Je travaille en PHP, mais je pense que la langue n'a pas d'importance.

Answer 1

Voici comment nous l’avons fait lorsque j’écrivais des logiciels pour les systèmes radar. (La vitesse compte dans le radar. C’est l’un des rares endroits où "temps réel" signifie en réalité "réel" au lieu de "rapide".)

[Je vais passer à la syntaxe Python, c'est plus facile pour moi et je suis sûr que vous pouvez l'interpréter.]

if var <= 3:
    if var == 2:
        # do something
    elif var == 3:
        # do something
    else: 
        raise Exception
else:
    if var == 4:
        # do something
    elif var == 5:
        # do something
    else:
        raise Exception

Vos instructions if forment un arbre au lieu d’une liste simple. Lorsque vous ajoutez des conditions à cette liste, vous vous déplacez autour du centre de l'arbre. La séquence plate de n comparaisons prend en moyenne n / 2 étapes. L’arborescence mène à une séquence de comparaisons qui prend des comparaisons log ( n ).

Answer 2

Eh bien, je pense que presque tout le temps , la lisibilité, par exemple, des valeurs ordonnées numériquement aurait préséance sur tout avantage minime que vous pourriez obtenir en réduisant le nombre d'instructions de comparaison.

Cela dit, comme pour toute optimisation:

1. Faites-le fonctionner
2. Mesurez-le
3. Si c'est assez rapide, laissez-le tranquille
4. S'il est trop lent, optimisez-le

Oh, et j'utiliserais probablement un commutateur / boîtier dès le départ! ; -)

Answer 3

Un cas classique dans lequel cela se produit (avec littéralement 5 options comme dans votre message) était dans ffmpeg, dans la fonction decode_cabac_residual. Cela était assez important, car le profilage (très important - n'optimisez pas avant le profilage!) A montré qu'il comptait pour plus de 10-15% du temps passé au décodage vidéo H.264. La déclaration if contrôlait un ensemble d'instructions calculées différemment pour les différents types de résidus à décoder - et malheureusement, la vitesse de lecture était trop grande en raison de la taille du code si la fonction était dupliquée 5 fois pour chacun des 5 types de résidus. résiduel. Au lieu de cela, une chaîne if devait être utilisée.

Le profilage a été effectué sur de nombreux flux de test courants pour les classer en termes de probabilité; le sommet était le plus commun, le bas le moins. Cela a donné un petit gain de vitesse.

Maintenant, en PHP, je soupçonne qu'il y a beaucoup moins de gain de vitesse de style de bas niveau que vous obtiendriez en C, comme dans l'exemple ci-dessus.

Answer 4

Utiliser une instruction switch / case est définitivement le chemin à parcourir ici.

Cela donne au compilateur (interprète) la possibilité d’utiliser une table de sauts pour accéder à la bonne branche sans avoir à effectuer N comparaisons. Pensez-y en créant un tableau d'adresses indexées sous la forme 0, 1, 2, .. alors vous pouvez simplement chercher celle qui convient dans le tableau en une seule opération.

De plus, étant donné que la syntaxe est moins syntaxique dans une instruction case, la lecture est également plus simple.

Mettre à jour: si les comparaisons conviennent pour une instruction switch, il s'agit d'un domaine dans lequel les optimisations guidées par profil peuvent être utiles. En exécutant une génération PGO avec des charges de test réalistes, le système peut générer des informations d'utilisation de branche, puis les utiliser pour optimiser le chemin emprunté.

Answer 5

Plutôt que de répondre à la question PHP, je vais répondre un peu plus généralement. Il ne s’applique pas directement à PHP, car il subira une sorte d’interprétation.

De nombreux compilateurs peuvent convertir des blocs if-elif-elif -... en blocs afin de changer de bloc si nécessaire et les tests dans les parties elif sont assez simples (et le reste de la sémantique est compatible). Pour 3-4 tests, il n'y a pas nécessairement quelque chose à gagner à utiliser une table de saut.

La raison en est que le prédicteur de branche dans la CPU est vraiment efficace pour prédire ce qui se passe. En réalité, la seule chose qui se passe est une pression un peu plus forte sur la récupération d'instructions, mais cela ne va guère bouleverser le monde.

Cependant, dans votre exemple, la plupart des compilateurs reconnaissent que $ var est une constante 3 puis remplacent $ var par 3 dans les blocs if..elif ... Cela rend les expressions constantes, ce qui les rend vraies ou fausses. L'éliminateur de code mort tue toutes les fausses branches et le test de true est également éliminé. Ce qui reste est le cas où $ var == 3. Vous ne pouvez cependant pas compter sur PHP pour être aussi malin. En général, vous ne pouvez pas faire la propagation de $ var mais cela pourrait être possible à partir de certains sites d’appel.

Answer 6

Vous pouvez essayer d’avoir un tableau de blocs de code dans lequel vous appelez. Ensuite, tous les blocs de code ont la même surcharge.

Perl 6:

our @code_blocks = (
  { 'Code Block 0' },
  { 'Code Block 1' },
  { 'Code Block 2' },
  { 'Code Block 3' },
  { 'Code Block 4' },
  { 'Code Block 5' },
);

if( 0 <= $var < @code_blocks.length ){
  @code_blocks[$var]->();
}

Answer 7

Si le code doit faire des tests supplémentaires, il fonctionnera certainement plus lentement. Si les performances sont essentielles dans cette section de code, vous devez commencer par les cas les plus courants.

Je suis normalement d'accord avec la mesure, puis j'optimise " Méthode quand vous ne savez pas si les performances seront suffisamment rapides, mais si le code doit simplement être exécuté aussi vite que possible ET que la solution est aussi simple que de réorganiser les tests, alors je créerais rapidement le code et ferais quelques mesures. après votre départ, assurez-vous que votre hypothèse (c’est-à-dire que 3 se produira 80% du temps) est en fait correcte.

Answer 8

Avec du code où il s'agit uniquement d'une analyse d'égalité, je le déplacerais vers un commutateur / cas, car cela fournit de meilleures performances.

$var = 3; // we'll say it's set to 3 for this example
switch($var)
 {
   case 4:
      //do something
      break;
   case 5:
      //do something
      break;
   case:
      //do something when none of the provided cases match (same as using an else{ after the elseif{
 }

Maintenant, si vous effectuez des comparaisons plus compliquées, je les imbriquerais dans le commutateur ou tout simplement en utilisant le paramètre elseif.

Answer 9

Dans les langages orientés objet, si une option fournit des ifs massifs, cela signifie que vous devez simplement déplacer le comportement (par exemple, vos blocs // faire quelque chose ) vers l'objet contenant la valeur.

Answer 10

Vous seul pouvez savoir si la différence de performances consistant à optimiser l'ordre, ou à le réorganiser pour en faire un arbre binaire, ferait une différence significative. Mais je suppose que vous devrez avoir des millions de fois par seconde, pas des milliers, pour même penser à cela en PHP (et plus encore dans d’autres langues).

Chronométrez. Voyez combien de fois par seconde vous pouvez exécuter l'instruction ci-dessus if / else if / else sans qu'aucune action ne soit entreprise et $ var ne faisant pas partie des choix.