Pourquoi les boucles imbriquées sont-elles considérées comme une mauvaise pratique?

Mon conférencier a mentionné aujourd’hui qu’il était possible de "étiqueter" les boucles en Java afin de pouvoir y faire référence lorsqu’il s’agissait de boucles imbriquées. J'ai donc regardé la fonctionnalité car je ne le connaissais pas et de nombreux endroits où cette fonctionnalité a été expliquée ont été suivis d'un avertissement, décourageant les boucles imbriquées.

Je ne comprends pas vraiment pourquoi? Est-ce parce que cela affecte la lisibilité du code? Ou est-ce quelque chose de plus "technique"?

Les boucles imbriquées vont bien tant qu'elles décrivent le bon algorithme.

Les boucles imbriquées ont des considérations sur les performances (voir la réponse de @ Travis-Pesetto), mais parfois c'est exactement le bon algorithme, par exemple lorsque vous devez accéder à toutes les valeurs d'une matrice.

L'étiquetage des boucles en Java permet de rompre prématurément plusieurs boucles imbriquées alors que d'autres méthodes seraient fastidieuses. Par exemple, certains jeux pourraient avoir un morceau de code comme ceci:

Player chosen_one = null;
...
outer: // this is a label
for (Player player : party.getPlayers()) {
  for (Cell cell : player.getVisibleMapCells()) {
    for (Item artefact : cell.getItemsOnTheFloor())
      if (artefact == HOLY_GRAIL) {
        chosen_one = player;
        break outer; // everyone stop looking, we found it
      }
  }
}

Bien que le code comme l'exemple ci-dessus puisse parfois être le moyen optimal d'exprimer un algorithme donné, il est généralement préférable de diviser ce code en fonctions plus petites et de les utiliser returnau lieu de break. Donc, breakavec une étiquette est une faible odeur de code ; faites très attention quand vous le voyez.

Les boucles imbriquées sont souvent (mais pas toujours) des mauvaises pratiques, car elles sont souvent (mais pas toujours) excessives pour ce que vous essayez de faire. Dans de nombreux cas, il existe un moyen beaucoup plus rapide et moins coûteux d’atteindre le but que vous essayez d’atteindre.

Par exemple, si vous avez 100 éléments de la liste A et 100 éléments de la liste B et que vous savez que pour chaque élément de la liste A, un élément de la liste B lui correspond (avec la définition de "match" laissée délibérément obscure). ici), et vous voulez produire une liste de paires, la façon simple de le faire est la suivante:

for each item X in list A:
  for each item Y in list B:
    if X matches Y then
      add (X, Y) to results
      break

Avec 100 éléments dans chaque liste, cela prendra en moyenne 100 * 100/2 (5 000) matchesopérations. Avec plus d'éléments, ou si la corrélation 1: 1 n'est pas assurée, elle devient encore plus chère.

D'autre part, il existe un moyen beaucoup plus rapide d'effectuer une opération comme celle-ci:

sort list A
sort list B (according to the same sort order)
I = 0
J = 0
repeat
  X = A[I]
  Y = B[J]
  if X matches Y then
    add (X, Y) to results
    increment I
    increment J
  else if X < Y then
    increment I
  else increment J
until either index reaches the end of its list

Si vous le faites de cette façon, au lieu du nombre d' matchesopérations length(A) * length(B)sur length(A) + length(B)lesquelles il est basé , il est maintenant basé sur , ce qui signifie que votre code s'exécutera beaucoup plus rapidement.

Une des raisons d'éviter les boucles d'imbrication est qu'il est déconseillé d'imbriquer les structures de blocs trop profondément, qu'il s'agisse de boucles ou non.

Chaque fonction ou méthode doit être facile à comprendre, à la fois son objectif (le nom doit exprimer ce qu’il fait) et ses responsables (il doit être facile de comprendre les éléments internes). Si une fonction est trop compliquée pour être facilement comprise, cela signifie généralement que certains composants internes doivent être décomposés en fonctions distinctes de manière à pouvoir être référencés par nom dans la fonction principale (désormais plus petite).

Les boucles imbriquées peuvent être difficiles à comprendre assez rapidement, bien que certaines imbrications fonctionnent correctement - à condition que, comme d'autres le soulignent, cela ne signifie pas que vous créez un problème de performances en utilisant un algorithme extrêmement (et inutilement) lent.

En fait, vous n'avez pas besoin de boucles imbriquées pour obtenir des limites de performances absurdement lentes. Prenons, par exemple, une seule boucle qui, à chaque itération, prend un élément d'une file d'attente, puis en restitue éventuellement plusieurs, par exemple une recherche approfondie d'un labyrinthe. La performance n’est pas déterminée par la profondeur d’imbrication de la boucle (qui n’est que de 1), mais par le nombre d’articles qui sont mis dans cette file d’attente avant qu’elle ne soit finalement épuisée ( si jamais elle est épuisée). le labyrinthe est.

