Por que os loops aninhados são considerados uma má prática?

33

Meu palestrante mencionou hoje que era possível "rotular" loops em Java para que você pudesse se referir a eles ao lidar com loops aninhados. Portanto, procurei o recurso porque não o conhecia e, em muitos lugares em que esse recurso foi explicado, foi seguido por um aviso, desencorajando loops aninhados.

Eu realmente não entendo o porquê? É porque afeta a legibilidade do código? Ou é algo mais "técnico"?

DSF
fonte
4
Se me lembro corretamente do meu curso no CS3, é porque muitas vezes leva a tempo exponencial, o que significa que, se você receber um conjunto de dados grande, seu aplicativo ficará inutilizável.
Travis Pessetto
21
Uma coisa que você deve aprender sobre os professores de CS é que nem tudo o que eles dizem se aplica 100% no mundo real. Eu desencorajaria loops aninhados mais do que alguns profundos, mas se você precisar processar m x n elementos para resolver seu problema, fará muitas iterações.
Blrfl 23/05
8
@TravisPessetto Na verdade, ainda é uma complexidade polinomial - O (n ^ k), sendo k o número de O aninhado, não exponencial (k ^ n), onde k é uma constante.
M3th0dman 23/05
1
@ m3th0dman Obrigado por me corrigir. Meu professor não era o melhor nesse assunto. Ele tratou O (n ^ 2) e O (k ^ n) como o mesmo.
Travis Pessetto
2
Os loops aninhados aumentam a complexidade ciclomática (veja aqui ), o que diminui a capacidade de manutenção de um programa, de acordo com algumas pessoas.
Marco

Respostas:

62

Loops aninhados são bons, desde que descrevam o algoritmo correto.

Os loops aninhados têm considerações de desempenho (consulte a resposta de @ Travis-Pesetto), mas às vezes é exatamente o algoritmo correto, por exemplo, quando você precisa acessar todos os valores em uma matriz.

Os loops de rotulagem em Java permitem interromper prematuramente vários loops aninhados quando outras maneiras de fazer isso seriam complicadas. Por exemplo, alguns jogos podem ter um 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
      }
  }
}

Embora código como o exemplo acima às vezes seja a maneira ideal de expressar um determinado algoritmo, geralmente é melhor dividir esse código em funções menores e provavelmente usar em returnvez de break. Portanto, a breakcom um rótulo é um leve cheiro de código ; preste atenção extra ao vê-lo.

9000
fonte
2
Assim como uma nota lateral, os gráficos usam um algoritmo que precisa acessar todas as partes de uma matriz. No entanto, a GPU é especializada para lidar com isso com economia de tempo.
Travis Pessetto 23/05
Sim, a GPU faz isso de maneira massivamente paralela; a pergunta era sobre um único segmento de execução, suponho.
9000
2
Uma das razões pelas quais os rótulos tendem a ser suspeitos é porque geralmente existe uma alternativa. Nesse caso, você pode retornar.
jgmjgm 30/01
22

Os loops aninhados são frequentemente (mas nem sempre) uma prática ruim, porque são frequentemente (mas nem sempre) um exagero no que você está tentando fazer. Em muitos casos, há uma maneira muito mais rápida e menos dispendiosa de atingir a meta que você está tentando alcançar.

Por exemplo, se você possui 100 itens na lista A e 100 itens na lista B e sabe que para cada item da lista A há um item na lista B que corresponde a ele (com a definição de "correspondência" deixada deliberadamente obscura aqui) e você deseja produzir uma lista de pares, a maneira mais simples de fazer isso é assim:

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

Com 100 itens em cada lista, isso levará em média 100 * 100/2 (5.000) matchesoperações. Com mais itens, ou se a correlação 1: 1 não for garantida, ela se tornará ainda mais cara.

Por outro lado, há uma maneira muito mais rápida de executar uma operação 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

Se você fizer dessa maneira, em vez do número de matchesoperações baseadas length(A) * length(B), agora será baseado length(A) + length(B), o que significa que seu código será executado muito mais rápido.

