Witam,
Spotkałem się z dziwną sytuacją. Dając taki warunek do pętli:
tab[j-1] > temp && j > 0
program wykonuje się szybciej niż przy zmienionej kolejności j > 0 && tab[j-1] > temp
Różnica może nie największa ~1650ms w stosunku do ~1800ms, ale zaciekawiło mnie dlaczego właśnie tak jest, bo przecież muszą zostać sprawdzone obydwa warunki. Może mógłby mi to ktoś wytłumaczyć.
Nie muszą.
@mark075 lektura na dziś: leniwa i gorliwa ewaluacja wyrażeń.
Gdybyś się zastanawiał jak to jest po jankesku: http://en.wikipedia.org/wiki/Short-circuit_evaluation
Teraz już rozumiem. Nawet chyba kiedyś o tym czytałem, ale zapomniałem.
Pierwsza wersja dodatkowo grozi SEGFAULTem jeżeli tab wskazuje na początek zaalokowanej strony pamięci :)
Jeśli zdarzył by się taki przypadek i wykroczono by poza tablicę to teoretycznie nie powinno się nic stać. Wtedy zostanie sprawdzony drugi warunek, który będzie nie spełniony i wykonanie instrukcji z pętli nie nastąpi. A zyskujemy szybszy czas wykonania algorytmu. Ale tu pojawia się pytanie, czy istnieją inne zagrożenia, np. system zakończy program z powodu naruszenie nie przydzielonej pamięci?
No dokładnie o to mi chodziło. Jeżeli tuż przed tym co wskazuje tab jest strona pamięci należąca do innego procesu to system sypnie ci wyjątkiem i udupi program.
Możesz np zaalokować tablicę o jeden element większą niż dotychczas i nie używać pierwszego elementu. Wtedy ta pętla będzie bezpieczna.
Poza tym nie napisałeś o jaki język chodzi. Jeżeli pisałbyś w Javie (lub analogicznie w C#) to dostałbyś wyjątek ArrayOutOfBoundsException z JVMa, który mógłbyś sobie jakoś obsłużyć.
Dzięki za wytłumaczenie, pisze w c++ i ten sposób z tablicą o 1 element większą będzie najlepszy.
Mnie troche dziwi taka konstrukcja. A to z tego powodu że kolejność warunków wcale po kompilacji nie musi się tak wykonywać, chyba że jest to określone w standardzie.
Jeśli przekazujemy coś do miejsca w tablicy warto dane wcześniej sprawdzić. W C trzeba uważać, bo kompilator bierze jak leci ;)
if ( j>0 )
if ( tab[j-1]>0 ) {
}
Moim zdaniem warto się tego nawyku w C uczyć. Nie zawsze upraszczanie do pojedynczych skomplikowanych linijek jest dobre . Zauważyłem że często tutaj popełniają ludzie błędy, a domyślnie kompilator wcale nie musi wiedzieć o co nam chodzi. ;)
Taka kolejność musi być, jest to nawet napisane na wiki, ktoś już przytoczył: http://en.wikipedia.org/wiki/Short-circuit_evaluation
A mi się to do końca nie podoba ;)
Raz że całe wyrażnie powinno się wykonać, a dwa, kompilator nie może przez to dokonywać optymalizacji.
No to chodzi o efekty uboczne, np śmierć procesu. Kompilator raczej nie może sobie takich rzeczy optymalizować. Wyraźnie jest wyspecyfikowane np, że || jest leniwym, a | jest zachłannym operatorem.
W PHP stosuje sie konstrukcje:
blablabla or die;
To jest wyrażenie logiczne. Jeżeli lewa strona jest prawdą to kompilator nie może liczyć prawej. Jeżeli zachowanie byłoby zależne od kompilacji to generalnie program by się wysypywał w losowych momentach.
Przypadków kiedy kompilator nie może dokonywać optymalizacji jest więcej, np jeżeli masz kod:
int * a;
int * b;
int * c;
*a += *b;
*c += *b;
To kompilator musi odczytać wartość *b dwukrotnie, gdyż nie wie czy a prowadzi do tego samego miejsca co b.
Im więcej zachowań kompilatora jest przewidywalnych, tym lepiej dla programistów.
wibowit napisał(a)
W PHP stosuje sie konstrukcje:
blablabla or die;
W Perlu też