wywoływanie funkcji wskaźnikiem (rekurencja?) - optymalizacja

0

Hej.
chcę stworzyć klasę, której każdy obiekt (poza ostatnim) będzie połączony z poprzednim obiektem - czyli klasa ma wskaźnik na inny obiekt tej klasy. W skrócie wygląda to tak:

class klasa {
public:
klasa(){wsk=nullptr;}
klasa* wsk;
void funkcja();
}
main(){
klasa obiekt[100];
for(int i=0; i<99; i++)
obiekt[i] = &obiekt[i+1];
}

Następnie chcę wywoływać funkcję w każdym obiekcie, który jest połączony z innym obiektem.
Mam dwie możliwości:

  1. stworzyć funkcję i wywołać ją w każdym obiekcie przy użyciu pętli for np. tak:

    for(int i=0; i<99; i++)
    obiekt[i].funkcja();
  2. skorzystać z rekurencji w ten sposób, że funkcja wyglądałaby tak:

    funkcja(){
    //...algorytm funkcji
    if(wsk)
    wsk->funkcja();
    }

Bardzo mi się podoba to drugie rozwiązanie ;-) i nawet liczyłem, że będzie ono ciut szybsze. Niestety ze wstępnych obliczeń wynika, że jest znacznie wolniejsza (o jakieś 10%).
Czy może mi ktoś wyjaśnić dlaczego to rozwiązanie jest znacznie mniej optymalne? Co na to wpływa?
Przecież pętla for musi za każdym razem sprawdzić warunek i<99 - natomiast w tym drugim przypadku mamy analogicznie sprawdzenie warunku if(wsk) - reszta jest taka sama (wywołanie funkcji na rzecz kolejnego obiektu)...

Z góry dziękuję za wyjaśnienie.
pozdrawiam.

0

Mam jeszcze jedno pytanie. Zauważyłem, że gdy ustawię sobie dość dużą wielkość tablicy obiektów np. 5000 to wywala mi komunikat stack overflow - z czym to jest związane? Przy mniejszych wielkościach tablicy nic się nie dzieje... Zabrakło mi pamięci na stosie czy popełniłem gdzieś błąd?
pozdrawiam

0

Małe sprostowanie:

  1. w kodzie powinno być oczywiście: obiekt[i].wsk = &obiekt[i+1];
  2. następnie for(int i=0; i<100; i++) obiekt[i].funkcja(); <- 100 a nie 99 (bo funkcja rekurencyjna wykona się w każdym obiekcie - łącznie z ostatnim)
  3. dla obiektów do około 12 chyba szybciej wykonuje się funkcja rekurencyjna. Przy większej liczbie obiektów lepsza okazuje się pętla for
1

Przy uzywaniu rekurencji dla kazdego wywolania musi utworzyc ramke stosu (jesli sa zmienne lokalne) do tego adres powrotu, etc. I ESP widocznie wylazi gdzies poza przydzielona pamiec dla stosu i "licznik sie przekreca" dajac w wyniku #O.
Przy petli ta sama ramka jest czyszona po kazdym wywolaniu.
user image

Co do wydajnosci: to zrob zrzut disassemblera jakiegos albo najlepiej samemu to policz droga wzajemnego wykluczania sie powtarzajacych instrukcji.

  • Rekurencja ma maly sens jak cos robisz stircte liniowo.
0

Dziękuję Ci bardzo n0name_l.
Mam jeszcze jedno być może głupie pytanie, ale jak zrobić zrzut asemblera? :/
Nie mam również bladego pojęcia jak policzyć to drogą wzajemnego wykluczania się powtarzających instrukcji :(.
Ten mój przykład zdaje się, że jest typowo liniowy, a mimo wszystko dla kilkunastu obiektów rekurencja chyba działa nieco szybciej ;-) - niestety dla większej liczby obiektów jest już gorzej :(

pozdrawiam i jeszcze raz dziękuję.

0

użyj:

static void funkcja(klasa *self)
  {
   for(;self;self=self->wsk)
     {
      //...algorytm funkcji dla tego self
     }
  }
0
_13th_Dragon napisał(a):

użyj:

static void funkcja(klasa *self)
{
for(;self;self=self->wsk)
{
//...algorytm funkcji dla tego self
}
}

@_13th_Dragon jesteś genialny!!! ;-)
Szybkość wykonywania funkcji po Twojej modyfikacji zwiększyła się około 7-9 krotnie!!!
Ten zapis z pętlą for troszkę mi się nie podoba (nie to że jest źle - po prostu nie lubię takich pustych miejsc :P) więc zrobiłem analogicznie z pętlą while w ten sposób:

static void funkcja(klasa *self)
  {
//...algorytm funkcji dla tego self
   while(self=self->up)
     {
      //...algorytm funkcji dla tego self
     }
  }

</quote>
Różnica w szybkości jest minimalna i czasami jest na "+" a czasami na "-" ;-)

0

Niestety moja radość dot. zoptymalizowania problemu nie trwała zbyt długo ;(.
Po głębszej analizie doszedłem do wniosku, że używanie zarówno klas jak i funkcji jest bardzo kosztowne...
Gdy nieco zmodyfikowałem mój kod tworząc dodatkową funkcję, której zadaniem było wykonywanie zadanego algorytmu tj. coś takiego:

static void funkcja(klasa *self)
  {
self->funkcja_z_algorytmem();
   while(self=self->up)
     {
      self->funkcja_z_algorytmem();
     }
  }

</quote>

okazało się, że czas wykonywania tej funkcji znacznie się pogorszył i wynosi podobnie jak poprzednie wersje tej funkcji...
Dodatkowo zmierzyłem czas wykonywania ciała funkcji bez używania funkcji i okazało się, że jest on znacznie szybszy nawet od tej wersji zaproponowanej przez Dragona.
No cóż, muszę to jeszcze przemyśleć :/

0

To może zacznijmy od początku: jak mierzysz, co robisz i do czego jest to potrzebne? Jakie są wartości bezwzględne?

  1. następnie for(int i=0; i<100; i++) obiekt[i].funkcja(); <- 100 a nie 99 (bo funkcja rekurencyjna wykona się w każdym obiekcie - łącznie z ostatnim)
  2. dla obiektów do około 12 chyba szybciej wykonuje się funkcja rekurencyjna. Przy większej liczbie obiektów lepsza okazuje się pętla for

Mierzenie szybkości wywołania pętli for dla tylu iteracji to jakaś pomyłka.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0