Mason Wheeler
fonte
10
Com a ressalva de que a configuração da classificação leva um tempo não trivial, O(n log n)duas vezes, se o Quicksort for usado.
Robert Harvey
@RobertHarvey: Claro. Mas isso ainda é muito menos do que O(n^2)para valores não-pequenas de N.
Mason Wheeler
10
A segunda versão do algoritmo geralmente está incorreta. Primeiro, assume que X e Y são comparáveis ​​via <operador, que geralmente não podem ser derivados do matchesoperador. Em segundo lugar, mesmo que X e Y sejam numéricos, o segundo algoritmo ainda pode produzir resultados errados, por exemplo, quando X matches Yé X + Y == 100.
Pasha
9
@ user958624: Obviamente, esta é uma visão geral de alto nível de um algoritmo geral. Como o operador "correspondências", o "<" deve ser definido de maneira correta no contexto dos dados que estão sendo comparados. Se isso for feito corretamente, os resultados estarão corretos.
Mason Wheeler
O PHP fez algo parecido com o último, com sua matriz única, eu acho e / ou o contrário. As pessoas usariam apenas as matrizes do PHP baseadas em hash e isso seria muito mais rápido.
jgmjgm 30/01
11

Uma razão para evitar aninhar loops é porque é uma má idéia aninhar estruturas de bloco muito profundamente, independentemente de serem ou não loops.

Cada função ou método deve ser fácil de entender, tanto seu objetivo (o nome deve expressar o que faz) quanto para os mantenedores (deve ser fácil entender os internos). Se uma função é muito complicada para entender com facilidade, isso geralmente significa que alguns dos internos devem ser fatorados em funções separadas para que possam ser referidos na função principal (agora menor) por nome.

Os loops aninhados podem ficar difíceis de entender de maneira relativamente rápida, embora alguns aninhamentos de loops sejam bons - desde que, como outros apontam, isso não signifique que você esteja criando um problema de desempenho usando um algoritmo lento extremamente (e desnecessariamente).

Na verdade, você não precisa de loops aninhados para obter limites de desempenho absurdamente lentos. Considere, por exemplo, um único loop que, em cada iteração, retira um item de uma fila e, em seguida, retira vários itens - por exemplo, a busca pela primeira vez em um labirinto. O desempenho não é decidido pela profundidade do aninhamento do loop (que é apenas 1), mas pelo número de itens que são colocados nessa fila antes de acabar eventualmente ( se algum dia esgotar) - quão grande é a parte alcançável do labirinto é.

Steve314
fonte
1
Muitas vezes, você pode apenas achatar um loop aninhado e ainda leva o mesmo tempo. tome para 0 a largura, para 0 a altura; Você pode colocar 0 a largura vezes a altura.
jgmjgm 30/01
@jgmjgm - sim, correndo o risco de complicar o código dentro do loop. O achatamento pode simplificar isso algumas vezes, mas com mais frequência você está adicionando pelo menos a complexidade de recuperar os índices que realmente deseja. Um truque para isso é usar um tipo de índice que fatore todo o loop aninhado na lógica para incrementar um índice composto especial - você provavelmente não fará isso apenas para um loop, mas talvez tenha vários loops com estruturas semelhantes ou talvez você pode escrever uma versão genérica mais flexível. As despesas gerais por usar esse tipo (se houver) podem valer a pena por clareza.
Steve314 30/01
Não estou sugerindo que seja uma coisa boa a se fazer, mas quão surpreendentemente simples pode ser transformar dois loops em um, mas ainda não afetando a complexidade do tempo.
jgmjgm 10/02
7

Dado o caso de muitos loops aninhados, você acaba com o tempo polinomial. Por exemplo, dado este pseudo-có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

Isso seria considerado tempo O (n ^ 2), que seria um gráfico semelhante a: insira a descrição da imagem aqui

Onde o eixo y é a quantidade de tempo que seu programa leva para terminar e o eixo x é a quantidade de dados.

Se você obtiver muitos dados, seu programa será tão lento que ninguém os esperará. e não são tantas as 1.000 entradas de dados que acredito que levem muito tempo.

