Kolejność sprawdzania warunków

Założenia:

1. Dana jest tablica liczb arr[] typu int i liczba idx większa od 0 i mniejsza niż wielkość tablicy pomniejszona o 1.
2. W tablicy są różne liczby, ale często jest kilka kolejnych elementów mających tą samą liczbę.
3. Zadanie polega na znalezieniu numeru pierwszego elementu zawierającego tą sama liczbę, jaką zawiera element idx.

Pytanie jest następujące: Czy poniższy sposób rozwiązania jest bezpieczny?

int numSerie = arr[idx];

while ((idx >= 0) && (arr[idx] == numSerie))
{
    idx--;
}

idx++

Przykładowa niebezpieczna sytuacja:

int[] arr = { 7, 7, 7, 7, 5, 5, 5, 6, 6, 6};
int idx = 2;

Moim zdaniem, to, co zdarzy się po uruchomieniu powyższego kodu zależy od tego, jak kompilator zoptymalizuje linię z instrukcją while i możliwe są trzy przypadki (napiszę językiem ludzkim, tak, jakby to człowiek robił ręcznie):

1. Komputer widzi, że jest "&&" i wie, ze muszą być spełnione oba warunki. Stwierdza, że pierwszy warunek nie jest spełniony (a nie będzie spełniony dla idx = -1), więc nie ma po co sprawdzać drugiego warunku, bo i tak, niezależnie od tego, całe wyrażenie będzie fałszywe. - Program zadziała i po końcowej inkrementacji idx przyjmie 0.
2. Kompilator w ramach "optymalizacji" może odwrócić kolejność sprawdzania warunków, (&& jest przemienne, więc jaka to różnica, w jakiej kolejnosci są sprawdzane oba warunki). Program WYSYPIE SIĘ w powyższym przypadku, bo nastąpi próba odczytania elementu tablicy o indeksie -1!
3. Komputer sprawdza cały warunek poprzez ustalanie elementów składowych od najbardziej zagnieżdżonego do całości, niezależnie od kolejności zapisania warunków w kodzie. Program WYSYPIE SIĘ w powyższym przypadku!

U mnie akurat działa (testy praktyczne na Linux i OpenJDK) i zachodzi pierwsza opcja, bo program nie wysypuje się, a wysypuje się po zamianie kolejności warunków w while, ale jaką mam gwarancję, że będzie działać na każdym JDK/JVM po skompilowaniu dowolnym kompilatorem Java?

Inny przykład obrazujący ten sam problem:

String str = "Jakis tam tekst";
idx = 20;

if ((str.length() > idx) && (str.charAt(idx) == ' '))
{
    System.out.printLn("Trafiono na spację"):
}

Czy kod może wysypać się, gdy idx >= str.length()? Program zadziała poprawnie tylko w sytuacji, gdy stwierdzenie niespełnienia pierwszego warunku implikuje odstąpienie od sprawdzenia drugiego. Ale skąd mogę wiedzieć, co kompilaror faktycznie zrobi z tym kodem?

andrzejlisek napisał(a):

Założenia:

1. Dana jest tablica liczb arr[] typu int i liczba idx większa od 0 i mniejsza niż wielkość tablicy pomniejszona o 1.
2. W tablicy są różne liczby, ale często jest kilka kolejnych elementów mających tą samą liczbę.
3. Zadanie polega na znalezieniu numeru pierwszego elementu zawierającego tą sama liczbę, jaką zawiera element idx.

Czyli w skrócie chcesz znaleźć element w tablicy.

Aczkolwiek przekombinowane jest trochę Twoje rozwiązanie. Nie można czegoś takiego?

for (int value : arr) {
  if (value == idx) {
    System.out.printLn("Znaleziono."):
    break;
  }
}

andrzejlisek napisał(a):

1. Komputer widzi, że jest "&&" i wie, ze muszą być spełnione oba warunki. Stwierdza, że pierwszy warunek nie jest spełniony (a nie będzie spełniony dla idx = -1), więc nie ma po co sprawdzać drugiego warunku, bo i tak, niezależnie od tego, całe wyrażenie będzie fałszywe.
   [...]
2. Kompilator w ramach "optymalizacji" może odwrócić kolejność sprawdzania warunków, (&& jest przemienne, więc jaka to różnica, w jakiej kolejnosci są sprawdzane oba warunki). Program WYSYPIE SIĘ w powyższym przypadku, bo nastąpi próba odczytania elementu tablicy o indeksie -1!
3. Komputer sprawdza cały warunek poprzez ustalanie elementów składowych od najbardziej zagnieżdżonego do całości, niezależnie od kolejności zapisania warunków w kodzie. Program WYSYPIE SIĘ w powyższym przypadku!

U mnie akurat działa (testy praktyczne na Linux i OpenJDK) i zachodzi pierwsza opcja, bo program nie wysypuje się, a wysypuje się po zamianie kolejności warunków w while, ale jaką mam gwarancję, że będzie działać na każdym JDK/JVM po skompilowaniu dowolnym kompilatorem Java?

