Dlaczego zagnieżdżone pętle są uważane za złą praktykę?

Mój wykładowca wspominał dziś, że możliwe jest „etykietowanie” pętli w Javie, aby można było się do nich odwoływać w przypadku pętli zagnieżdżonych. Sprawdziłem więc tę funkcję, ponieważ nie wiedziałem o niej, a w wielu miejscach, w których ta funkcja została wyjaśniona, pojawiło się ostrzeżenie, zniechęcające zagnieżdżone pętle.

Naprawdę nie rozumiem dlaczego? Czy to dlatego, że wpływa na czytelność kodu? A może jest to coś bardziej „technicznego”?

Pętle zagnieżdżone są w porządku, o ile opisują poprawny algorytm.

Zagnieżdżone pętle mają wpływ na wydajność (patrz odpowiedź @ Travis-Pesetto), ale czasami jest to dokładnie poprawny algorytm, np. Gdy trzeba uzyskać dostęp do każdej wartości w macierzy.

Oznaczanie pętli w Javie pozwala na przedwczesne wyrwanie się z kilku zagnieżdżonych pętli, gdy inne sposoby na zrobienie tego byłyby uciążliwe. Np. Niektóre gry mogą zawierać taki kod:

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

Chociaż kod taki jak w powyższym przykładzie może czasem być optymalnym sposobem wyrażenia określonego algorytmu, zwykle lepiej jest podzielić ten kod na mniejsze funkcje i prawdopodobnie użyć returnzamiast niego break. A więc breakz etykietą jest słaby zapach kodu ; zwracaj szczególną uwagę, kiedy to zobaczysz.

Zagnieżdżone pętle są często (ale nie zawsze) złą praktyką, ponieważ często (ale nie zawsze) są nadmierne w stosunku do tego, co próbujesz zrobić. W wielu przypadkach istnieje znacznie szybszy i mniej marnotrawny sposób na osiągnięcie celu, który próbujesz osiągnąć.

Na przykład, jeśli masz 100 pozycji na liście A i 100 pozycji na liście B, a wiesz, że dla każdej pozycji na liście A jest jedna pozycja na liście B, która do niej pasuje (z definicją „dopasowania” pozostawiono celowo niejasne tutaj), a chcesz utworzyć listę par, prosty sposób to zrobić:

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

Przy 100 pozycjach na każdej liście zajmie to średnio 100 * 100/2 (5000) matchesoperacji. Przy większej liczbie elementów lub jeśli nie jest zapewniona korelacja 1: 1, staje się ona jeszcze droższa.

Z drugiej strony istnieje znacznie szybszy sposób wykonania takiej operacji:

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

Jeśli zrobisz to w ten sposób, zamiast liczby matchesoperacji, na których się opierasz length(A) * length(B), jest on teraz oparty na length(A) + length(B), co oznacza, że ​​Twój kod będzie działał znacznie szybciej.

Jednym z powodów, dla których należy unikać zagnieżdżania się pętli, jest to, że złym pomysłem jest zbyt głębokie zagnieżdżanie struktur bloków, niezależnie od tego, czy są to pętle, czy nie.

Każda funkcja lub metoda powinna być łatwa do zrozumienia, zarówno jej cel (nazwa powinna wyrażać to, co robi), jak i dla opiekunów (powinno być łatwe do zrozumienia elementy wewnętrzne). Jeśli funkcja jest zbyt skomplikowana, aby można ją było łatwo zrozumieć, oznacza to zwykle, że niektóre elementy wewnętrzne należy rozdzielić na osobne funkcje, aby można było do nich odwoływać się do (obecnie mniejszej) funkcji głównej według nazwy.

Zagnieżdżone pętle mogą być trudne do zrozumienia stosunkowo szybko, chociaż niektóre zagnieżdżanie pętli jest w porządku - pod warunkiem, jak zauważają inni, nie oznacza to, że tworzysz problem z wydajnością przy użyciu wyjątkowo (i niepotrzebnie) powolnego algorytmu.

W rzeczywistości nie potrzebujesz zagnieżdżonych pętli, aby uzyskać absurdalnie powolne ograniczenia wydajności. Rozważmy na przykład pojedynczą pętlę, która w każdej iteracji pobiera jeden element z kolejki, a następnie ewentualnie odkłada kilka z powrotem - np. Pierwsze przeszukanie labiryntu. O wydajności nie decyduje głębokość zagnieżdżenia pętli (która wynosi tylko 1), ale liczba przedmiotów, które trafiają do tej kolejki, zanim zostanie ona ostatecznie wyczerpana ( jeśli w ogóle zostanie wyczerpana) - jak duża jest osiągalna część labirynt jest.

Biorąc pod uwagę przypadek wielu zagnieżdżonych pętli, kończy się czas wielomianowy. Na przykład biorąc pod uwagę ten pseudo kod:

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

Byłby to czas O (n ^ 2), który byłby wykresem podobnym do:

Gdzie oś y to ilość czasu potrzebna na zakończenie programu, a oś x to ilość danych.