Dans le cas de nombreuses boucles imbriquées, vous vous retrouvez avec le temps polynomial. Par exemple, étant donné ce pseudo-code:

set i equal to 1
while i is not equal to 100
  increment i
  set j equal to 1
  while j is not equal to i
    increment j
  end
 end

Ceci serait considéré comme un temps O (n ^ 2) qui serait un graphique similaire à:

Où l'axe des ordonnées correspond à la durée nécessaire à votre programme pour se terminer et l'axe des ordonnées à la quantité de données.

Si vous recevez trop de données, votre programme sera si lent que personne ne l'attendra. et ce n’est pas tellement autour de 1000 entrées de données que je pense que cela prendra trop de temps

Conduire un camion de trente tonnes au lieu d'un petit véhicule de tourisme est une mauvaise pratique. Sauf lorsque vous devez transporter 20 ou 30 tonnes de matériel.

Lorsque vous utilisez une boucle imbriquée, ce n'est pas une mauvaise pratique. C'est soit complètement stupide, soit c'est exactement ce dont on a besoin. Tu décides.

Cependant, quelqu'un s'est plaint de l' étiquetage des boucles. La réponse à cela: si vous devez poser la question, n'utilisez pas d'étiquetage. Si vous en savez assez pour décider vous-même, alors vous décidez vous-même.

Il n'y a rien de fondamentalement faux ou nécessairement même mauvais sur les boucles imbriquées. Ils ont cependant certaines considérations et pièges.

Les articles auxquels vous avez été amené, probablement au nom de la brièveté ou en raison d'un processus psychologique appelé brûlure, sautant les détails.

Être brûlé, c'est quand vous avez une expérience négative de quelque chose qui implique que vous l'évitiez. Par exemple, je pourrais couper des légumes avec un couteau bien aiguisé et me couper moi-même. Je pourrais alors dire que les couteaux tranchants sont mauvais, ne les utilisez pas pour couper des légumes afin d’empêcher que cette mauvaise expérience ne se reproduise plus. C'est évidemment très peu pratique. En réalité, il faut juste faire attention. Si vous demandez à quelqu'un d'autre de couper des légumes, vous avez un sens encore plus fort de cela. Si j’ordonnais aux enfants de couper les légumes, j’aurais très envie de leur dire de ne pas utiliser de couteau tranchant, surtout si je ne peux pas les surveiller de près.

Le problème, dans la programmation, est que vous ne rencontrerez pas une efficacité maximale si vous préférez toujours la sécurité en premier. Dans ce cas, les enfants ne peuvent couper que des légumes mous. Confrontés à quoi que ce soit d'autre, ils ne feront que gâcher cela avec un couteau émoussé. Il est important d'apprendre à utiliser correctement les boucles, y compris les boucles imbriquées. Vous ne pouvez pas le faire si elles sont jugées mauvaises et si vous n'essayez jamais de les utiliser.

Comme de nombreuses réponses le soulignent, une boucle for imbriquée est une indication des caractéristiques de performance de votre programme, qui peuvent empirer de façon exponentielle à chaque imbrication. C'est-à-dire O (n), O (n ^ 2), O (n ^ 3) et ainsi de suite, ce qui comprend O (n ^ profondeur) où profondeur représente le nombre de boucles que vous avez imbriquées. À mesure que votre imbrication augmente, le temps requis augmente de manière exponentielle. Le problème, c’est qu’il n’est pas certain que votre complexité dans le temps ou dans l’espace sera simple (bien souvent un * b * c, mais toutes les boucles de nid ne fonctionneront pas tout le temps), pas plus que avoir un problème de performance même si c'est ça.

Pour beaucoup de gens, en particulier les étudiants, les écrivains et les conférenciers qui, pour être francs, programment pour gagner leur vie ou au jour le jour pour des boucles peuvent aussi être des activités auxquelles ils ne sont pas habitués et qui ont entraîné une charge cognitive excessive lors des premières rencontres. C'est un aspect problématique car il y a toujours une courbe d'apprentissage et l'éviter ne sera pas efficace pour convertir les étudiants en programmeurs.

Les boucles imbriquées peuvent se déchaîner, c’est-à-dire qu’elles peuvent être imbriquées très profondément. Si je passe par chaque continent, puis par chaque pays, puis par chaque ville, puis par chaque magasin, puis par chaque étagère, puis par chaque produit si c'est une boîte de haricots à travers chaque haricot et mesure sa taille pour obtenir la moyenne peut voir que va nid très profondément. Vous aurez une pyramide et beaucoup d’espace perdu à partir de la marge gauche. Vous pouvez même finir par sortir de la page.

