¿Por qué los bucles anidados se consideran una mala práctica?

33

Mi profesor mencionó hoy que era posible "etiquetar" los bucles en Java para que pudiera referirse a ellos cuando se trata de bucles anidados. Así que busqué la función, ya que no lo sabía y en muchos lugares donde se explicó esta función fue seguida por una advertencia, desalentando los bucles anidados.

Realmente no entiendo por qué? ¿Es porque afecta la legibilidad del código? ¿O es algo más "técnico"?

DSF
fuente
44
Si recuerdo correctamente mi curso CS3 es porque a menudo conduce a un tiempo exponencial, lo que significa que si obtiene un gran conjunto de datos, su aplicación quedará inutilizable.
Travis Pessetto
21
Una cosa que debe aprender sobre los profesores de CS es que no todo lo que dicen se aplica al 100% en el mundo real. Desalentaría los bucles anidados a más de unos pocos de profundidad, pero si tiene que procesar elementos m x n para resolver su problema, hará tantas iteraciones.
Blrfl
8
@TravisPessetto En realidad, todavía es una complejidad polinómica: O (n ^ k), siendo k el número de O anidado, no exponencial (k ^ n), donde k es una constante.
m3th0dman
1
@ m3th0dman Gracias por corregirme. Mi maestro no era el mejor en este tema. Trató a O (n ^ 2) y O (k ^ n) como lo mismo.
Travis Pessetto
2
Los bucles anidados aumentan la complejidad ciclomática (ver aquí ), lo que disminuye la capacidad de mantenimiento de un programa, según algunas personas.
Marco

Respuestas:

62

Los bucles anidados están bien siempre que describan el algoritmo correcto.

Los bucles anidados tienen consideraciones de rendimiento (consulte la respuesta de @ Travis-Pesetto), pero a veces es exactamente el algoritmo correcto, por ejemplo, cuando necesita acceder a cada valor en una matriz.

Etiquetar bucles en Java permite romper prematuramente varios bucles anidados cuando otras formas de hacerlo serían engorrosas. Por ejemplo, algunos juegos pueden tener un código como este:

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

Si bien el código como el ejemplo anterior a veces puede ser la forma óptima de expresar un cierto algoritmo, generalmente es mejor dividir este código en funciones más pequeñas, y probablemente usarlo en returnlugar de break. Entonces, una breaketiqueta tiene un olor a código débil ; presta especial atención cuando lo veas.

9000
fuente
2
Del mismo modo que los gráficos de una nota lateral utilizan un algoritmo que tiene que acceder a cada pieza de una matriz. Sin embargo, la GPU está especializada para manejar esto de una manera eficiente en el tiempo.
Travis Pessetto
Sí, GPU hace esto de una manera masivamente paralela; La pregunta era sobre un solo hilo de ejecución, supongo.
9000
2
Una de las razones por las que las etiquetas tienden a ser sospechosas es porque a menudo hay una alternativa. En este caso, podría regresar en su lugar.
jgmjgm
22

Los bucles anidados son con frecuencia (pero no siempre) una mala práctica, porque con frecuencia (pero no siempre) son excesivos para lo que estás tratando de hacer. En muchos casos, hay una forma mucho más rápida y menos derrochadora de lograr el objetivo que está tratando de lograr.

Por ejemplo, si tiene 100 elementos en la lista A y 100 elementos en la lista B, y sabe que para cada elemento en la lista A hay un elemento en la lista B que coincide, (con la definición de "coincidencia" deja deliberadamente oscuro aquí), y desea producir una lista de pares, la forma simple de hacerlo es así:

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

Con 100 elementos en cada lista, esto requerirá un promedio de 100 * 100/2 (5,000) matchesoperaciones. Con más elementos, o si la correlación 1: 1 no está asegurada, se vuelve aún más costosa.

Por otro lado, hay una forma mucho más rápida de realizar una operación como esta:

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 lo hace de esta manera, en lugar de la cantidad de matchesoperaciones en que se basa length(A) * length(B), ahora se basa en length(A) + length(B), lo que significa que su código se ejecutará mucho más rápido.