Jeśli otrzymasz za dużo danych, twój program będzie tak wolny, że nikt na niego nie poczeka. i nie jest to aż tak wiele z około 1000 wpisów, które, jak sądzę, potrwają zbyt długo.

Prowadzenie trzydziestotonowej ciężarówki zamiast małego samochodu osobowego to zła praktyka. Z wyjątkiem sytuacji, gdy musisz przewieźć 20 lub 30 ton rzeczy.

Kiedy używasz zagnieżdżonej pętli, nie jest to zła praktyka. Jest albo całkowicie głupi, albo jest dokładnie tym, czego potrzeba. Ty decydujesz.

Jednak ktoś narzekał na pętle etykietowania . Odpowiedź na to pytanie: jeśli musisz zadać pytanie, nie używaj etykietowania. Jeśli wiesz wystarczająco dużo, aby samemu decydować, to ty sam decydujesz.

W zagnieżdżonych pętlach nie ma z natury nic złego, a nawet zła. Mają jednak pewne względy i pułapki.

Artykuły, do których cię zaprowadzono, prawdopodobnie w imię zwięzłości lub z powodu procesu psychologicznego zwanego poparzeniem, pomijając szczegóły.

Spalenie występuje wtedy, gdy masz negatywne doświadczenie czegoś z implikacją bycia, a następnie tego unikasz. Na przykład mógłbym kroić warzywa ostrym nożem i sam się kroić. Mogę wtedy powiedzieć, że ostre noże są złe, nie używaj ich do krojenia warzyw, aby uniemożliwić powtórzenie się tego złego doświadczenia. To oczywiście bardzo niepraktyczne. W rzeczywistości musisz tylko uważać. Jeśli mówisz komuś innemu, aby kroił warzywa, masz jeszcze silniejsze poczucie tego. Gdybym pouczał dzieci, aby kroił warzywa, bardzo mocno powiedziałbym im, aby nie używały ostrego noża, zwłaszcza jeśli nie mogę ich ściśle nadzorować.

Problem w programowaniu polega na tym, że nie osiągniesz szczytowej wydajności, jeśli zawsze wolisz bezpieczeństwo. W tym przypadku dzieci mogą kroić tylko miękkie warzywa. W konfrontacji z czymkolwiek innym zrobią z tego bałagan za pomocą tępego noża. Ważne jest, aby nauczyć się właściwego korzystania z pętli, w tym pętli zagnieżdżonych, i nie możesz tego zrobić, jeśli są one uważane za złe i nigdy nie próbujesz ich używać.

Ponieważ wiele odpowiedzi tutaj wskazuje, że zagnieżdżona pętla for wskazuje na charakterystykę wydajności twojego programu, która może pogorszyć się wykładniczo z każdym zagnieżdżeniem. Oznacza to, że O (n), O (n ^ 2), O (n ^ 3) itd., Który obejmuje O (głębokość n ^), gdzie głębokość reprezentuje liczbę zagnieżdżonych pętli. W miarę wzrostu gniazdowania wymagany czas rośnie wykładniczo. Problem polega na tym, że nie ma pewności, że twoja złożoność czasu lub przestrzeni będzie taka (dość często * b * c, ale nie wszystkie pętle gniazd mogą działać cały czas), ani też nie jest pewne, że będziesz masz problem z wydajnością, nawet jeśli tak jest.

Dla wielu ludzi, zwłaszcza studentów, pisarzy i wykładowców, którzy szczerze mówiąc, rzadko programowanie życia lub codzienne pętle mogą być czymś, do czego nie są przyzwyczajeni i które wywołują zbyt duże obciążenie poznawcze na wczesnych spotkaniach. Jest to problematyczny aspekt, ponieważ zawsze istnieje krzywa uczenia się i unikanie jej nie będzie skuteczne w przekształcaniu uczniów w programistów.

Zagnieżdżone pętle mogą zwariować, co oznacza, że ​​mogą zostać zagnieżdżone bardzo głęboko. Jeśli przejdę przez każdy kontynent, następnie przez każdy kraj, następnie przez każde miasto, następnie przez każdy sklep, następnie przez każdą półkę, a następnie przez każdy produkt, jeśli jest to puszka fasoli przez każdą fasolę i zmierzę jej rozmiar, aby uzyskać średnią, to ty widzę, że zagnieżdżą się bardzo głęboko. Będziesz miał piramidę i dużo zmarnowanego miejsca z dala od lewego marginesu. Możesz nawet wyjść ze strony.

Jest to problem, który miałby większe znaczenie w przeszłości, gdy ekrany były małe i niskiej rozdzielczości. W takich przypadkach nawet kilka poziomów zagnieżdżenia może rzeczywiście zająć dużo miejsca. Jest to dziś mniejszy problem, gdy próg jest wyższy, choć może nadal stanowić problem, jeśli jest wystarczająco dużo zagnieżdżenia.