Travis Pessetto
fonte
10
você pode querer selecionar novamente o gráfico: que é uma curva exponencial não uma quadrática, também recursão não faz coisas O (n log n) a partir de O (n ^ 2)
catraca aberração
5
Para recursão Eu tenho duas palavras "pilha" e "estouro"
Mateusz
10
Sua afirmação de que a recursão pode reduzir uma operação O (n ^ 2) para um O (n log n) é bastante imprecisa. O mesmo algoritmo implementado recursivamente versus iterativamente deve ter exatamente a mesma complexidade de tempo grande. Além disso, a recursão geralmente pode ser mais lenta (dependendo da implementação do idioma), pois cada chamada recursiva requer a criação de um novo quadro de pilha, enquanto a iteração requer apenas uma ramificação / comparação. As chamadas de função geralmente são baratas, mas não são gratuitas.
Dckrooney 23/05
2
@TravisPessetto Eu vi 3 estouros de pilha nos últimos 6 meses enquanto desenvolvia aplicativos C # devido a recursão ou referências a objetos cíclicos. O engraçado é que ele irá falhar e você não sabe o que o atingiu. Quando você vê loops aninhados, sabe que algo ruim pode acontecer e a exceção sobre o índice errado de algo é facilmente visível.
Mateusz 24/05
2
@Mateusz também, linguagens como Java permitem detectar um erro de estouro de pilha. Isso com um rastreamento de pilha deve permitir que você veja o que aconteceu. Não tenho muita experiência, mas a única vez que vi um erro de estouro de pilha é em um PHP que teve um bug causando uma recursão infinita e o PHP ficou sem os 512 MB de memória que lhe foram atribuídos. A recursão precisa ter um valor final final, não é bom para loops infinitos. Como tudo no CS, há um tempo e um lugar para todas as coisas.
Travis Pessetto
0

Dirigir um caminhão de trinta toneladas em vez de um veículo pequeno de passageiros é uma má prática. Exceto quando você precisa transportar 20 ou 30 toneladas de material.

Quando você usa um loop aninhado, não é uma prática ruim. Ou é totalmente estúpido, ou é exatamente o que é necessário. Você decide.

No entanto, alguém se queixou de rotular loops. A resposta para isso: se você precisar fazer a pergunta, não use etiquetas. Se você souber o suficiente para se decidir, então se decide.

gnasher729
fonte
Se você souber o suficiente para decidir a si mesmo, saberá o suficiente para não usar loops rotulados. :-)
user949300 29/01
Não. Quando você foi ensinado o suficiente, foi ensinado a não usar o uso rotulado. Quando você sabe o suficiente, transcende além do dogma e faz o que é certo.
gnasher729 29/01
1
O problema com o rótulo é que ele raramente é necessário e muitas pessoas o usam desde o início para solucionar erros de controle de fluxo. Mais ou menos como as pessoas colocam a saída em todos os lugares quando entendem errado o controle de fluxo. As funções também o tornam amplamente redundante.
jgmjgm 30/01
-1

Não há nada inerentemente errado ou necessariamente ruim nos loops aninhados. No entanto, eles têm certas considerações e armadilhas.

Os artigos aos quais você foi direcionado, provavelmente em nome da brevidade ou devido a um processo psicológico conhecido como sendo queimado, pulando os detalhes.

Ser queimado é quando você tem uma experiência negativa de algo com o ser implicante e evita-o. Por exemplo, eu poderia cortar legumes com uma faca afiada e me cortar. Eu poderia então dizer que facas afiadas são ruins, não as use para cortar legumes para tentar tornar impossível que essa experiência ruim aconteça novamente. Isso é obviamente muito impraticável. Na realidade, você só precisa ter cuidado. Se você está dizendo para outra pessoa cortar legumes, você tem uma sensação ainda mais forte disso. Se eu estivesse instruindo as crianças a cortarem legumes, sentiria muito forte que lhes dissessem para não usarem uma faca afiada, especialmente se não puder supervisioná-las de perto.

