Perché i loop annidati sono considerati una cattiva pratica?

29

Il mio docente ha menzionato oggi che era possibile "etichettare" i loop in Java in modo che potessi fare riferimento a essi quando si tratta di cicli annidati. Così ho cercato la funzione perché non ne ero a conoscenza e in molti punti in cui questa funzione è stata spiegata è seguito un avvertimento, scoraggiando i cicli annidati.

Non capisco davvero perché? È perché influisce sulla leggibilità del codice? O è qualcosa di più "tecnico"?

    
posta DSF 23.05.2013 - 21:56
fonte

4 risposte

53

I cicli annidati vanno bene fintanto che descrivono l'algoritmo corretto.

I cicli annidati hanno considerazioni sulle prestazioni (vedi @ risposta di Travis-Pesetto), ma a volte è esattamente l'algoritmo corretto, ad es. quando devi accedere ad ogni valore in una matrice.

L'etichettatura di loop in Java consente di interrompere prematuramente diversi cicli annidati quando altri modi per farlo sarebbero scomodi. Per esempio. alcuni giochi potrebbero avere un pezzo di codice come questo:

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

Sebbene il codice come l'esempio sopra possa a volte essere il modo ottimale per esprimere un determinato algoritmo, è solitamente meglio suddividere questo codice in funzioni più piccole e probabilmente usare return anziché break . Quindi un break con un'etichetta è un debole odore di codice ; fai attenzione quando lo vedi.

    
risposta data 23.05.2013 - 22:43
fonte
21

I cicli annidati sono spesso (ma non sempre) cattive pratiche, perché sono frequentemente (ma non sempre) eccessivo per ciò che stai cercando di fare. In molti casi, c'è un modo molto più rapido e meno dispendioso per raggiungere l'obiettivo che stai cercando di raggiungere.

Ad esempio, se hai 100 elementi nell'elenco A e 100 elementi nell'elenco B e sai che per ogni elemento nell'elenco A c'è un elemento nell'elenco B che lo abbina (con la definizione di "corrispondenza"). lasciato deliberatamente oscuro qui), e vuoi produrre una lista di coppie, il modo semplice per farlo è come questo:

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 voci in ciascuna lista, questa operazione richiederà in media 100 * 100/2 (5.000)% di operazioni dimatches. Con più elementi o se la correlazione 1: 1 non è garantita, diventa ancora più costosa.

D'altra parte, c'è un modo molto più veloce per eseguire un'operazione come questa:

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 lo fai in questo modo, invece del numero di matches operazioni basate su length(A) * length(B) , ora si basa su length(A) + length(B) , il che significa che il tuo codice verrà eseguito molto più velocemente.

    
risposta data 23.05.2013 - 22:35
fonte
8

Dato il caso di molti cicli annidati si finisce con il tempo polinomiale. Ad esempio dato questo pseudo codice:

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

Questo sarebbe considerato O (n ^ 2) tempo che sarebbe un grafico simile a:

Dove l'asse y è la quantità di tempo che il tuo programma impiega per terminare e l'asse x è la quantità di dati.

Se ricevi troppi dati il tuo programma sarà così lento nessuno lo aspetterà. e non si tratta di circa 1.000 voci di dati, a mio avviso, ci vorrà troppo tempo.

    
risposta data 23.05.2013 - 22:16
fonte
8

Un motivo per evitare i cicli di nidificazione è perché è una cattiva idea nidificare strutture di blocchi troppo in profondità, indipendentemente dal fatto che siano loop o meno.

Ogni funzione o metodo dovrebbe essere facile da capire, sia il suo scopo (il nome dovrebbe esprimere quello che fa) sia i maintainer (dovrebbe essere facile capire gli interni). Se una funzione è troppo complicata per comprendere facilmente, ciò significa solitamente che alcuni interni devono essere suddivisi in funzioni separate in modo che possano essere indicati nella funzione principale (ora più piccola) per nome.

I loop annidati possono essere difficili da comprendere in tempi relativamente brevi, anche se alcuni nidi di loop sono soddisfacenti - fornendo, come altri sottolineano, che ciò non significa che si sta creando un problema di prestazioni usando un algoritmo estremamente (e inutilmente) lento .

In realtà, non hai bisogno di cicli nidificati per ottenere limiti di prestazioni assurdamente lenti. Si consideri, ad esempio, un singolo ciclo che in ogni iterazione prende un elemento da una coda, quindi può essere inserito più volte, ad es. ricerca in ampiezza di un labirinto. La performance non è decisa dalla profondità del nesting del loop (che è solo 1) ma dal numero di elementi che vengono messi in quella coda prima che sia esaurito ( se è mai esaurito) - quanto è grande la parte raggiungibile del labirinto.

    
risposta data 24.05.2013 - 11:00
fonte

Leggi altre domande sui tag