DejaVu |
» 2011-01-26 20:49:06 Wiesz... ja akurat mierzę czas za pomocą QueryPerformanceCounter, także nie ma mowy o niedokładności pomiaru - co najwyżej o bardziej lub mniej obciążonym procku :) anyway myślę że dłuższa walka na temat tego że rekurencja wcale nie jest taka zła nie ma sensu. Udowodniłem dwukrotnie, że kod pisany rekurencyjnie wcale nie będzie gorszy wydajnościowo niż rozwiązanie iteracyjne, a nawet algorytm rekurencyjny potrafi być wydajniejszy niż równoważny iteracyjny. |
|
Elaine |
» 2011-01-26 21:52:04 To wciąż jest porównanie iteracji z iteracją, różnica wynika albo z tego, że kompilator wygenerował dla tych pętli różne kody (i poprzez niewielkie zmiany w kodzie możnaby sprawić, że będą takie same), albo po prostu z warunków losowych, jak na przykład procesy działające w tle (różnica to 2.5%, więc to jest bardzo prawdopodobne).
Skąd wiadomo, że to pętla? Obliczany jest wyraz numer czterysta milionów, stos by tego nie wytrzymał, o czym można się przekonać na przykład w trybie debug.
Przede wszystkim, należy pamiętać, że mówimy tu o rekurencji w kontekście C++. Ten język nie nadaje się zbyt dobrze do zabaw z rekurencją, nawet, jeśli wygląda ona na ogonową - wystarczy jeden nietrywialny destruktor i ogonowość szlag trafia, kompilator nie będzie w stanie tego zoptymalizować nawet, gdyby chciał.
Nawet, jeśli rekurencja jest faktycznie ogonowa, to i tak nie ma gwarancji, że zostanie zoptymalizowana - język tego nie wymaga, to jest tylko dobra wola twórców kompilatora i nastąpi tylko przy kompilacji z optymalizacjami i tylko, jeśli kompilator to wspiera. Dla porównania, w językach funkcyjnych ta optymalizacja (podobnie jak kilka innych optymalizacji związanych z rekurencją) jest wymagana przez język - języki te silnie zależą od rekurencji, więc trzeba zapewnić, że przepełnie stosu nie nastąpi nawet przy wyłączonych optymalizacjach.
| Udowodniłem dwukrotnie, że kod pisany rekurencyjnie wcale nie będzie gorszy wydajnościowo niż rozwiązanie iteracyjne, a nawet algorytm rekurencyjny potrafi być wydajniejszy niż równoważny iteracyjny. |
Raz udowodniłeś, że rekurencja oparta o systemowy stos jest wydajniejsza od rekurencji opartej o std::stack<>, a raz udowodniłeś, że jedna pętla jest niewiele szybsza od drugiej. Skompiluj dla porównania tego Fibonacciego w trybie debug, wtedy faktycznie będzie to rekurencja - zobaczysz, że nastąpi przepełnienie stosu.
Ciągle też czekam na odpowiedź na pytanie: skoro rekurencja jest lepsza od iteracji, to dlaczego kompilatory optymalizują rekurencję ogonową do postaci pętli? |
|
ThudPoland |
» 2011-01-26 22:18:38 Teraz kolej na mój jakże powalony program mający sporo bugów i udowadniający że w wielu przypadkach lepsza jest iteracja. #include <iostream>
#include <ctime>
#include <vector>
using namespace std;
unsigned int CollatzLoop( unsigned int Value )
{
while( Value != 1 )
{
if( Value % 2 == 1 ) Value =( Value * 3 ) + 1;
else if( Value % 2 == 0 ) Value /= 2;
}
return Value;
}
unsigned int CollatzRecusive( unsigned int Value )
{
if( Value != 1 )
{
if( Value % 2 == 1 ) CollatzRecusive(( Value * 3 ) + 1 );
else if( Value % 2 == 0 ) CollatzRecusive( Value / 2 );
}
return Value;
}
unsigned long TestTimeOfAlgorithm( unsigned int( * Function )( unsigned int ), int NumberOfTests )
{
clock_t StartTime = clock();
for( int Loop = NumberOfTests; Loop > 0; Loop-- )
{
Function( Loop );
}
return static_cast < unsigned long >(( clock() - StartTime ) * CLOCKS_PER_SEC / 1000000000 );
}
void CompareTimes( const vector < unsigned long > Vector[ 2 ] )
{
if( Vector[ 0 ].size() == Vector[ 1 ].size() )
{
cout << "Ok, bedzie dzialac!" << endl;
for( unsigned int Loop = 0; Loop < Vector[ 0 ].size(); Loop++ )
{
cout << "Dla testu nr " << Loop + 1 << ": ";
if( Vector[ 0 ][ Loop ] < Vector[ 1 ][ Loop ] ) cout << "Pierwszy algorytm byl szybszy o: " << Vector[ 1 ][ Loop ] - Vector[ 0 ][ Loop ] << endl;
else if( Vector[ 0 ][ Loop ] > Vector[ 1 ][ Loop ] ) cout << "Drugi algorytm byl szybszy o: " << Vector[ 0 ][ Loop ] - Vector[ 1 ][ Loop ] << endl;
else cout << "Oba algorytmy zostaly wykonane w tym samym czasie" << endl;
}
}
else cout << "Ups. cos nie tak" << endl;
}
int main()
{
vector < unsigned long > TimeVector[ 2 ];
for( int Loop = 0; Loop < 750000; Loop += 10000 )
{
TimeVector[ 0 ].push_back( TestTimeOfAlgorithm( CollatzLoop, Loop ) );
TimeVector[ 1 ].push_back( TestTimeOfAlgorithm( CollatzRecusive, Loop ) );
}
CompareTimes( TimeVector );
return 0;
} Powalony kod ale realizuje to o co chodzi. Proszę mnie za niego nie krytykować. Panie Iname zachowaj komentarze dla siebie. :D Tutaj macie loga całości dla mojego kompa. Każdy kto zna się na programowaniu będzie znał ideę akurat tego programu i domyśli się o co chodzi: Ok, bedzie dzialac!
Dla testu nr 1: Oba algorytmy zostaly wykonane w tym samym czasie
Dla testu nr 2: Drugi algorytm byl szybszy o: 10
Dla testu nr 3: Pierwszy algorytm byl szybszy o: 10
Dla testu nr 4: Oba algorytmy zostaly wykonane w tym samym czasie
Dla testu nr 5: Pierwszy algorytm byl szybszy o: 20
Dla testu nr 6: Pierwszy algorytm byl szybszy o: 30
Dla testu nr 7: Pierwszy algorytm byl szybszy o: 20
Dla testu nr 8: Pierwszy algorytm byl szybszy o: 30
Dla testu nr 9: Pierwszy algorytm byl szybszy o: 40
Dla testu nr 10: Pierwszy algorytm byl szybszy o: 30
Dla testu nr 11: Pierwszy algorytm byl szybszy o: 40
Dla testu nr 12: Pierwszy algorytm byl szybszy o: 40
Dla testu nr 13: Pierwszy algorytm byl szybszy o: 50
Dla testu nr 14: Pierwszy algorytm byl szybszy o: 60
Dla testu nr 15: Pierwszy algorytm byl szybszy o: 60
Dla testu nr 16: Pierwszy algorytm byl szybszy o: 60
Dla testu nr 17: Pierwszy algorytm byl szybszy o: 80
Dla testu nr 18: Pierwszy algorytm byl szybszy o: 70
Dla testu nr 19: Pierwszy algorytm byl szybszy o: 90
Dla testu nr 20: Pierwszy algorytm byl szybszy o: 90
Dla testu nr 21: Pierwszy algorytm byl szybszy o: 80
Dla testu nr 22: Pierwszy algorytm byl szybszy o: 100
Dla testu nr 23: Pierwszy algorytm byl szybszy o: 100
Dla testu nr 24: Pierwszy algorytm byl szybszy o: 100
Dla testu nr 25: Pierwszy algorytm byl szybszy o: 120
Dla testu nr 26: Pierwszy algorytm byl szybszy o: 110
Dla testu nr 27: Pierwszy algorytm byl szybszy o: 120
Dla testu nr 28: Pierwszy algorytm byl szybszy o: 130
Dla testu nr 29: Pierwszy algorytm byl szybszy o: 130
Dla testu nr 30: Pierwszy algorytm byl szybszy o: 130
Dla testu nr 31: Pierwszy algorytm byl szybszy o: 150
Dla testu nr 32: Pierwszy algorytm byl szybszy o: 160
Dla testu nr 33: Pierwszy algorytm byl szybszy o: 150
Dla testu nr 34: Pierwszy algorytm byl szybszy o: 160
Dla testu nr 35: Pierwszy algorytm byl szybszy o: 160
Dla testu nr 36: Pierwszy algorytm byl szybszy o: 180
Dla testu nr 37: Pierwszy algorytm byl szybszy o: 180
Dla testu nr 38: Pierwszy algorytm byl szybszy o: 180
Dla testu nr 39: Pierwszy algorytm byl szybszy o: 190
Dla testu nr 40: Pierwszy algorytm byl szybszy o: 200
Dla testu nr 41: Pierwszy algorytm byl szybszy o: 190
Dla testu nr 42: Pierwszy algorytm byl szybszy o: 200
Dla testu nr 43: Pierwszy algorytm byl szybszy o: 210
Dla testu nr 44: Pierwszy algorytm byl szybszy o: 210
Dla testu nr 45: Pierwszy algorytm byl szybszy o: 230
Dla testu nr 46: Pierwszy algorytm byl szybszy o: 230
Dla testu nr 47: Pierwszy algorytm byl szybszy o: 230
Dla testu nr 48: Pierwszy algorytm byl szybszy o: 240
Dla testu nr 49: Pierwszy algorytm byl szybszy o: 230
Dla testu nr 50: Pierwszy algorytm byl szybszy o: 250
Dla testu nr 51: Pierwszy algorytm byl szybszy o: 260
Dla testu nr 52: Pierwszy algorytm byl szybszy o: 270
Dla testu nr 53: Pierwszy algorytm byl szybszy o: 260
Dla testu nr 54: Pierwszy algorytm byl szybszy o: 260
Dla testu nr 55: Pierwszy algorytm byl szybszy o: 260
Dla testu nr 56: Pierwszy algorytm byl szybszy o: 290
Dla testu nr 57: Pierwszy algorytm byl szybszy o: 300
Dla testu nr 58: Pierwszy algorytm byl szybszy o: 300
Dla testu nr 59: Pierwszy algorytm byl szybszy o: 300
Dla testu nr 60: Pierwszy algorytm byl szybszy o: 310
Dla testu nr 61: Pierwszy algorytm byl szybszy o: 300
Dla testu nr 62: Pierwszy algorytm byl szybszy o: 320
Dla testu nr 63: Pierwszy algorytm byl szybszy o: 320
Dla testu nr 64: Pierwszy algorytm byl szybszy o: 340
Dla testu nr 65: Pierwszy algorytm byl szybszy o: 330
Dla testu nr 66: Pierwszy algorytm byl szybszy o: 340
Dla testu nr 67: Pierwszy algorytm byl szybszy o: 340
Dla testu nr 68: Pierwszy algorytm byl szybszy o: 350
Dla testu nr 69: Pierwszy algorytm byl szybszy o: 360
Dla testu nr 70: Pierwszy algorytm byl szybszy o: 370
Dla testu nr 71: Pierwszy algorytm byl szybszy o: 360
Dla testu nr 72: Pierwszy algorytm byl szybszy o: 370
Dla testu nr 73: Pierwszy algorytm byl szybszy o: 380
Dla testu nr 74: Pierwszy algorytm byl szybszy o: 390
Dla testu nr 75: Pierwszy algorytm byl szybszy o: 400 Zastanawiam się tylko nad jedną rzeczą... Czemu tak mocno musiałem podzielić całość "przebytego" czasu w funkcji Test... |
|
DejaVu |
» 2011-01-26 22:38:31 Ja dostałem czasy równoważne dla wszystkich testów po skompilowaniu tego w release. Poza tym myślę, że tu nie chodzi już o to czy iteracja jest lepsza czy nie. Faktem jest po prostu, że nie należy na siłę robić algorytmów iteracyjnych jeżeli rekurencja sprawdza się dobrze. Quicksort jest tego najlepszym przykładem. Oczywiście, że rekurencja ma swoje wady, jednak są przypadki w których jest ona dużo fajniejsza i uzyskuje się lepsze efekty.
/edit:
Stosowną puentę w sumie dał Uland i dlatego uważam, że nie ma sensu dłużej ciągnąć tematu. Rekurencja została w tym temacie poruszona zarówno od strony teoretycznej jak i praktycznej. Co więcej mieliśmy gry i zabawy z wydajnością oraz różne poglądy na ten temat. Myślę, że temat sam w sobie zawiera sporo wartościowych informacji dla przeciętnego czytelnika i można by było się nawet pokusić o napisanie szerszego artykułu na temat rekurencji na bazie tego co zostało tutaj napisane. Brakuje tylko wniosków ;p |
|
ThudPoland |
» 2011-01-26 22:46:42 Dobrz, to ja to sprawdzę.
Release nic u mnie nie dało. Nadal mam jasne porółnanie że oba algorytmy nie wykonują się tak samo szybko. Spróbuje Pan zmienić wartość 1000000000 na 1000, bo właśnie u mnie coś nie tak w algorytmie Test... I jedynie tak mi poprawnie działa.
//Edit:
Mam pomysł na konkurs - jak najlepszy artykuł o rekurencji. ;) |
|
Elaine |
» 2011-01-26 22:49:15 Czasy uzyskane z tego kodu nie mają większego sensu - CollatzRecursive() robi zupełnie co innego niż CollatzLoop().
Wniosek poprawny, ale warto dodać, że tak samo jest w drugą stronę - nie należy używać na siłę rekurencji tam, gdzie iteracja sprawdza się dobrze. |
|
DejaVu |
» 2011-01-26 22:51:24 Ale konkurs z którego jest tylko jedno 'dziecko' to słaby konkurs ;p |
|
McAffey |
» 2011-01-27 00:54:28 Trochę mi nie zręcznie tak pisać do Pana Piotra, ale ten temat ma już 5 stron i wydaje mi się, że offtopic to nie jest dobry pomysł ;p |
|
| 1 2 3 4 « 5 » 6 |