O problema da programação é que você não alcançará o pico de eficiência se sempre preferir segurança primeiro. Nesse caso, as crianças só podem cortar legumes macios. Confrontado com qualquer outra coisa e eles só vão fazer uma bagunça usando uma faca sem corte. É importante aprender o uso adequado de loops, incluindo loops aninhados, e você não pode fazer isso se eles forem considerados ruins e você nunca tentar usá-los.

Como muitas respostas aqui apontam que um loop aninhado é uma indicação das características de desempenho do seu programa que podem ficar exponencialmente piores a cada aninhamento. Ou seja, O (n), O (n ^ 2), O (n ^ 3) e assim por diante, que compreende O (n ^ profundidade), em que profundidade representa quantos ciclos você aninhou. À medida que o seu aninhamento cresce, o tempo necessário aumenta exponencialmente. O problema é que não é uma certeza que sua complexidade de tempo ou espaço seja essa (muitas vezes a * b * c, mas nem todos os loops de ninho podem ser executados o tempo todo) nem é uma certeza que você tem um problema de desempenho mesmo que seja isso.

Para muitas pessoas, especialmente estudantes, escritores e professores que, para ser franco, raramente programa para viver ou diariamente para loops também pode ser algo com o qual não está acostumado e que induziu muita carga cognitiva nos primeiros encontros. Esse é um aspecto problemático, porque sempre há uma curva de aprendizado e evitá-la não será eficaz na conversão de alunos em programadores.

Loops aninhados podem enlouquecer, ou seja, podem acabar aninhados muito profundamente. Se eu percorrer cada continente, depois cada país, depois cada cidade, depois cada loja, depois cada prateleira e cada produto, se for uma lata de feijão através de cada feijão e medir seu tamanho para obter a média, então você pode ver que vai aninhar muito profundamente. Você terá uma pirâmide e muito espaço desperdiçado longe da margem esquerda. Você pode até acabar saindo da página.

Este é um problema que seria mais significativo historicamente onde as telas eram pequenas e de baixa resolução. Nesses casos, mesmo alguns níveis de aninhamento poderiam realmente ocupar muito espaço. Hoje, essa é uma preocupação menor, em que o limite é mais alto, embora ainda possa apresentar um problema se houver aninhamento suficiente.

Relacionado é o argumento da estética. Muitas pessoas não acham aninhadas para loops esteticamente agradáveis, em contraste com layouts com alinhamento mais consistente, isso pode ou não estar relacionado ao que as pessoas estão acostumadas, rastreamento ocular e outras preocupações. No entanto, é problemático, pois tende a se auto-reforçar e, finalmente, pode dificultar a leitura do código, pois quebra um bloco de código e encapsula loops atrás de abstrações, como funções, também corre o risco de quebrar o mapeamento do código para o fluxo de execução.

Há uma tendência natural para o que as pessoas estão acostumadas. Se você estiver programando algo da maneira mais simples, a probabilidade de não precisar de aninhamento é maior, a probabilidade de precisar de um nível diminui em uma ordem de magnitude, a probabilidade de outro nível diminui novamente. A frequência diminuindo e, essencialmente, significando que quanto mais profundo o ninho, menos treinados os sentidos humanos são para antecipá-lo.

Relacionado a isso é que, em qualquer construção complexa, na qual um loop aninhado pode ser considerado, você deve sempre perguntar: a solução mais simples possível, pois há potencial para uma solução perdida que precisa de menos loops. A ironia é que uma solução aninhada costuma ser a maneira mais simples de produzir algo que funcione com a quantidade mínima de esforço, complexidade e carga cognitiva. Geralmente, é natural aninhar-se em loops. Se você considerar, por exemplo, uma das respostas acima, em que a maneira mais rápida que um loop for aninhado também é muito mais complexa e consiste em significativamente mais código.

É necessário muito cuidado, pois muitas vezes é possível abstrair os loops ou achatá-los, mas o resultado final acaba sendo uma cura pior do que a doença, principalmente se você não estiver, por exemplo, recebendo um aprimoramento de desempenho mensurável e significativo do esforço.