Powiązany jest argument dotyczący estetyki. Wiele osób nie uważa, że ​​zagnieżdżone w pętlach są estetyczne, w przeciwieństwie do układów z bardziej spójnym wyrównaniem, które może, ale nie musi być związane z tym, do czego ludzie są przyzwyczajeni, śledzeniem wzroku i innymi problemami. Jest to jednak problematyczne, ponieważ ma tendencję do samowzmocnienia i może ostatecznie utrudniać odczytanie kodu, ponieważ rozbicie bloku kodu i zamknięcie pętli za abstrakcjami, takimi jak funkcje, również grozi rozbiciem odwzorowania kodu na przepływ wykonania.

Istnieje naturalna tendencja do tego, do czego ludzie są przyzwyczajeni. Jeśli programujesz coś w najprostszy sposób, prawdopodobieństwo braku zagnieżdżenia jest najwyższe, prawdopodobieństwo, że jeden poziom spadnie o rząd wielkości, prawdopodobieństwo dla innego poziomu ponownie spadnie. Częstotliwość spada i w gruncie rzeczy im głębsze zagnieżdżanie, tym mniej wyszkoleni ludzkie zmysły mają go przewidzieć.

Wiąże się to z tym, że w dowolnej złożonej konstrukcji, którą można rozważyć zagnieżdżoną pętlę, należy zawsze zapytać, czy jest to najprostsze możliwe rozwiązanie, ponieważ istnieje prawdopodobieństwo, że pominięte rozwiązanie będzie wymagało mniejszej liczby pętli. Ironią jest to, że zagnieżdżone rozwiązanie często jest najprostszym sposobem na wyprodukowanie czegoś, co działa przy minimalnym wysiłku, złożoności i obciążeniu poznawczym. Często gniazdowanie pętli jest naturalne. Jeśli weźmiesz na przykład jedną z powyższych odpowiedzi, w której sposób szybszy niż zagnieżdżona pętla for jest również znacznie bardziej złożony i składa się ze znacznie większej ilości kodu.

Konieczna jest duża ostrożność, ponieważ często możliwe jest wyodrębnienie pętli lub spłaszczenie ich, a efekt końcowy ostatecznie jest lekarstwem gorszym niż choroba, szczególnie jeśli na przykład nie otrzymujesz mierzalnego i znacznego zwiększenia wydajności z wysiłku.

Często zdarza się, że ludzie często doświadczają problemów z wydajnością w powiązaniu z pętlami, które nakazują komputerowi powtarzanie akcji wiele razy i z natury często są związane z wąskimi gardłami wydajności. Niestety odpowiedzi na to mogą być bardzo powierzchowne. Ludzie często widzą pętlę i widzą problem z wydajnością, gdy jej nie ma, a następnie ukrywają pętlę przed wzrokiem, aby nie mieć rzeczywistego efektu. Kod „wygląda” szybko, ale umieść go na drodze, włącz zapłon, podłóż pedał przyspieszenia i spójrz na prędkościomierz, a może się okazać, że wciąż jest tak szybki jak starsza pani chodząca po ramie zimmer.

Ten rodzaj ukrywania jest podobny do tego, jeśli masz na swojej drodze dziesięciu rabusiów. Jeśli zamiast mieć prostą drogę do miejsca, w którym chcesz się udać, ustaw go tak, aby za każdym rogiem znajdował się rabuś, to dajesz złudzenie, gdy zaczynasz swoją podróż, że nie ma rabusiów. Co z oczu to z serca. nadal będziesz atakowany dziesięć razy, ale teraz nie zobaczysz, że to nadchodzi.

Odpowiedź na twoje pytanie brzmi: jedno i drugie, ale żadna z obaw nie jest absolutna. Są albo całkowicie subiektywne, albo tylko obiektywnie kontekstowe. Niestety czasami całkowicie subiektywna lub raczej opinia ma pierwszeństwo i dominuje.

Zasadniczo, jeśli potrzebuje zagnieżdżonej pętli lub wydaje się to kolejnym oczywistym krokiem, najlepiej nie zastanawiać się i po prostu to zrobić. Jeśli jednak pozostaną jakiekolwiek wątpliwości, należy to później przejrzeć.

Inną ogólną zasadą jest to, że zawsze powinieneś sprawdzać liczność i zadawać sobie pytanie, czy ta pętla będzie problemem. W poprzednim przykładzie przeszedłem przez miasta. Do testów mogę przejść tylko dziesięć miast, ale jakiej rozsądnej maksymalnej liczby miast można się spodziewać w świecie rzeczywistym? Mógłbym wtedy pomnożyć to samo dla kontynentów. Jest to ogólna zasada, aby zawsze brać pod uwagę pętle, szczególnie, że iteruje dynamiczną (zmienną) liczbę razy, co może przełożyć się na niższą linię.

Niezależnie od tego zawsze rób to, co działa jako pierwsze. Gdy zobaczysz okazję do optymalizacji, możesz porównać zoptymalizowane rozwiązanie z najłatwiejszym do pracy i potwierdzić, że przyniosło ono oczekiwane korzyści. Możesz także spędzić zbyt długo przedwcześnie optymalizując przed zakończeniem pomiarów, co prowadzi do YAGNI lub dużej ilości zmarnowanego czasu i przekroczonych terminów.