Mason Wheeler
fuente
10
Con la advertencia de que la configuración de clasificación lleva una cantidad de tiempo no trivial, O(n log n)dos veces, si se usa Quicksort.
Robert Harvey
@RobertHarvey: Por supuesto. Pero eso es mucho menos que O(n^2)para los valores no pequeños de N.
Mason Wheeler
10
La segunda versión del algoritmo es generalmente incorrecta. Primero, se supone que X e Y son comparables a través del <operador, que generalmente no puede derivarse del matchesoperador. En segundo lugar, incluso si X e Y son numéricos, el segundo algoritmo aún puede producir resultados incorrectos, por ejemplo, cuando lo X matches Yes X + Y == 100.
Pasha
9
@ user958624: Obviamente, esta es una visión general de muy alto nivel de un algoritmo general. Al igual que el operador "coincide", el "<" debe definirse de forma correcta en el contexto de los datos que se comparan. Si esto se hace correctamente, los resultados serán correctos.
Mason Wheeler
PHP hizo algo así como el último con su matriz única, creo, y / o lo contrario. En cambio, las personas solo usarían matrices de PHP que están basadas en hash y sería mucho más rápido.
jgmjgm
11

Una razón para evitar anidar bucles es porque es una mala idea anidar estructuras de bloques con demasiada profundidad, independientemente de si son bucles o no.

Cada función o método debe ser fácil de entender, tanto su propósito (el nombre debe expresar lo que hace) como para los mantenedores (debe ser fácil de entender lo interno). Si una función es demasiado complicada para comprenderla fácilmente, eso generalmente significa que algunas de las funciones internas se deben descomponer en funciones separadas para que se pueda hacer referencia a ellas en la función principal (ahora más pequeña) por nombre.

Los bucles anidados pueden ser difíciles de entender con relativa rapidez, aunque algunos anidamientos de bucles están bien, ya que, como otros señalan, eso no significa que esté creando un problema de rendimiento al usar un algoritmo extremadamente lento (e innecesariamente).

En realidad, no necesita bucles anidados para obtener límites de rendimiento absurdamente lentos. Considere, por ejemplo, un solo bucle que en cada iteración toma un elemento de una cola y luego posiblemente devuelve varios, por ejemplo, la búsqueda en primer plano de un laberinto. El rendimiento no se decide por la profundidad de anidamiento del bucle (que es solo 1) sino por el número de elementos que se colocan en esa cola antes de que finalmente se agote ( si alguna vez se agota): cuán grande es la parte alcanzable del bucle Laberinto es.

Steve314
fuente
1
Muy a menudo, puede aplanar un bucle anidado y todavía se necesita el mismo tiempo. tomar de 0 a ancho; de 0 a altura; En su lugar, solo puede poner de 0 a ancho por alto.
jgmjgm
@jgmjgm: sí, a riesgo de complicar el código dentro del bucle. El aplanamiento también puede simplificar eso a veces, pero más a menudo al menos agrega la complejidad de recuperar los índices que realmente desea. Un truco para eso es usar un tipo de índice que factoriza todos los bucles que anidan en la lógica para incrementar un índice compuesto especial: no es probable que lo haga solo para un bucle, pero tal vez tenga múltiples bucles con estructuras similares o tal vez Puedes escribir una versión genérica más flexible. Los gastos generales para usar ese tipo (si los hay) pueden valer la pena para mayor claridad.
Steve314
No lo sugiero como algo bueno, sino por lo sorprendentemente simple que puede ser convertir dos bucles en uno, pero aún así no tener un impacto en la complejidad del tiempo.
jgmjgm
7

Dado el caso de muchos bucles anidados, terminas con tiempo polinómico. Por ejemplo, dado este pseudocódigo:

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

Esto se consideraría O (n ^ 2) tiempo, que sería un gráfico similar a: ingrese la descripción de la imagen aquí

Donde el eje y es la cantidad de tiempo que su programa tarda en terminar y el eje x es la cantidad de datos.

Si obtiene demasiados datos, su programa será tan lento que nadie lo esperará. y no es tanto alrededor de 1,000 entradas de datos, creo que tomará demasiado tiempo.