To nie jest "w ramach optymalizacji". Drugi warunek po && ma nie być wywołany jeśli pierwszy argument jest false. Na żadnym środowisku uruchomieniowym i kompilatorze kolejność się nie zmieni.

Zerknij na specyfikację języka rozdział 15, sekcja 23: https://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.23

The conditional-and operator && is like & (§15.22.2), but evaluates its right-hand operand only if the value of its left-hand operand is true.

Do tego co podał @Riddle dla &&&, dodałbym, że w ogólności https://docs.oracle.com/javase/specs/jls/se23/html/jls-15.html#jls-15.7 specyfikacja języka zaleca, żeby nie opierać się na tej gwarancji.

@andrzejlisek: chyba masz jakieś źródło wiedzy z błędami , szukaj w dokumentacji albo po prostu zapytacj chat GPT albo perplexity

yarel napisał(a):

Do tego co podał @Riddle dla &&&, dodałbym, że w ogólności https://docs.oracle.com/javase/specs/jls/se23/html/jls-15.html#jls-15.7 specyfikacja języka zaleca, żeby nie opierać się na tej gwarancji.

Przytaczając ten fragment:

It is recommended that code not rely crucially on this specification. Code is usually clearer when each expression contains at most one side effect, as its outermost operation, and when code does not depend on exactly which exception arises as a consequence of the left-to-right evaluation of expressions.

Faktycznie, specyfikacja nie zaleca polegania na tym, ale wygląda że tylko ze względu na przejrzystość kodu. Linijkę wyżej jest napisane że kolejność jest ustalona:

The Java programming language guarantees that the operands of operators appear to be evaluated in a specific evaluation order, namely, from left to right.

Czyli w skrócie chcesz znaleźć element w tablicy.

Aczkolwiek przekombinowane jest trochę Twoje rozwiązanie. Nie można czegoś takiego?

Pewnie, że można inaczej, jednak to nie jest zwyczajne szukanie pierwszego elementu spełniającego określony warunek. Chodzi o znalezienie początku ciągu takich samych elementów, poczynając od wskazanego.

Np tablica: { 7, 7, 7, 7, 5, 5, 5, 6, 6, 6, 7, 7, 7, 6, 6, 6}.
Dla idx=2 odpowiedzią jest 0, dla idx=11 odpowiedzią jest 10.

To nie jest "w ramach optymalizacji". Drugi warunek po && ma nie być wywołany jeśli pierwszy argument jest false. Na żadnym środowisku uruchomieniowym i kompilatorze kolejność się nie zmieni.

Zerknij na specyfikację języka rozdział 15, sekcja 23: https://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.23

O taką odpowiedź mi chodziło. Rozumiem, że skoro takie działanie jest "odgórnie" narzucone poprzez specyfikację, to mój kod nie ma prawa się wysypać.

Do tego co podał @Riddle dla &&&, dodałbym, że w ogólności https://docs.oracle.com/javase/specs/jls/se23/html/jls-15.html#jls-15.7 specyfikacja języka zaleca, żeby nie opierać się na tej gwarancji.

Dla mnie to jest wiadomo, że w takim przypadku nie należy wywoływać funkcji (ja właściwie tego nigdy nie robię), które oprócz samego zwrócenia jakiejś wartości, wykonują jakąś pracę, co skutkuje tym "side effect", choćby wypisanie tekstu na wyjściu w przypadku wywołania System.out.print("xyz") wewnątrz takiej funkcji. Rozumiem, że owe zalecenie wynika z tego, że użycie funkcji wykonujących jakąś pracę skutkuje wykonaniem lub niewykonaniem owej pracy w zależności od spełnienia innych warunków w miejscu wywołania tej funkcji. Bezpieczne jest użycie tylko takich funkcji, które nie wykonują żadnej pracy, tylko coś sprawdzają i podają wartość, a fakt sprawdzenia/niesprawdzenia nie ma wpływu na działanie programu.

andrzejlisek napisał(a):

Dla mnie to jest wiadomo, że w takim przypadku nie należy wywoływać funkcji (ja właściwie tego nigdy nie robię), które oprócz samego zwrócenia jakiejś wartości, wykonują jakąś pracę, co skutkuje tym "side effect", choćby wypisanie tekstu na wyjściu w przypadku wywołania System.out.print("xyz") wewnątrz takiej funkcji. Rozumiem, że owe zalecenie wynika z tego, że użycie funkcji wykonujących jakąś pracę skutkuje wykonaniem lub niewykonaniem owej pracy w zależności od spełnienia innych warunków w miejscu wywołania tej funkcji. Bezpieczne jest użycie tylko takich funkcji, które nie wykonują żadnej pracy, tylko coś sprawdzają i podają wartość, a fakt sprawdzenia/niesprawdzenia nie ma wpływu na działanie programu.

