Pozornie nieskończona pętla się kończy, chyba że zostanie użyty System.out.println

91

Miałem prosty fragment kodu, który miał być nieskończoną pętlą, ponieważ xzawsze będzie się rozwijał i zawsze pozostanie większy niż j.

int x = 5;
int y = 9;
for (int j = 0; j < x; j++) {
   x = x + y;
}
System.out.println(y);

ale tak jak jest, drukuje yi nie zapętla się w nieskończoność. Nie wiem, dlaczego. Jednak gdy dostosowuję kod w następujący sposób:

int x = 5;
int y = 9;
for (int j = 0; j < x; j++) {
    x = x + y;
    System.out.println(y);
}
System.out.println(y);

Staje się nieskończoną pętlą i nie mam pojęcia, dlaczego. Czy java rozpoznaje swoją nieskończoną pętlę i pomija ją w pierwszej sytuacji, ale musi wykonać wywołanie metody w drugiej, aby zachowywała się zgodnie z oczekiwaniami? Zmieszany :)

Omar
źródło
4
Druga pętla jest nieskończona, ponieważ górna granica xrośnie szybciej niż zmienna pętli j. Innymi słowy, jnigdy nie osiągnie górnej granicy, stąd pętla będzie działać „na zawsze”. Cóż, nie na zawsze, najprawdopodobniej w pewnym momencie dojdzie do przepełnienia.
Tim Biegeleisen
75
To nie jest nieskończona pętla, po prostu potrzeba 238609294 razy, aby wyjść z pętli for w pierwszym przypadku, a za drugim razem wypisuje wartość y238609294 razy
N00b Pr0grammer
13
odpowiedź jednym słowem: przepełnienie
qwr
20
Zabawne, System.out.println(x)zamiast yna koniec od razu pokazałoby, na czym polega problem
JollyJoker
9
@TeroLahtinen nie, nie byłoby. Przeczytaj specyfikację języka Java, jeśli masz wątpliwości, co to jest typ int. Jest niezależny od sprzętu.
9ilsdx 9rvj 0lo

Odpowiedzi:

161

Oba przykłady nie są nieskończone.

Problem polega na ograniczeniu inttypu w Javie (lub prawie każdym innym powszechnym języku). Gdy wartość xosiąga 0x7fffffff, dodanie jakiejkolwiek wartości dodatniej spowoduje przepełnienie i stanie xsię ujemne, a zatem niższe niż j.

Różnica między pierwszą a drugą pętlą polega na tym, że kod wewnętrzny zajmuje znacznie więcej czasu i prawdopodobnie zajmie kilka minut, zanim xprzepełnienie. W pierwszym przykładzie może to zająć mniej niż sekundę lub najprawdopodobniej kod zostanie usunięty przez optymalizator, ponieważ nie ma to żadnego efektu.

Jak wspomniano w dyskusji, czas będzie w dużej mierze zależał od tego, jak system operacyjny buforuje dane wyjściowe, czy wysyła do emulatora terminala itp., Więc może być znacznie dłuższy niż kilka minut.