Travis Pessetto
fuente
10
es posible que desee volver a seleccionar la gráfica: que no es una curva exponencial de forma cuadrática, también recursividad no hace cosas de O (n log n) de O (n ^ 2)
de trinquete monstruo
55
Para la recursión tengo dos palabras "apilar" y "desbordar"
Mateusz
10
Su afirmación de que la recursividad puede reducir una operación O (n ^ 2) a una O (n log n) es en gran medida inexacta. El mismo algoritmo implementado de forma recursiva frente a iterativa debería tener exactamente la misma complejidad de tiempo Big-O. Además, la recursión a menudo puede ser más lenta (dependiendo de la implementación del lenguaje), ya que cada llamada recursiva requiere la creación de un nuevo marco de pila, mientras que la iteración solo requiere una ramificación / comparación. Las llamadas a funciones suelen ser baratas, pero no son gratuitas.
dckrooney
2
@TravisPessetto He visto 3 desbordamientos de pila en los últimos 6 meses al desarrollar aplicaciones de C # debido a referencias de objetos de recursión o cíclicos. Lo curioso es que se estrellará y no sabes qué te golpeó. Cuando ve bucles anidados, sabe que algo malo puede suceder, y una excepción sobre el índice incorrecto de algo es fácilmente visible.
Mateusz
2
@Mateusz también, lenguajes como Java le permiten detectar un error de desbordamiento de pila. Esto con un seguimiento de pila debería permitirle ver lo que sucedió. No tengo mucha experiencia, pero la única vez que he visto un error de desbordamiento de pila es en un PHP que tenía un error que causaba una recursión infinita y PHP se quedó sin los 512 MB de memoria que se le asignó. La recursión debe tener un valor final final, no es bueno para bucles infinitos. Como todo en CS, hay un momento y un lugar para todas las cosas.
Travis Pessetto
0

Conducir un camión de treinta toneladas en lugar de un pequeño vehículo de pasajeros es una mala práctica. Excepto cuando necesite transportar 20 o 30 toneladas de cosas.

Cuando usa un bucle anidado, no es una mala práctica. Es completamente estúpido o es exactamente lo que se necesita. Tú decides.

Sin embargo, alguien se quejó de etiquetar los bucles. La respuesta para eso: si tiene que hacer la pregunta, entonces no use el etiquetado. Si sabes lo suficiente como para decidirte, entonces tú decides.

gnasher729
fuente
Si sabes lo suficiente como para decidirte, sabes lo suficiente como para no usar bucles etiquetados. :-)
user949300
No. Cuando se le ha enseñado lo suficiente, se le ha enseñado a no usar el uso etiquetado. Cuando sabes lo suficiente, trasciendes más allá del dogma y haces lo correcto.
gnasher729
1
El problema con la etiqueta es que rara vez se necesita y mucha gente lo usa desde el principio para evitar errores de control de flujo. Algo así como cómo las personas ponen la salida en todo el lugar cuando obtienen un control de flujo incorrecto. Las funciones también lo hacen en gran medida redundante.
jgmjgm
-1

No hay nada intrínsecamente malo o necesariamente malo en los bucles anidados. Sin embargo, tienen ciertas consideraciones y dificultades.

Los artículos a los que se dirigió, probablemente en nombre de la brevedad o debido a un proceso psicológico conocido como quemado, omitiendo los detalles.

Quemarse es cuando tienes una experiencia negativa de algo con el ser implicado y luego lo evitas. Por ejemplo, podría cortar vegetales con un cuchillo afilado y cortarme yo mismo. Entonces podría decir que los cuchillos afilados son malos, no los use para cortar vegetales para tratar de hacer imposible que esa mala experiencia vuelva a suceder. Eso es obviamente muy poco práctico. En realidad solo necesitas tener cuidado. Si le estás diciendo a otra persona que corte las verduras, entonces tienes un sentido aún más fuerte de esto. Si les dijera a los niños que cortaran vegetales, me gustaría mucho decirles que no usen un cuchillo afilado, especialmente si no puedo supervisarlos de cerca.