trochę się gryzę z tym stwierdzeniem, teoretycznie tak jest, choć praktycznie w Javie jest to bez znaczenia. Założeniem języków imperatywnych jest to, że słowa kluczowe języka są instrukcjami - a instrukcje z racji swojej natury powodują side-effecty. Więc nieistotne jest to, jak bardzo byśmy nie podpicowali definicji "expressions" w Javie, nadal to nie będą wyrażenia per se.
Zgadzam się, że pisanie funkcji ułatwia czytanie, testowanie i utrzymanie kodu. Ale tak poza tym? Jak napiszę prostą funkcję z inkrementacją ++, to już pakuję się w side-effecty, bo i++ w Javie to instrukcja

Kompilator w ramach "optymalizacji" może odwrócić kolejność sprawdzania warunków, (&& jest przemienne, więc jaka to różnica, w jakiej kolejnosci są sprawdzane oba warunki).

No właśnie ze względu na early exit nie jest przemienne i twórca kompilatora na pewno o tym wie.

Rozumiem, że owe zalecenie wynika z tego, że użycie funkcji wykonujących jakąś pracę skutkuje wykonaniem lub niewykonaniem owej pracy w zależności od spełnienia innych warunków w miejscu wywołania tej funkcji. Bezpieczne jest użycie tylko takich funkcji, które nie wykonują żadnej pracy, tylko coś sprawdzają i podają wartość, a fakt sprawdzenia/niesprawdzenia nie ma wpływu na działanie programu.

To jest bardzo dobra rada, należy tylko pamiętać, że w takiej Javie nie da się wymusić, żeby funkcja była "pure" (albo nie znam sposobu). W prostych programach utrzymanie porządku jest łatwe, ale w ogólności każdy może ci twoją "funkcję, która nie wykonuje żadnej pracy" edytować i np. zapisać coś do zmiennej globalnej.

No i w kwestii działania && to nie widzę problemu, żeby polegać na early exit, chyba że zaciemnia to kod. W sumie nie znam języka programowania, który by robił ewaluację wszystkich gałęzi w drzewku if zanim obliczy wynik.

andrzejlisek napisał(a):

Pytanie jest następujące: Czy poniższy sposób rozwiązania jest bezpieczny?

Kopiuj

while ((idx >= 0) && (arr[idx] == numSerie))
{
    idx--;
}
[...]
Moim zdaniem, to, co zdarzy się po uruchomieniu powyższego kodu zależy od tego, jak kompilator zoptymalizuje linię z instrukcją `while` i możliwe są trzy przypadki (napiszę językiem ludzkim, tak, jakby to człowiek robił ręcznie):
1. Komputer widzi, że jest "&&" i wie, ze muszą być spełnione oba warunki. Stwierdza, że pierwszy warunek nie jest spełniony (a nie będzie spełniony dla `idx = -1`), więc nie ma po co sprawdzać drugiego warunku, bo i tak, niezależnie od tego, całe wyrażenie będzie fałszywe. - **Program zadziała i po końcowej inkrementacji idx przyjmie 0.**
2. Kompilator w ramach "optymalizacji" może odwrócić kolejność sprawdzania warunków, (&& jest przemienne, więc jaka to różnica, w jakiej kolejnosci są sprawdzane oba warunki). **Program WYSYPIE SIĘ w powyższym przypadku, bo nastąpi próba odczytania elementu tablicy o indeksie -1!**
3. Komputer sprawdza cały warunek poprzez ustalanie elementów składowych od najbardziej zagnieżdżonego do całości, niezależnie od kolejności zapisania warunków w kodzie. **Program WYSYPIE SIĘ w powyższym przypadku!**

U mnie akurat działa (testy praktyczne na Linux i OpenJDK) i zachodzi pierwsza opcja, bo program nie wysypuje się, a wysypuje się po zamianie kolejności warunków w `while`, ale **jaką mam gwarancję, że będzie działać na każdym JDK/JVM po skompilowaniu dowolnym kompilatorem Java**?

Kompletnie błędne jest założenie, że operacje takie jak && i || są przemienne. Wystarczy zajrzeć do specyfikacji języka.
Kolejne wyrażenia są opracowywane od lewej do prawej i kończone na tym wyrażeniu, które decyduje o wartości false dla && lub true dla ||.
Kompilator może sobie różne rzeczy optymalizować, ale musi nadal zgodnie ze specyfikacją języka. Nie ma możliwości zamiany opracowywania wyrażeń operatorów logicznych bo zmienia to semantykę wyrażenia. To samo można zobaczyć np. w podpowiedziach IDE.

Czy kod może wysypać się, gdy idx >= str.length()? Program zadziała poprawnie tylko w sytuacji, gdy stwierdzenie niespełnienia pierwszego warunku implikuje odstąpienie od sprawdzenia drugiego. Ale skąd mogę wiedzieć, co kompilaror faktycznie zrobi z tym kodem?

Wystarczy dobry podręcznik do Javy i specyfikacja języka. Tam można się dokładnie dowiedzieć co kompilator zrobi z takim kodem.
Zakładanie opracowywania wyrażenia po && lub || jest błędem bo jest dokładnie odwrotnie.
Każda operacja z = x && y; może zostać wprost zamieniona na z = false; if(x) if(y) z = true,
a z logicznej równoważności x || y == !x && !y to samo można zrobić z operacją ||.