C’est un problème qui serait historiquement plus important lorsque les écrans étaient petits et de faible résolution. Dans ces cas, même quelques niveaux d'imbrication pourraient réellement occuper beaucoup d'espace. C’est une préoccupation moindre aujourd’hui où le seuil est plus élevé, même s’il peut toujours poser problème si l’emboîtement est suffisant.

Lié est l'argument esthétique. Beaucoup de personnes ne trouvent pas esthétique de boucles imbriquées, contrairement aux dispositions avec un alignement plus cohérent. Cela peut être lié ou non à ce à quoi les gens sont habitués, au suivi oculaire et à d’autres préoccupations. Cependant, il est problématique en ce sens qu'il tend à s'auto-renforcer et peut éventuellement rendre le code plus difficile à lire, car casser un bloc de code et encapsuler des boucles derrière des abstractions telles que des fonctions risquerait également de briser la mise en correspondance du code avec le flux d'exécution.

Il y a une tendance naturelle à ce que les gens sont habitués. Si vous programmez quelque chose de la manière la plus simple, la probabilité de ne pas avoir besoin d'imbrication est la plus élevée, la probabilité d'avoir besoin d'un niveau diminue d'un ordre de grandeur, la probabilité d'un autre niveau diminue à nouveau. La fréquence diminue et signifie essentiellement que plus le nid est profond, moins les sens humains sont entraînés à l’anticiper.

À cela s’ajoute que dans toute construction complexe, dans laquelle une boucle imbriquée peut être envisagée, vous devez toujours vous demander si c’est la solution la plus simple possible, car il est possible qu’une solution manquée nécessite moins de boucles. L'ironie est qu'une solution imbriquée est souvent le moyen le plus simple de produire quelque chose qui fonctionne avec un minimum d'effort, de complexité et de charge cognitive. Il est souvent naturel de nidifier pour des boucles. Si vous considérez par exemple l’une des réponses ci-dessus, la méthode beaucoup plus rapide qu’une boucle for imbriquée est également beaucoup plus complexe et consiste en beaucoup plus de code.

Vous devez prendre beaucoup de précautions, car il est souvent possible d’abstraire ou d’aplatir les boucles, mais le résultat final est un remède pire que la maladie, en particulier si vous ne bénéficiez pas par exemple d’une amélioration mesurable et significative des performances.

Il est très courant que des personnes rencontrent fréquemment des problèmes de performances en association avec des boucles qui indiquent à l’ordinateur de répéter une action plusieurs fois et qui, par nature, sont souvent impliquées dans des goulots d’étranglement en termes de performances. Malheureusement, les réponses à cette question peuvent être très superficielles. Il devient courant pour les gens de voir une boucle et de voir un problème de performance où il n'y en a pas, puis de masquer la boucle sans aucun effet réel. Le code "semble" rapide, mais mettez-le sur la route, mettez le contact, relevez l'accélérateur et examinez l'indicateur de vitesse. Vous constaterez qu'il est toujours aussi rapide qu'une vieille dame promenant son cadre zimmer.

Ce type de dissimulation est similaire à si vous avez dix agresseurs sur votre itinéraire. Si, au lieu d'avoir un itinéraire rectiligne vers l'endroit où vous souhaitez aller, vous l'organisez de manière à ce qu'il y ait un agresseur derrière chaque coin, alors cela donne l'illusion que, lorsque vous commencez votre voyage, il n'y a pas d'agresseurs. Hors de vue, hors de l'esprit. tu vas encore te faire agresser dix fois mais maintenant tu ne le verras pas venir.

La réponse à votre question est que c'est les deux, mais aucune des préoccupations n'est absolue. Ils sont soit totalement subjectifs, soit uniquement objectifs par rapport au contexte. Malheureusement, parfois, l’opinion entièrement subjective ou plutôt dominante prévaut.

En règle générale, si cela nécessite une boucle imbriquée ou si cela semble être la prochaine étape évidente, il est préférable de ne pas délibérer, mais simplement de le faire. Cependant, si des doutes persistent, il devrait être réexaminé ultérieurement.

Une autre règle est que vous devez toujours vérifier la cardinalité et vous demander si cette boucle pose problème. Dans mon exemple précédent, je traversais des villes. Pour tester, je ne vais peut-être parcourir que dix villes, mais quel est le nombre maximal raisonnable de villes à attendre dans le monde réel? Je pourrais alors le multiplier par le même pour les continents. En règle générale, il est conseillé de toujours considérer avec les boucles, en particulier le fait d'itérer un nombre de fois dynamique (variable) ce que cela pourrait traduire par la suite.

Peu importe toujours ce qui fonctionne en premier. Lorsque vous voyez une opportunité d'optimisation, vous pouvez comparer votre solution optimisée aux solutions les plus faciles à mettre en œuvre et confirmer qu'elle offre les avantages escomptés. Vous pouvez également passer trop de temps à optimiser prématurément avant que les mesures ne soient effectuées, ce qui conduit à YAGNI ou à beaucoup de perte de temps et de délais.