Zbynek Vyskovsky - kvr000
źródło
48
Właśnie wypróbowałem program (na moim laptopie), który drukuje wiersz w pętli. Zmierzyłem czas i był w stanie wydrukować około 1000 linii na sekundę. Opierając się na komentarzu N00b, że pętla wykona 238609294 razy, zakończenie pętli zajmie około 23861 sekund - ponad 6,6 godziny. Trochę więcej niż „kilka minut”.
ajb
11
@ajb: Zależy od implementacji. IIRC println()w systemie Windows jest operacją blokującą, podczas gdy na (niektórych?) Uniksie jest buforowany, więc działa znacznie szybciej. Spróbuj także użyć print(), które buforuje, dopóki nie trafi \n(lub bufor się flush()
zapełni
6
Zależy to również od terminala pokazującego wyjście. Zobacz stackoverflow.com/a/21947627/53897, aby zapoznać się z ekstremalnym przykładem (gdzie spowolnienie było spowodowane zawijaniem słów)
Thorbjørn Ravn Andersen
1
Tak, jest buforowany w systemie UNIX, ale nadal blokuje. Gdy bufor 8K lub więcej się zapełni, będzie blokowany, aż będzie miejsce. Szybkość będzie silnie zależna od tego, jak szybko zostanie zużyty. Przekierowanie wyjścia do / dev / null będzie najszybsze, ale wysłanie go do terminala, domyślnie, będzie wymagało aktualizacji grafiki na ekranie i znacznie większej mocy obliczeniowej, ponieważ renderuje czcionki spowalniające.
pingwin 359
2
@Zbynek oh, prawdopodobnie tak, ale to mi przypomina, terminale I / O zwykle będą buforowane liniowo, a nie blokowo, więc najprawdopodobniej każdy println spowoduje dalsze spowolnienie wywołania systemowego.
pingwin 359
33

Ponieważ są one zadeklarowane jako int, po osiągnięciu maksymalnej wartości pętla zostanie przerwana, ponieważ wartość x stanie się ujemna.

Ale kiedy System.out.println zostanie dodany do pętli, prędkość wykonania staje się widoczna (ponieważ wyjście do konsoli spowolni szybkość wykonywania). Jeśli jednak pozwolisz drugiemu programowi (temu z syso wewnątrz pętli) działać wystarczająco długo, powinien on zachowywać się tak samo jak pierwszy (ten bez syso wewnątrz pętli).

Ace Zachary
źródło
21
Ludzie nie zdają sobie sprawy, ile spamowania na konsoli może spowolnić ich kod.
user9993
13

Mogą być ku temu dwa powody:

  1. Java optymalizuje forpętlę, a ponieważ po pętli nie jest używana, xpo prostu ją usuwa. Możesz to sprawdzić, umieszczając System.out.println(x);instrukcję po pętli.

  2. Może się zdarzyć, że Java w rzeczywistości nie optymalizuje pętli i poprawnie wykonuje program i ostatecznie xbędzie zbyt duży inti przepełniony. Przepełnienie liczb całkowitych najprawdopodobniej spowoduje, że liczba całkowita xbędzie ujemna, która będzie mniejsza od j, a więc wyjdzie z pętli i wypisze wartość y. Można to również sprawdzić, dodając System.out.println(x);po pętli.

Ponadto nawet w pierwszym przypadku ostatecznie nastąpi przepełnienie, co spowoduje przeniesienie go do drugiego przypadku, więc nigdy nie będzie to prawdziwa nieskończona pętla.

Ashok Vishnoi
źródło
14
Wybieram drzwi numer 2.
Robby Cornelissen
Prawdziwe. Poszedł na ujemną skalę i wyszedł z pętli. Ale a sysoutjest tak powolny, aby dodać iluzję nieskończonej pętli.
Pavan Kumar
4
1. Byłby to błąd. Optymalizacje kompilatora nie mogą zmienić zachowania programu. Jeśli byłaby to nieskończona pętla, kompilator może zoptymalizować wszystko, czego chce, jednak wynik nadal musi być nieskończoną pętlą. Prawdziwym rozwiązaniem jest to, że OP się myli: żadna z nich nie jest nieskończoną pętlą, jedna po prostu wykonuje więcej pracy niż druga, więc trwa dłużej.
Jörg W Mittag
1
@ JörgWMittag W tym przypadku x jest zmienną lokalną, która nie ma żadnego związku z niczym innym. W związku z tym możliwe jest, że jest zoptymalizowany. Ale należy spojrzeć na kod bajtowy, aby określić, czy tak jest, a nigdy nie zakładać, że kompilator zrobił coś takiego.
Miejmy nadzieję, że
1

Obie nie są nieskończonymi pętlami, początkowo j = 0, o ile j <x, j rośnie (j ++), a j jest liczbą całkowitą, więc pętla działałaby do momentu osiągnięcia maksymalnej wartości, a następnie przepełnienia (warunkiem jest przepełnienie całkowite która ma miejsce, gdy wynik operacji arytmetycznej, takiej jak mnożenie lub dodawanie, przekracza maksymalny rozmiar typu liczby całkowitej użytej do jej przechowywania). w drugim przykładzie system po prostu wypisuje wartość y do momentu przerwania pętli.

jeśli szukasz przykładu nieskończonej pętli, powinno to wyglądać tak

int x = 6;

for (int i = 0; x < 10; i++) {
System.out.println("Still Looping");
}

ponieważ (x) nigdy nie osiągnąłby wartości 10;

możesz też stworzyć nieskończoną pętlę z podwójną pętlą for:

int i ;

  for (i = 0; i <= 10; i++) {
      for (i = 0; i <= 5; i++){
         System.out.println("Repeat");   
      }
 }

ta pętla jest nieskończona, ponieważ pierwsza pętla for mówi i <10, co jest prawdą, więc przechodzi do drugiej pętli for, a druga pętla for zwiększa wartość (i), aż będzie == 5. Następnie przechodzi do pierwszej for ponownie, ponieważ i <10, proces powtarza się, ponieważ resetuje się po drugiej pętli for

Kennedy
źródło
1

Jest to pętla skończona, ponieważ gdy wartość xprzekracza 2,147,483,647(która jest wartością maksymalną a int), xstanie się ujemna i nie będzie większa j, niezależnie od tego, czy drukujesz y, czy nie.

Możesz po prostu zmienić wartość yto 100000i wydrukować yw pętli, a pętla wkrótce się zepsuje.

Powodem, dla którego czujesz, że stało się to nieskończone, jest to, że System.out.println(y);kod wykonywał się znacznie wolniej niż bez żadnych działań.

Joe Cheng
źródło
0

Ciekawy problem Właściwie w obu przypadkach pętla nie jest nieskończona

Ale główna różnica między nimi polega na tym, kiedy zakończy się i ile czasu xzajmie przekroczenie maksymalnej intwartości, 2,147,483,647po której osiągnie stan przepełnienia i pętla się zakończy.

Najlepszym sposobem zrozumienia tego problemu jest przetestowanie prostego przykładu i zachowanie jego wyników.

Przykład :

for(int i = 10; i > 0; i++) {}
System.out.println("finished!");

Wynik:

finished!
BUILD SUCCESSFUL (total time: 0 seconds)

Po przetestowaniu tej nieskończonej pętli zakończenie zajmie mniej niż 1 sekundę.

for(int i = 10; i > 0; i++) {
    System.out.println("infinite: " + i);
}
System.out.println("finished!");

Wynik:

infinite: 314572809
infinite: 314572810
infinite: 314572811
.
.
.
infinite: 2147483644
infinite: 2147483645
infinite: 2147483646
infinite: 2147483647
finished!
BUILD SUCCESSFUL (total time: 486 minutes 25 seconds)

W tym przypadku testowym zauważysz ogromną różnicę w czasie zamykania i kończenia działania programu.

Jeśli nie masz cierpliwości, pomyślisz, że ta pętla jest nieskończona i nie zakończy się, ale w rzeczywistości jej zakończenie i osiągnięcie stanu przepełnienia przy iwartości zajmie kilka godzin .

Wreszcie, po umieszczeniu instrukcji print wewnątrz pętli for, doszliśmy do wniosku, że zajmie to znacznie więcej czasu niż pętla w pierwszym przypadku bez instrukcji print.

Czas potrzebny na uruchomienie programu zależy od specyfikacji komputera, w szczególności mocy obliczeniowej (pojemności procesora), systemu operacyjnego i IDE, które kompiluje program.

Testuję ten przypadek na:

Lenovo 2,7 GHz Intel Core i5

System operacyjny: Windows 8.1 64x

IDE: NetBeans 8.2

Zakończenie programu zajmuje około 8 godzin (486 minut).

Możesz również zauważyć, że krok zwiększa się w pętli for i = i + 1 jest bardzo wolnym czynnikiem, aby osiągnąć maksymalną wartość int.

Możemy zmienić ten współczynnik i przyspieszyć przyrost kroku, aby przetestować pętlę w krótszym czasie.

jeśli to umieścimy i = i * 10i przetestujemy:

for(int i = 10; i > 0; i*=10) {
           System.out.println("infinite: " + i);
}
     System.out.println("finished!");

Wynik:

infinite: 100000
infinite: 1000000
infinite: 10000000
infinite: 100000000
infinite: 1000000000
infinite: 1410065408
infinite: 1215752192
finished!
BUILD SUCCESSFUL (total time: 0 seconds)

Jak widać, jest to bardzo szybkie w porównaniu z poprzednią pętlą

zakończenie i zakończenie działania programu zajmuje mniej niż 1 sekundę.

Po tym przykładzie testowym myślę, że powinno to wyjaśnić problem i udowodnić słuszność Zbynka Vyskovsky'ego - odpowiedź kvr000 , również będzie odpowiedzią na to pytanie .

Oghli
źródło