El problema con la programación es que no alcanzará la máxima eficiencia si siempre prefiere la seguridad primero. En este caso, los niños solo pueden cortar vegetales blandos. Enfrentados con cualquier otra cosa y solo lo arruinarán con un cuchillo sin filo. Es importante aprender el uso adecuado de los bucles, incluidos los bucles anidados, y no puede hacerlo si se consideran malos y nunca intenta usarlos.

Como muchas respuestas aquí señalan, un bucle anidado es una indicación de las características de rendimiento de su programa que pueden empeorar exponencialmente cada anidación. Es decir, O (n), O (n ^ 2), O (n ^ 3) y así sucesivamente, que comprende O (n ^ profundidad) donde la profundidad representa cuántos bucles ha anidado. A medida que crece su anidación, el tiempo requerido crece exponencialmente. El problema es que esto no es una certeza de que su complejidad de tiempo o espacio sea eso (a menudo a * b * c pero no todos los bucles de nido pueden ejecutarse todo el tiempo tampoco) ni es una certeza de que tener un problema de rendimiento incluso si es eso.

Para muchas personas, especialmente estudiantes, escritores y profesores que, para ser francos, rara vez programan para ganarse la vida o en el día a día para bucles, también pueden ser algo a lo que no están acostumbrados y que indujeron demasiada carga cognitiva en los primeros encuentros. Este es un aspecto problemático porque siempre hay una curva de aprendizaje y evitarla no será eficaz para convertir a los estudiantes en programadores.

Los bucles anidados pueden volverse salvajes, es decir, pueden terminar anidados muy profundamente. Si paso por cada continente, luego por cada país, luego por cada ciudad, luego por cada tienda, luego por cada estante, luego por cada producto si es una lata de frijoles por cada frijol y mido su tamaño para obtener el promedio, entonces usted puede ver que anidará muy profundamente. Tendrás una pirámide y mucho espacio desperdiciado lejos del margen izquierdo. Incluso puede terminar saliendo de la página.

Este es un problema que sería más significativo históricamente donde las pantallas eran pequeñas y de baja resolución. En esos casos, incluso unos pocos niveles de anidación podrían realmente ocupar mucho espacio. Esta es una preocupación menor hoy en día donde el umbral es más alto, aunque todavía puede presentar un problema si hay suficiente anidamiento.

Relacionado está el argumento de la estética. Muchas personas no encuentran que los bucles anidados sean estéticamente agradables en contraste con los diseños con una alineación más consistente, esto puede o no estar relacionado con lo que las personas están acostumbradas, el seguimiento ocular y otras preocupaciones. Sin embargo, es problemático porque tiende a reforzarse a sí mismo y, en última instancia, puede hacer que el código sea más difícil de leer, ya que romper un bloque de código y encapsular bucles detrás de abstracciones como funciones también corre el riesgo de romper el mapeo del código al flujo de ejecución.

Hay una tendencia natural hacia lo que la gente está acostumbrada. Si está programando algo de la manera más simple, la probabilidad de no necesitar anidamiento es mayor, la probabilidad de necesitar un nivel disminuye en un orden de magnitud, la probabilidad de que otro nivel disminuya nuevamente. La caída de frecuencia y esencialmente significa que cuanto más profundo es el anidamiento, menos capacitados están los sentidos humanos para anticiparlo.

Relacionado con eso, es que en cualquier construcción compleja, que se puede considerar un bucle anidado, siempre debe preguntar es la solución más simple posible, ya que existe el potencial para una solución perdida que necesita menos bucles. La ironía es que una solución anidada a menudo es la forma más sencilla de producir algo que funcione con la mínima cantidad de esfuerzo, complejidad y carga cognitiva. A menudo es natural anidar para bucles. Si considera, por ejemplo, una de las respuestas anteriores donde la forma mucho más rápida que un bucle for anidado también es mucho más compleja y consiste en un código significativamente más.

Se necesita una gran cantidad de atención, ya que a menudo es posible abstraer los bucles o aplanarlos, pero el resultado final es una cura peor que la enfermedad, especialmente si no está recibiendo, por ejemplo, una mejora del rendimiento cuantificable y significativa.

