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

33

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"?

DSF
la source
4
Si je me souviens bien de mon cours CS3, c'est qu'il entraîne souvent un temps exponentiel, ce qui signifie que si vous obtenez un ensemble de données volumineux, votre application deviendra inutilisable.
Travis Pessetto
21
Une chose que vous devriez apprendre à propos des conférenciers CS est que tout ce qu'ils disent ne s'applique pas à 100% dans le monde réel. Je découragerais les boucles imbriquées plus que quelques profonds, mais si vous devez traiter m x n éléments pour résoudre votre problème, vous allez faire autant d'itérations.
Blrfl
8
@ TravisPessetto En réalité, il s'agit toujours d'une complexité polynomiale - O (n ^ k), k étant le nombre de O imbriqués et non exponentiels, k étant une constante.
m3th0dman
1
@ m3th0dman Merci de m'avoir corrigé. Mon professeur n'était pas le meilleur sur ce sujet. Il a traité O (n ^ 2) et O (k ^ n) comme identiques.
Travis Pessetto
2
Les boucles imbriquées augmentent la complexité cyclomatique (voir ici ), ce qui diminue la maintenabilité d'un programme, selon certaines personnes.
Marco

Réponses:

62

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.

9000
la source
2
Tout comme une note latérale, les graphiques utilisent un algorithme qui doit accéder à chaque élément d'une matrice. Cependant, le GPU est spécialisé pour gérer cela rapidement.
Travis Pessetto
Oui, GPU le fait de manière très parallèle. la question portait sur un seul fil d'exécution, je suppose.
9000
2
L'une des raisons pour lesquelles les étiquettes ont tendance à être suspectes est qu'il existe souvent une alternative. Dans ce cas, vous pouvez retourner à la place.
Jgmjgm
22

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.

Maçon Wheeler
la source
10
Avec l'avertissement que la configuration de tri prend une quantité de temps non triviale, O(n log n)deux fois, si Quicksort est utilisé.
Robert Harvey
@ RobertHarvey: Bien sûr. Mais c'est toujours beaucoup moins que O(n^2)pour les valeurs non infimes de N.
Mason Wheeler
10
La deuxième version de l'algorithme est généralement incorrecte. Premièrement, il suppose que X et Y sont comparables via un <opérateur, ce qui ne peut généralement pas être dérivé de l' matchesopérateur. Deuxièmement, même si X et Y sont numériques, le deuxième algorithme peut toujours produire des résultats erronés, par exemple, quand X matches Yest X + Y == 100.
Pasha
9
@ user958624: Évidemment, il s'agit d'un aperçu de très haut niveau d'un algorithme général. A l'instar de l'opérateur "matches", le "<" doit être défini de manière correcte dans le contexte des données comparées. Si cela est fait correctement, les résultats seront corrects.
Mason Wheeler
PHP a fait quelque chose comme cette dernière avec son tableau unique et / ou l’inverse. Les gens utiliseraient plutôt les tableaux de PHP basés sur le hachage et ce serait beaucoup plus rapide.
jgmjgm
11

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.

Steve314
la source
1
Vous pouvez très souvent simplement aplatir une boucle imbriquée et cela prend toujours le même temps. prendre pour 0 à la largeur, pour 0 à la hauteur; Vous pouvez plutôt mettre 0 pour la largeur multiplié par la hauteur.
Jgmjgm
@jgmjgm - oui, au risque de compliquer le code dans la boucle. L'aplatissement peut parfois simplifier les choses, mais le plus souvent, vous ajoutez au moins la complexité de la récupération des index que vous souhaitez réellement. Une astuce consiste à utiliser un type d’index prenant en compte toutes les boucles imbriquées dans la logique pour incrémenter un index composé spécial - vous ne le ferez probablement que pour une boucle, mais vous aurez peut-être plusieurs boucles avec des structures similaires ou peut-être vous pouvez écrire une version générique plus flexible. Les frais généraux liés à l'utilisation de ce type (le cas échéant) peuvent valoir la peine d'être clarifiés.
Steve314 le
Je ne le suggère pas comme une bonne chose à faire, mais comme il est incroyablement simple de transformer deux boucles en une, sans pour autant avoir un impact sur la complexité temporelle.
Jgmjgm
7

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 à: entrez la description de l'image ici

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