É muito comum as pessoas experimentarem problemas de desempenho frequentemente associados a loops que estão dizendo ao computador para repetir uma ação muitas vezes e, inerentemente, frequentemente estão envolvidos em gargalos de desempenho. Infelizmente, as respostas a isso podem ser muito superficiais. Torna-se comum que as pessoas vejam um loop e vejam um problema de desempenho onde não há nenhum e depois ocultem o loop da vista, sem nenhum efeito real. O código "parece" rápido, mas o coloca na estrada, aciona a ignição, pisca no acelerador e dá uma olhada no velocímetro e você pode achar que ele ainda é tão rápido quanto uma velhinha andando em seu zimmer.

Esse tipo de ocultação é semelhante a se você tiver dez ladrões no seu caminho. Se, em vez de seguir um caminho direto para onde você deseja ir, você o organizar de forma que haja um assaltante atrás de cada esquina, isso dará a ilusão de que, ao iniciar sua jornada, não haverá assaltantes. Fora da vista, longe da mente. você ainda será assaltado dez vezes, mas agora não verá isso chegando.

A resposta para sua pergunta é que são as duas coisas, mas nenhuma das preocupações é absoluta. Eles são inteiramente subjetivos ou apenas contextualmente objetivos. Infelizmente, às vezes, a opinião inteiramente subjetiva ou melhor, tem precedentes e domina.

Como regra geral, se precisar de um loop aninhado ou parecer o próximo passo óbvio, é melhor não deliberar e simplesmente fazê-lo. No entanto, se houver alguma dúvida, deve ser revisado posteriormente.

Outra regra prática é que você deve sempre verificar a cardinalidade e se perguntar se esse loop será um problema. No meu exemplo anterior, passei pelas cidades. Para os testes, posso passar por apenas dez cidades, mas qual é o número máximo razoável de cidades que se pode esperar no uso no mundo real? Eu poderia então multiplicar o mesmo para os continentes. É uma regra prática sempre considerar com loops, especialmente que iteram uma quantidade dinâmica (variável) de vezes o que isso pode traduzir para baixo da linha.

Independentemente, sempre faça o que funciona primeiro. Da maneira que você vê uma oportunidade de otimização, você pode comparar sua solução otimizada com a mais fácil de começar a trabalhar e confirmar que ela produziu os benefícios esperados. Você também pode gastar muito tempo otimizando prematuramente antes que as medições sejam realizadas, o que leva ao YAGNI ou a muito desperdício de tempo e prazos perdidos.

jgmjgm
fonte
O exemplo de faca afiada <-> afiada não é excelente, pois as facas sem corte são geralmente mais perigosas para o corte. E O (n) -> O (n ^ 2) -> O (n ^ 3) não é exponencial em n, é geométrica ou polinomial .
Caleth 29/01
Que facas sem graça são piores é um mito urbano. Na prática, isso varia e geralmente é específico para o caso em que as facas opacas são particularmente inadequadas, geralmente exigindo muita força e envolvendo muito deslizamento. Você está certo, porém, há uma limitação oculta, mas inerente, só é possível cortar legumes macios. Eu consideraria exponencial em profundidade, mas você está certo, por exemplo, por si só.
jgmjgm 30/01
@jgmjgm: n ^ profundidade é polinomial, profundidade ^ n é exponencial. Não é realmente uma questão de interpretação.
Roel Schroeven
x ^ y é diferente de y ^ x? O erro que você cometeu é que você nunca não lê a resposta. Você esperou por exponencial e depois esperou por equações que por si só não são exponenciais. Se você ler, verá que eu disse que aumenta exponencialmente para cada camada de aninhamento e, se você testar isso, tempo para (a = 0; a <n; a ++); para (b = 0; b <n ; b ++); para (c = 0; c <n; c ++); ao adicionar ou remover loops, você verá que é realmente exponencial. Você encontrará um loop em n ^ 1, dois em n ^ 2 e três em n ^ 3. Você falha ao entender aninhado: D. Subconjuntos gemoetric exponenciais.
jgmjgm 30/01
Acho que isso prova que as pessoas realmente lutam com construções aninhadas.
jgmjgm 30/01