algorytmy rekurencyjne
Logowanie
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zapomniałem hasła
» Forum » Programowanie » [C, C++] Inne

algorytmy rekurencyjne

Ostatnio zmodyfikowano 2014-08-19 17:29
Autor Wiadomość
ison
» 2011-01-26 19:33:21
@up podaj kod Fibonacciego rekurencyjnego, który nie będzie działał w czasie wykładniczym ;)
P-27152
Elaine
» 2011-01-26 19:37:51
Sam przecież chciałeś tego porównania, dlaczego nagle coś ci nie pasuje? ;P
P-27153
DejaVu
» 2011-01-26 19:49:28
Proszę bardzo Fibonaci rekurencyjnie z algorytmem liniowym:
C/C++
unsigned fiblimit( unsigned x, unsigned last2 = 0, unsigned last1 = 0 )
{
    if( x <= 0 )
         return last1;
   
    if( last1 == 0 )
         last2 = 1;
   
    return fiblimit( x - 1, last1, last1 + last2 );
}
//Wywołanie:
printf( "%d\n", fiblimit( 40 ) );
P-27155
Elaine
» 2011-01-26 19:56:49
Proszę bardzo:
C/C++
#include <ctime>
#include <cstdio>
using namespace std;

unsigned fibrPrim( unsigned n, unsigned n1, unsigned n2 )
{
    if( n == 0 ) return n2;
   
    return fibrPrim( n - 1, n2, n1 + n2 );
}

unsigned fibr( unsigned x )
{
    if( x == 0 ) return 0;
   
    if( x == 1 ) return 1;
   
    return fibrPrim( x - 1, 0, 1 );
}

unsigned fibi( unsigned x )
{
    if( x == 0 ) return 0;
   
    if( x == 1 ) return 1;
   
    unsigned n1 = 0, n2 = 1;
    for( --x; x != 0; --x )
    {
        unsigned temp = n1 + n2;
        n1 = n2;
        n2 = temp;
    }
   
    return n2;
}

void test( unsigned( * fn )( unsigned ) )
{
    clock_t start = clock();
    volatile unsigned result = fn( 1000000000 );
    printf( "%ldms\n", static_cast < long >( clock() - start ) * CLOCKS_PER_SEC / 1000 );
}

int main()
{
    test( fibr );
    test( fibi );
}

Tym razem wyniki od GCC 4.5.2 (-O3):
668ms
667ms
...ale zaraz. Oto wygenerowany kod dla funkcji fibr:
push ebp
xor eax, eax
mov ebp, esp
push ebx
mov edx, [ebp+arg_0]
test edx, edx
jz short loc_2A
cmp edx, 1
mov al, 1
jz short loc_2A
dec edx
jz short loc_2A
mov ecx, 1
xor ebx, ebx
jmp short loc_24
loc_20:
mov ebx, ecx
mov ecx, eax
loc_24:
dec edx
lea eax, [ecx+ebx]
jnz short loc_20
loc_2A:
pop ebx
leave
retn
Jak widać, kompilator zrobił z tego pętlę (kod funkcji fibi jest taki sam). Czyli mamy porównanie iteracji z iteracją. Chyba nie o to chodziło, nie? ;>

Ponawiam pytanie: jeśli rekurencja jest taka dobra, to dlaczego kompilatory starają się optymalizować rekurencję ogonową do postaci pętli (i, jak widać wyżej, czasami im się to udaje; acz nie wszystkie kompilatory to robią (w trybie debug nie robi żaden, oh hai stack overflow!), a tym, które robią, nie zawsze się to udaje)? ;>
P-27156
jsc
» 2011-01-26 20:03:02
Nie doprowadziliśmy tego do absurdu?

Skoro mamy pętla kontra identyczna pętla. To powinniśmy stosować inne kryteria wyboru konkretnego algorytmu.
P-27158
DejaVu
» 2011-01-26 20:37:55
C/C++
unsigned iTestFib = 400000000;

prepare( & vLista[ 0 ], vLista.size() );
show( & vLista[ 0 ], vLista.size() );
time.Set( 0 );
iResult = fibi( iTestFib );
time.Update();
printf( "Iteracyjny Fibonaci: %lf; wynik = %d\n",( double ) time.Get(), iResult );
show( & vLista[ 0 ], vLista.size() );

