Algorytm rekurencyjny i stos oraz szybkość wykonywania.

Ostatnio zmodyfikowano 2013-07-18 20:56

johny

Temat założony przez niniejszego użytkownika

» 2013-07-17 22:18:26

Używając stosu na std::deque algorytm iteracyjny liczył około 0.43 sek, a używając stosu na tablicy około 0.32 sek. Rekurencyjnie nie sprawdzałem, ale raczej szybciej, musiałbym się na ubuntu przelogować, a nie chce mi się;D

@pekfos
To już tak rekreacyjnie chciałem coś sprawdzić, z czystej ciekawości, ile w każdym kolejnym kroku mi odkłada na stos wywoływana rekurencyjnie funkcja. Potrafię oszacować, że przy każdym wywołaniu przekazuję do funkcji 2x

short

uchar

oraz tworzę zmienną

int

, czyli gdzieś 9 bajtów. Do tego dochodzi jakiś adres powrotu? Po prostu myślałem, że da się to jakoś łatwo sprawdzić.

P-88138

m4tx

» 2013-07-17 22:58:04

kol.reserve( 100 );

Prędzej coś takiego:

kol.resize( 100 );

Ale jak ten stos ma mieć rozmiar wyrażany w milionach to wstaw tam trochę większą liczbę niż 100 ;>

P-88144

johny

Temat założony przez niniejszego użytkownika

» 2013-07-17 23:58:38

Tak wiem, że większą, 100 to tylko przykład;p
Już sprawdzałem metodę

resize( 100 )

i ona rozszerza kolejkę, do 100 elementów. Tylko problem w tym, że od chwili rozszerzenia, metody

pop_back()

push_back()

działają na setnym elemencie. Czyli jak chcę zapełniać kolejkę od pierwszego miejsca to pozostaje mi tylko

at()

i jakiś licznik do wskazywania na aktualny wierzchołek stosu (w tej kolejce). Skoro nie mogę używać push i pop to to wszystko traci ręce i nogi, chyba, że czegoś tu nie rozumiem:D

P-88152

DejaVu

» 2013-07-18 00:02:06

std::vector < int > bla;
bla.reserve( 10000000 );
bla.push_back( 123 );
bla.pop_back();

P-88153

pekfos

» 2013-07-18 12:11:57

czyli gdzieś 9 bajtów

Więcej.

P-88165

johny

Temat założony przez niniejszego użytkownika

» 2013-07-18 20:04:41

No masz rację, więcej. Zrobiłem mały eksperyment, jako że bardzo chcę to dokładnie zrozumieć. Kod:

#include <iostream>
#include <stdio.h>

using namespace std;

static char * poczatek; //wskaznik pokazujacy na miejsce w pamieci, gdzie zaczyna sie budowac nasz stos
static int max_rozmiar_stosu; //jako ograniczenie dla nieskonczonej referencji

int pobierzAktualnyRozmiarStosu() {
char lokalna; //zmienna lokalna o adresie &lokalna
int zwracamy =( & lokalna - poczatek ) * sizeof( lokalna ); //roznica adresow zmiennej z linijki powyzej i poczatku stosu
if( zwracamy < 0 ) //pamiec w moim przypadku zajmowana jest w dol (od wiekszych adresow w kierunku mniejszych), dlatego odwrotnosc
   return - zwracamy;
else
   return zwracamy;

}

void rekurencja() {
int a, b, c, d, e, f, g, h; // 1 tworzymy pomocniczne zmienne lokalne zapychajace stos
int z = a + b + c; //+d+e+f+g;//+h;   // 2 dodajemy, do siebie, zeby kompilator nie optymalizowal

int AktualnyRozmiar = pobierzAktualnyRozmiarStosu(); //funkcja zwraca nam o ile stos sie rozrosl od momentu powstania
cout << "Aktualny Rozmiar Stosu: " << AktualnyRozmiar << endl;
if( AktualnyRozmiar < max_rozmiar_stosu ) {
rekurencja();
} else {
cout << "\nStack Overflow! xD" << endl;
}
cout << z - z; // 3 wyrzucamy na ekran, zeby kompilator nie optymalizowal (roznica po to zeby ladnie wygladalo ;D)
}

