jsc |
» 2011-01-26 17:04:21 DejaVu możesz się powołać na źródła, bo wg. mojej zdroworozsądkowej analizy dla prostych algorytmów matematycznych (to znaczy obliczania n-tego wyrazu nierozbudowanego ciągu) pętla for ma mniejsze zużycie zasobów pamięcio-czasowych niż rekurencja? |
|
DejaVu |
» 2011-01-26 17:10:01 Napisz sortowanie tym samym algorytmem rekurencyjnie i nierekurencyjnie, a potem zmierz czasy. Zdrowy rozsądek rozłoży Ciebie na łopatki. |
|
jsc |
» 2011-01-26 17:32:29 Wg. tytułowe algorytmy rekurencyjne, to takie algorytmy, których zastosowanie odpowiedników pogarsza jakość programu. W tym QuickSort, na który się powołujesz.
Ja tylko dyskutuję z manierą stosowania rekurencji do silni, ciągów Fibbonachiego i innych ciągów, do których zrobienie pętli jest "skomplikowane". |
|
markon Temat założony przez niniejszego użytkownika |
» 2011-01-26 18:31:28 ale chodzi mi o taki konkretny opis, na czym polega dokładnie ta rekurencja,
bo jak zachowa się takie wywołanie return fib( n - 1 ) + fib( n - 2 );
tutaj będą aż dwa wywołania naraz, jak to będzie wyglądało od wewnątrz?
|
|
DejaVu |
» 2011-01-26 18:38:02 Cóż... myślę, że zamiast wykrzykiwać takie bzdury i uważać stanowczo, że rekurencja jest zła to pofatygowałbyś się zaimplementować oba quicksorty i przetestował ich wydajność.
Debug
Iteracyjny quicksort: 0.211045
Rekurencyjny quicksort: 0.017094
Release
Iteracyjny quicksort: 0.013266
Rekurencyjny quicksort: 0.007031
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <tools/Time.hpp>
void prepare( long * pArray, long iCount )
{
for( long i = 0; i < iCount; i++ )
pArray[ i ] = i %( iCount / 10 );
}
void show( long * pArray, long iCount )
{
return;
for( long i = 0; i < iCount; i++ )
printf( "%d, ", pArray[ i ] );
printf( "\n\n" );
}
long getPartition( long * pArray, long iBegin, long iEnd )
{
long iMidVal = pArray[ iBegin +( iEnd - iBegin ) / 2 ];
long i = iBegin;
long j = iEnd;
for(;; )
{
while( pArray[ i ] < iMidVal )
i++;
while( pArray[ j ] > iMidVal )
j--;
if( i < j )
std::swap( pArray[ i++ ], pArray[ j-- ] );
else
return j;
}
}
void qsort1( long * pArray, long iBegin, long iEnd )
{
if( iBegin >= iEnd )
return;
long iPartition = getPartition( pArray, iBegin, iEnd );
qsort1( pArray, iBegin, iPartition );
qsort1( pArray, iPartition + 1, iEnd );
}
void qsort2( long * pArray, long iBegin, long iEnd )
{
if( iBegin >= iEnd )
return;
typedef std::pair < long, long > TPair;
std::stack < TPair > stack;
stack.push( std::make_pair( iBegin, iEnd ) );
while( !stack.empty() )
{
TPair pair = stack.top();
stack.pop();
if( pair.first >= pair.second )
continue;
long iPartition = getPartition( pArray, pair.first, pair.second );
stack.push( std::make_pair( pair.first, iPartition ) );
stack.push( std::make_pair( iPartition + 1, pair.second ) );
}
}
int main()
{
tools::CTime time;
std::vector < long > vLista;
vLista.resize( 100000 );
prepare( & vLista[ 0 ], vLista.size() );
show( & vLista[ 0 ], vLista.size() );
time.Set( 0 );
qsort2( & vLista[ 0 ], 0, vLista.size() - 1 );
time.Update();
printf( "Iteracyjny quicksort: %lf\n",( double ) time.Get() );
show( & vLista[ 0 ], vLista.size() );
prepare( & vLista[ 0 ], vLista.size() );
show( & vLista[ 0 ], vLista.size() );
time.Set( 0 );
qsort1( & vLista[ 0 ], 0, vLista.size() - 1 );
time.Update();
printf( "Rekurencyjny quicksort: %lf\n",( double ) time.Get() );
show( & vLista[ 0 ], vLista.size() );
return 0;
} |
|
jsc |
» 2011-01-26 18:45:28 | Cóż... myślę, że zamiast wykrzykiwać takie bzdury i uważać stanowczo, że rekurencja jest zła to pofatygowałbyś się zaimplementować oba quicksorty i przetestował ich wydajność. |
Chyba mnie źle zrozumiałeś, ja tylko napisałem, że rekurencja w dydaktyce nie zawsze używana do tego czego powinna. Czyli rekurencyjny QuickSort jest dobry, a rekurencyjna silnia i rekurencyjny ciąg do Fibonachiego są złe. Jeśli pomyślałeś, że te wszystkie algorytmy wrzucam do jednego worka to jesteś w błędzie. |
|
ison |
» 2011-01-26 18:46:19 @markon żeby zrozumieć rekurencję musisz zrozumieć rekurencję |
|
DejaVu |
» 2011-01-26 18:49:41 Rekurencyjna silnia również jest dobra jak i rekurencyjny Fibonaci. Tworzysz po prostu teorię do której nie znajdziesz właściwych argumentów potwierdzających Twoje słowa. |
|
| 1 « 2 » 3 4 5 6 |