prepare( & vLista[ 0 ], vLista.size() );
show( & vLista[ 0 ], vLista.size() );
time.Set( 0 );
iResult = fiblimit( iTestFib );
time.Update();
printf( "Rekurencyjny Fibonaci2: %lf; wynik = %d\n",( double ) time.Get(), iResult );
show( & vLista[ 0 ], vLista.size() );
Pod Visualem mimo wszystko i tak rekurencyjny jest nieznacznie szybszy (Release):
Iteracyjny Fibonaci: 0.488922; wynik = 425843259
Rekurencyjny Fibonaci2: 0.476193; wynik = 425843259
P-27164
Uland
Może inaczej?
» 2011-01-26 20:41:35
Trzeba wyróżnić parę rzeczy:

@pytający

Rekurencja i jej zachowanie:
W miejscu, gdzie wywołujesz funkcję rekurencyjnie obecna przerywa działanie, aż do momentu kiedy wywołana funkcja się skończy i ew. zwróci wynik.

A więc:

C/C++
void f( int x )
{
    printf( "START %d\n", x );
    if( x == 0 )
         return;
   
    f( x - 1 );
    printf( "KONIEC %d\n", x );
}
wywołanie f(4) wypisze:
START 4
START 3
START 2
START 1
START 0
KONIEC 1
KONIEC 2
KONIEC 3
KONIEC 4


@reszta

Są dwie kwestie:
algorytm:

Generalnie rekurencję wymyślono długo przed jak wymyślono programowaniem i od początku było to wygodne narzędzie matematyczne...
Często bezpośrednie implementacje oryginalnych rekurencyjnych matematyczne definicji (np. takie jak w ciągu Fibonacciego) nie sa zbyt wydajne, ale dla innych problemów rozwiązania bazujące na rekurencji mogą być wydajniejsze.
Trudno mówić o wydajności rekurencji w algorytmicznym sensie -> jest to po prostu jedna z metod definiowania pojęć.

Jest przy tym czasem bardzo elegancka z kilku powodów:
-Niektóre algorytmy/struktury sa naturalnie rekurenyjne - drzewa, mergesort, quicksort, poniekąd dfs...
-Zapewnią pewną abstrakcje, co znacznie upraszcza dowody poprawności
-Nie musi jawnie wprowadzać pojęcia czasu i obliczeń (bardzo wygodne w niektórych przypadkach, np. obliczeń rozproszonych, patrz języki czysto funkcyjne)

implementacja:
Każdą iterację można zastąpić rekurencją. Rekurencję też można bez problemu zaimplementować za pomocą stosu bez jej wsparcia z poziomu języka (patrz FORTRAN i qsort2 od DejaVu). Języki czysto funkcyjne o których wspomniałem wcześniej nie wprowadzaja pojęć typowych dla programów imperatywnych (albo o częściach imperatywnych), opierają się na rekurencji i wyrażeniach lambda.

Co do wydajności to bardzo zależy od konkretnego przypadku. Generalnie każde wywołanie funkcji potrzebuje pewnej ilości pamięci (dokładna wartość zależy od kilku czynników) . Czasem można całkowicie się tego narzutu pozbyć lub go ograniczyć. (np. zwijając rekurencję ogonową do iteracji, co jest podstawowym sposobem tworzenia pętli w Scheme, a g++ -O2 również tę optymalizację wprowadza). W przypadku języków czysto funkcyjnych szczególnie skuteczne mogą być techniki optymalizacji rekurencji, gdyż można przyjąć kilka wygodnych, dodatkowych założeń.

Jeżeli mówimy o C++ to chociaż trzeba się zwykle postarać (tzn może nie jakoś bardzo mocno optymalizować, ale zastanowić się czego używamy -> stack z stla jest bardzo wolny(nie wiem czemu), jakby użyć zamiast tego vectora i najlepiej podać mu jaki ma być jego rozmiar, żeby nie musiał być przealokowywany, podjrzewam, że kod mógłby być szybszy) by napisać typowo rekurencyjny algorytm na własnym stosie, który by chodził szybciej. Natomiast wydajność pamięciowa prawie zawsze jest znacznie lepsza.


Na koniec przypominam, że optymalizacja algorytmu jest podstawą i wszelkiej poprawy wydajności należy szukać właśnie tam -> chociaż stałą trzeba uwzględniać w przypadku rzeczywistych programów(szczególnie dla małych danych),  najpierw warto się zawsze zastanowić nad asymptotyczną złożonością algorytmu.
P-27165
szyx_yankez
» 2011-01-26 20:44:56
Pojedynczy wynik nie jest zbyt wiarygodny. Różnica może wynikać z np. niedokładności funkcij zwracającej czas. Najlepiej wziąć średnio z kilku/nastu pomiarów!
P-27166
1 2 3 « 4 » 5 6
Poprzednia strona Strona 4 z 6 Następna strona
» Forum » Programowanie » [C, C++] Inne
© Wszelkie prawa zastrzeżone 2005-2024