Es muy común que las personas experimenten con frecuencia problemas de rendimiento en asociación con bucles que le dicen a la computadora que repita una acción muchas veces y que a menudo estarán implicados en cuellos de botella de rendimiento. Lamentablemente, las respuestas a esto pueden ser muy superficiales. Es común que las personas vean un bucle y vean un problema de rendimiento donde no lo hay, y luego oculten el bucle de la vista sin ningún efecto real. El código "se ve" rápido pero lo pone en el camino, teclea el encendido, pisa el acelerador y mira el velocímetro y es posible que todavía sea tan rápido como una anciana que camina por su marco zimmer.

Este tipo de escondite es similar a si tienes diez asaltantes en tu ruta. Si en lugar de tener una ruta directa a donde quieres ir, la arreglas para que haya un atracador detrás de cada esquina, entonces te da la ilusión al comenzar tu viaje de que no hay atracadores. Fuera de la vista, fuera de la mente. todavía vas a ser asaltado diez veces, pero ahora no lo verás venir.

La respuesta a su pregunta es que son ambas, pero ninguna de las preocupaciones es absoluta. Son completamente subjetivos o solo contextualmente objetivos. Lamentablemente, a veces, la opinión totalmente subjetiva o más bien precede y domina.

Como regla general, si necesita un bucle anidado o ese parece ser el siguiente paso obvio, es mejor no deliberar y simplemente hacerlo. Sin embargo, si persisten las dudas, se debe revisar más adelante.

Otra regla general es que siempre debe verificar la cardinalidad y preguntarse si este bucle será un problema. En mi ejemplo anterior, pasé por ciudades. Para las pruebas, podría pasar por diez ciudades, pero ¿cuál es el número máximo razonable de ciudades que se pueden esperar en el uso en el mundo real? Entonces podría multiplicar eso por lo mismo para los continentes. Es una regla general considerar siempre con bucles, especialmente que iteran una cantidad dinámica (variable) de veces lo que eso podría traducirse en el futuro.

Independientemente, siempre haz lo que funciona primero. La forma en que ve una oportunidad para la optimización puede comparar su solución optimizada con la más fácil de conseguir y confirmar que produjo los beneficios esperados. También puede pasar demasiado tiempo optimizando prematuramente antes de que comiencen las mediciones y eso conduce a YAGNI o una gran cantidad de tiempo perdido y plazos vencidos.

jgmjgm
fuente
El ejemplo de cuchillo afilado <-> no es excelente, ya que los cuchillos romos son generalmente más peligrosos para cortar. Y O (n) -> O (n ^ 2) -> O (n ^ 3) no es exponencial en n, es geométrica o polinómica .
Caleth
Que los cuchillos sin filo sean peores es un mito urbano. En la práctica, varía y suele ser específico para el caso en el que los cuchillos desafilados son particularmente inadecuados, por lo general requieren mucha fuerza e implican mucho deslizamiento. Sin embargo, tienes razón, hay una limitación oculta pero inherente, solo puedes cortar vegetales blandos. Consideraría n ^ profundidad exponencial, pero tienes razón, esos ejemplos por sí solos no lo son.
jgmjgm
@jgmjgm: n ^ la profundidad es polinómica, la profundidad ^ n es exponencial. No es realmente una cuestión de interpretación.
Roel Schroeven
x ^ y es diferente a y ^ x? El error que cometiste es que nunca lees la respuesta. Has buscado exponencialmente y luego has buscado ecuaciones que por sí mismas no son exponenciales. Si lees, verás que dije que aumenta exponencialmente para cada capa de anidación y si lo pones a prueba tú mismo, el tiempo para (a = 0; a <n; a ++); para (b = 0; b <n ; b ++); para (c = 0; c <n; c ++); al agregar o eliminar bucles, verá que es exponencial. Encontrará que un ciclo se realiza en n ^ 1, dos en n ^ 2 y tres en n ^ 3. No puede entender anidado: D. Subconjuntos gemoétricos exponenciales.
jgmjgm
Supongo que esto prueba que las personas realmente luchan con construcciones anidadas.
jgmjgm