int main() {
max_rozmiar_stosu = 512; //bajtow

//tutaj pare ekseprymentow

char c_a; //zmienna typu char (a)
int i_b, i_c; //zmienne typu int (b,c)
char c_d, c_e; //zmienne typu char (d,e)
short s_f; //zmienna typu short (f)
cout << static_cast < void *>( & c_a ) << " " << sizeof( c_a ) << "bajtow" << endl;
cout << static_cast < void *>( & i_b ) << " " << sizeof( i_b ) << "bajtow" << endl;
cout << static_cast < void *>( & i_c ) << " " << sizeof( i_c ) << "bajtow" << endl;
cout << static_cast < void *>( & c_d ) << " " << sizeof( c_d ) << "bajtow" << endl;
cout << static_cast < void *>( & c_e ) << " " << sizeof( c_e ) << "bajtow" << endl;
cout << static_cast < void *>( & s_f ) << " " << sizeof( s_f ) << "bajtow" << endl;

cout << "\nOdleglosc pomiedzy dwoma int: " <<( & i_b -& i_c ) * sizeof( i_b );
cout << "\nOdleglosc pomiedzy dwoma char: " <<( & c_d -& c_e ) * sizeof( c_d );

//koniec eksperymentow

char pomocnicza_zmienna; //na ta zmienna wskazuje *poczatek!
poczatek =& pomocnicza_zmienna;
cout << "\n\nAdres poczatku to: " << static_cast < void *>( poczatek ) << endl << endl;

rekurencja();

cout << "\n\n";
return 0;
}

Na ekranie wydrukowane zostanie:

0x22feaf 1bajtow
0x22fea8 4bajtow
0x22fea4 4bajtow
0x22fea3 1bajtow
0x22fea2 1bajtow
0x22fea0 2bajtow

Odleglosc pomiedzy dwoma int: 4
Odleglosc pomiedzy dwoma char: 1

Adres poczatku to: 0x22fe9f

Aktualny Rozmiar Stosu: 108
Aktualny Rozmiar Stosu: 172
Aktualny Rozmiar Stosu: 236
Aktualny Rozmiar Stosu: 300
Aktualny Rozmiar Stosu: 364
Aktualny Rozmiar Stosu: 428
Aktualny Rozmiar Stosu: 492
Aktualny Rozmiar Stosu: 556

Stack Overflow! xD
00000000

Zgodnie z powyższym obrazkiem, stos jest budowany tuż za pamięcią main.
Dlatego pobieram sobie adres ostatniej zmiennej w main i ustawiam ją jako początek stosu. Tak pi razy drzwi.
Następnie wywołuję funkcję rekurencyjną, która za każdym razem tworzy 5 zmiennych lokalnych typu int (a,b,c,z oraz AktualnyRozmiar). Reszta (d,e,f,g,h) jest automatycznie optymalizowana przez kompilator.

Wnioski:
W aktualnej konfiguracji stos przyrasta z każdą iteracją o 64B.
Program wrzuca na stos po 32+n*16 bajtów danych. Czyli w tej chwili trzeba dodać 3x int, żeby zamiast 64B wrzucał po 80B. A następnie trzeba dodać 4x int, żeby zamiast 80B wrzucał 96B, itd.
Czyli jakbym nie tworzył żadnych zmiennych lokalnych w tej funkcji referencyjnej to by dorzucał po 32B.

Moje pytanie: czym są te 32B? adres powrotu funkcji tyle zajmuje?

P-88223

pekfos

» 2013-07-18 20:47:19

z - z

może być zoptymalizowane do zera, a używanie niezainicjalizowanych zmiennych to UB, więc tym bardziej kompilator ma prawo zrobić to inaczej ;)

P-88229

johny

Temat założony przez niniejszego użytkownika

» 2013-07-18 20:56:18

Chodziło mi o najszybszy sposób, żeby mój kompilator nie wyrzucał ostrzeżeń. I nie wyrzuca. Ale, żeby nie było dodałem inicjalizację zmiennych

a = b = c = d = e = f = g = h = 1;

oraz wypisywanie przed wyjściem z rekurencji zmieniłem na

cout << z;

. Wynik jest taki sam, tylko że teraz zamiast kilku zer jest kilka trójek w ostatniej linijce.

Nie przekazuję do funkcji żadnych parametrów, więc tylko adres powrotu jest odkładany na stosie? (poza zmiennymi lokalnymi?)

P.S. Właśnie do tego kilka postów wcześniej potrzebowałem czegoś co odczytuje adres wierzchołka stosu. Ale widać, da się to zasymulować jak wyżej (o ile to jest dobrze:D).

P-88232

1 « 2 »

Poprzednia strona

Strona 2 z 2

» Forum » Programowanie » [C, C++] Inne