Travis Pessetto
la source
10
vous voudrez peut-être resélectionner votre graphique: c'est une courbe exponentielle et non quadratique, la récursivité ne fait pas non plus de substance O (n log n) à partir de O (n ^ 2)
phénomène de cliquet
5
Pour la récursion, j'ai deux mots "stack" et "overflow"
Mateusz
10
Votre déclaration selon laquelle la récursivité peut réduire une opération O (n ^ 2) à un O (n log n) est largement inexacte. Le même algorithme implémenté de manière récursive ou itérative doit avoir exactement la même complexité temporelle big-O. De plus, la récursivité peut souvent être plus lente (en fonction de l'implémentation du langage), car chaque appel récursif nécessite la création d'un nouveau cadre de pile, alors que l'itération nécessite uniquement une branche / comparaison. Les appels de fonction sont généralement peu coûteux, mais ils ne sont pas gratuits.
dckrooney
2
@TravisPessetto J'ai vu 3 débordements de pile au cours des 6 derniers mois lors du développement d'applications C # en raison de références d'objets récursifs ou cycliques. Ce qui est amusant, c’est que ça va planter et que vous ne savez pas ce qui vous a frappé. Lorsque vous voyez des boucles imbriquées, vous savez que quelque chose de mauvais peut arriver, et une exception concernant un index incorrect pour quelque chose est facilement visible.
Mateusz
2
@Mateusz également, des langages comme Java vous permettent de détecter une erreur de débordement de pile. Ceci avec une trace de pile devrait vous permettre de voir ce qui s'est passé. Je n'ai pas beaucoup d'expérience, mais la seule fois où j'ai vu une erreur de débordement de pile, c'est dans un PHP qui avait un bogue causant une récursion infinie et PHP manquait des 512 Mo de mémoire qui lui avaient été attribués. La récursion doit avoir une valeur finale, ce n'est pas bon pour les boucles infinies. Comme dans CS, il y a un temps et un lieu pour toutes choses.
Travis Pessetto
0

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.

gnasher729
la source
Si vous en savez assez pour décider vous-même, vous en savez assez pour ne pas utiliser de boucles étiquetées. :-)
user949300
Non. Lorsque vous en avez appris suffisamment, vous avez appris à ne pas utiliser les étiquettes. Quand vous en savez assez, vous transcendez le dogme et faites ce qui est juste.
Gnasher729
1
Le problème avec l'étiquette est que c'est rarement nécessaire et que beaucoup de gens l'utilisent très tôt pour contourner les erreurs de contrôle de flux. Un peu comme la façon dont les gens mettent la sortie partout quand ils se trompent de contrôle de flux. Les fonctions le rendent également largement redondant.
Jgmjgm
-1

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.

jgmjgm
la source
L'exemple de couteau tranchant <-> tranchant n'est pas génial, car les couteaux émoussés sont généralement plus dangereux à couper. Et O (n) -> O (n ^ 2) -> O (n ^ 3) n'est pas exponentiel en n, c'est géométrique ou polynomial .
Caleth
Que les couteaux émoussés soient pires est un peu un mythe urbain. En pratique, cela varie et est généralement spécifique au cas où les couteaux émoussés sont particulièrement inadaptés, requérant généralement beaucoup de force et de glissement. Vous avez raison cependant, il existe une limitation cachée mais inhérente, vous ne pouvez couper que des légumes mous. Je ne considérerais pas la profondeur comme exponentielle, mais vous avez raison, ces exemples ne le sont pas.
jgmjgm le
@jgmjgm: n ^ profondeur est polynomiale, profondeur ^ n est exponentielle. Ce n'est pas vraiment une question d'interprétation.
Roel Schroeven le
x ^ y est différent de y ^ x? L'erreur que vous avez commise est de ne jamais lire la réponse. Vous avez recherché exponentiel, puis des équations qui, à elles seules, ne sont pas exponentielles. Si vous lisez, vous verrez que j'ai dit que cela augmentait de façon exponentielle pour chaque couche d'imbrication et si vous le testiez vous-même, le temps pour (a = 0; a <n; a ++); pour (b = 0; b <n ; b ++); pour (c = 0; c <n; c ++); lors de l'ajout ou de la suppression de boucles, vous verrez qu'il est effectivement exponentiel. Vous trouverez une boucle effectuée à n ^ 1, deux à n ^ 2 et trois à n ^ 3. Vous ne parvenez pas à comprendre imbriqué: D. Sous-ensembles gémoétriques exponentiels.
jgmjgm
J'imagine que cela prouve que les gens ont vraiment du mal avec les constructions imbriquées.
jgmjgm