Stack Overflow jak uniknac na rekurencji [BCB]

0

Staowrzaylem sobie funkcje zastepujaca Canvas->FloodFill

Problem w tym, ze przy wiekszych obiektach do zamalowania wywala mi Stack overflow, no ale niby dlaczemu. Kto by mi pomogl to poprawic albo wskazac miejsce gdzie nie powinienem czegos powtarzac czy cos...



//fill Color on X,Y if is fimilar to Base Color with Fill Color
void __fastcall PC_EYE_TOOL::FillNext(Graphics::TBitmap *bmp, int X, int Y,
int Fr,int Fg, int Fb,										  int BaseR, int BaseG, int BaseB)
{
		 if ( (X < 0) || (X == bmp->Width) || (X < 0) || (Y == bmp->Height) || (Y < 0) ) return;


float dist,angle;
Byte * p;
p = (Byte*)bmp->ScanLine[Y];

int r = p[X*4+2];
int g = p[X*4+1];
int b = p[X*4+0];

if ( !( (r == Fr) && (g == Fg) && (b == Fb) ) )                          {
ReturnCOLOR_DIST_AND_ANGLE(r,g,b,BaseR,BaseG,BaseB,dist,angle);
if ( (dist < 15.0f) && (angle < 30.0f)  )
{
p[X*4+2] = Fr;
p[X*4+1] = Fg;
p[X*4+0] = Fb;
FillNext(bmp,X-1,Y,Fr,Fg,Fb,BaseR,BaseG,BaseB);
FillNext(bmp,X+1,Y,Fr,Fg,Fb,BaseR,BaseG,BaseB);
FillNext(bmp,X,Y-1,Fr,Fg,Fb,BaseR,BaseG,BaseB);
FillNext(bmp,X,Y+1,Fr,Fg,Fb,BaseR,BaseG,BaseB);



}
}
}

void __fastcall PC_EYE_TOOL::FillColor(Graphics::TBitmap *bmp, int X, int Y, int Fr,int Fg, int Fb)
{

Byte * p;
p = (Byte*)bmp->ScanLine[Y];

int r = p[X*4+2];
int g = p[X*4+1];
int b = p[X*4+0];

float dist;
float angle;

if (! ( (r == Fr) && (g == Fg) && (b == Fb) ) )      {
p[X*4+2] = Fr;
p[X*4+1] = Fg;
p[X*4+0] = Fb;
FillNext(bmp,X-1,Y,Fr,Fg,Fb,r,g,b);
FillNext(bmp,X+1,Y,Fr,Fg,Fb,r,g,b);
FillNext(bmp,X,Y-1,Fr,Fg,Fb,r,g,b);
FillNext(bmp,X,Y+1,Fr,Fg,Fb,r,g,b);



}


}
</cpp>
0

juz wiesz czemu tak sie tego Nie robi

0

no ale co ma ilosc wywolan jak wskaznik sie przesuwa i zmienia

0

ale masz wywołania rekurencyjne, każde wywołanie pakuje na stos argumenty, adres powrotu. Są zdejmowane przy wyjściu z funkcji - jako że wchodzisz bardzo wielokrotnie, stos sie bardzo szybko kończy.
Poza tym wygląda jakby to mogło biegać w nieskończoność - przyszedłeś z jednego kierunku (np X+1), zaraz potem wchodzisz tam z powrotem (X-1).

0

to jak go zwiekszyc jezeli sie da albo jak czyscic stos

0

Jak sobie wyczyścisz stos to funkcja nie będzie wiedziała gdzie wrócić i sobie program wyrąbiesz :P
Przekształć z algorytmu rekurencyjnego na iteracyjny, np używając jawenego stosu albo kolejki.

0

jednak co innego zrobie:: jak ilosc powtorzen FillNext bedzie wieksza od jakiejs zmiennej zapisze ostatnie wartosci X i Y i powtorze proces od tego punktu poprzednio kończąc wszystkie wywolane rekurencyjnie funkcje tylko najpierw to musze napisac ale to zaraz :>

0

no i jednak źle bo nie wypełni całej figury tylko idzie w dół po zakończeniu pierwszego wywołania idzie dalej ale w dół nie do góry bo ma juz wypełniony fillcolor i to go zatrzymuje. cholwecia

0

a ja bym jednak optowal za tym, abys sprobowal zrozumiec co do Ciebie powiedzieli przedmowcy :)))

//edit (po obejrzeniu kodu): ..albo przynajmniej zadbal o to, zeby algorytm nie przechodzil drugi raz po tym co juz zdazyl zakolorowac..

0

ale on wchodzi do funkcjii jak juz tam byl to z niej wychodzi, czy tego nie widac czy wy az tak slepi jestescie?

0
quetzalcoatl napisał(a)

przynajmniej zadbal o to, zeby algorytm nie przechodzil drugi raz po tym co juz zdazyl zakolorowac..
Jest zadbane tutaj:

if ( !( (r == Fr) && (g == Fg) && (b == Fb) ) ) 

i to jest zły sposób, bo jeśli kolor zalewania jest bliski (według twojego kryterium dist & angle) kolorowi zalewanemu to piksele, które przed zalaniem już mają kolor zalewania będą tworzyć barierę . Tu by trzeba wykorzystać drugą bitmapę (monochromatyczną).

komorkowy napisał(a)

czy tego nie widac czy wy az tak slepi jestescie?
tak piszesz, że ciężko się dopatrzyć.

Pozbądź się zmiennych lokalnych zapełniających stos. Wystarczą 3: this, X i Y
Dam kod bo będzie szybciej niż miałbym opisywać słowami:

//nie ma to jak poczciwe obiekty :]
struct RGBX
{
   Byte r;
   Byte g;
   Byte b;
   Byte x;
   
   bool operator!=(RGBX rgbx) const
   {
      return (*((int*)this) ^ *((int*)&rgbx)) & 0x00FFFFFF;
   }
   
   RGBX& operator=(RGBX rgbx)
   {
      *((int*)this) = *((int*)&rgbx);
      return *this;
   }
};

//wszystkie nie zmieniajace sie zmienne lokalne opakujemy w klase
//zamiast za kazdym razem wrzucac ich kopie na stos wrzucany bedzie jedynie wskaznik this
class FloodFill
{
private:
   RGBX base;
   RGBX fill;
   Graphics::TBitmap *bmp;
   
   bool CheckColor(RGBX pixel)
   {
      float dist, angle;
      ReturnCOLOR_DIST_AND_ANGLE(pixel.r, pixel.g, pixel.b, base.r, base.g, base.b, dist, angle);
      return (dist < 15.0f) && (angle < 30.0f);
   }
   
   bool __fastcall FillNext(Graphics::TBitmap *bmp, unsigned short X, unsigned short Y);
public:
   bool __fastcall FillColor(Graphics::TBitmap *bmp, int X, int Y, int Fr,int Fg, int Fb);
   //tu warto kilka parametrow przeksztalcic we wlasnosci (__property)
};

//fill Color on X,Y if is fimilar to base Color with fill Color
//zakladam, ze unsigned short wystarczy (max 32 tys.), zreszta przy wiekszych bitmapach stosu raczej nie wystarczy
bool __fastcall FloodFill::FillNext(Graphics::TBitmap *bmp, unsigned short X, unsigned short Y)
{
   RGBX pixel = ((RGBX*)bmp->ScanLine[Y])[X];

   
   if(pixel != fill//jak pisałem wcześniej to sprawdzanie jest do poprawienia
      && CheckColor(pixel))
   {
      pixel = fill;
      try
      {
         return
            (X == 0               || FillNext(X-1,Y)) &&
            (Y == 0               || FillNext(X,Y-1)) &&
            (X == bmp->Width - 1  || FillNext(X+1,Y)) &&
            (Y == bmp->Height - 1 || FillNext(X,Y+1));
      }
      catch(EStackOverflow)
      {
         return false;
      }
   }
}

bool __fastcall FloodFill::FillColor(Graphics::TBitmap *bmp, int X, int Y, int Fr,int Fg, int Fb)
{
   if(X < 0 || Y < 0 || X >= bmp->Width || Y >= bmp->Height) return false;

   this->bmp = bmp;
   this->fill.r = Fr;
   this->fill.g = Fg;
   this->fill.b = Fb;
   
   base = ((RGBX*)bmp->ScanLine[Y])[X];

   return FillNext(X-1,Y) && FillNext(X+1,Y) && FillNext(X,Y-1) && FillNext(X,Y+1);
}
0
if ( !( (r == Fr) && (g == Fg) && (b == Fb) ) )                          {
ReturnCOLOR_DIST_AND_ANGLE(r,g,b,BaseR,BaseG,BaseB,dist,angle);
if ( (dist < 15.0f) && (angle < 30.0f)  )

NIe rozumeim czemu to jest źłe mam jak kolor nie jest kolorem wypełnienia to wtedy sprawdź czy kolor jest chociaz troche podobny do koloru podstawowego i dopiero wtedy zamien.

0

problem jest taki ze za duzo zmiennych tworze i nie usuwam

np.

ReturnCOLOR_DIST_AND_ANGLE(r,g,b,BaseR,BaseG,BaseB,dist,angle);

tutaj w tej funkcji sa dwie funkcje z czego jedna wywolana 2 razy dla jednej funkcji dla obrazka 320x240 zwykle pierwiastkowanie zzera 300 KB

szkoda ze troszku wolno mi to dziala ale dziala :>>>

0

Nie rozumeim czemu to jest źłe mam jak kolor nie jest kolorem wypełnienia
To że piksel ma kolor wypełnienia nie oznacza, że był zalany. Mógł mieć przed zalaniem już taki kolor.

problem jest taki ze za duzo zmiennych tworze i nie usuwam

np.

ReturnCOLOR_DIST_AND_ANGLE(r,g,b,BaseR,BaseG,BaseB,dist,angle);
Akurat to co się znajduje wewnątrz tej funkcji nie ma wpływu na problem pojemności stosu.

Odległość kolorów możesz szybko mierzyć tym wzorem:
(R_1-R_2)<sup>2+(G_1-G_2)</sup>2+(B_1-B_2)^2
Pierwiastkowanie nie jest potrzebne, wystarczy zadać odległość w kwadracie.

ale dziala :>
nie znoszę takiego podejścia :-[

Najlepiej porzuć rekurencje i użyj programowego stosu, na który będziesz odkładać X i Y. Pozbędziesz się problemu stack overflow i przyspieszysz działanie.

0

Akurat to co się znajduje wewnątrz tej funkcji nie ma wpływu na problem pojemności stosu.

Zmienne lokalne są odkładane na stosie.

0
rnd napisał(a)

Akurat to co się znajduje wewnątrz tej funkcji nie ma wpływu na problem pojemności stosu.

Zmienne lokalne są odkładane na stosie.
Ale przy wyjściu z funkcji są ściągane, czyli bilans zerowy. Jedynie zmienne lokalne funkcji rekurencyjnej mają znaczenie.

0

Jedynie zmienne lokalne funkcji rekurencyjnej mają znaczenie.

No i właśnie o zmienne lokalne funkcji rekurencyjnej chodziło :)

0
adf88 napisał(a)
quetzalcoatl napisał(a)

przynajmniej zadbal o to, zeby algorytm nie przechodzil drugi raz po tym co juz zdazyl zakolorowac..
Jest zadbane tutaj:

if ( !( (r == Fr) && (g == Fg) && (b == Fb) ) ) 

o kurcze.. faktycznie, przepraszam. serio - nie moglem uwierzyc w tak banalny blad i przez bite 10 minut przegladalem kod szukajac takiegoż warunku, i go przegapilem.. tzn. ifa widzialem, nie zauwazylem zas, ze on obejmuje caly nastepujacy blok kodu!
dla mnie nauczka zeby czytac jeszcze uwazniej, dla Ciebie (->komorkowy) - dbaj o biale znaki.. klamry tego IF'a okazaly sie byc dla mnie nie do przesledzenia..

0

A nie możesz po prostu zwiększyć stosu w opcjach projektu? Nawet do 256 mb?
Problem rozwiązany w 30 sekund, geez.

0

zeby ja jeszcze takie cos znalazl w ogole nie zauwazylem czegos takiego i dalej znalezc nie moge

Wylaczylem Standard Stack Frames, ale to nie to..

0
bodziobudowniczy napisał(a)

A nie możesz po prostu zwiększyć stosu w opcjach projektu? Nawet do 256 mb?
Problem rozwiązany w 30 sekund, geez.

Jak pies ma sraczke, to postawiasz wieksze wiadro czy idziesz z nim do weterynarza?

0

Kto normalny idzie z psem, który ma sraczkę, do weterynarza? Można mu conajwyżej dać węgiel...
Pomijając jej bezsens, analogia zupełnie nietrafiona.
Pamięc jest po to, żeby jej używać. Co za różnica czy na stosie czy na stercie? Zwłaszcza, że ta druga opcja wprowadza dodatkowe komplikacje.
Są problemy, w których potrzebujemy informacji z rekurencji. Jeśli można to rozwiązać zwiększeniem limitu pamięci, czystym idiotyzmem jest obchodzenie tego na inne sposoby.
Kod komórkowego nie jest idealny (można trochę pamięci zaoszczędzić) ale sam algorytm jest ok.

0

No to inaczej - skad gwarancja, ze po wielu obiegach stosu nie braknie? Rekurencja tej gwarancji nie daje. Zwiekszanie pamieci tylko dlatego, ze program ja zzera (a nie musi) jest bez sensu. To nie jest optymalizacja tylko podstawa - napisanie algorytmu, zeby dzialal w normalnych warunkach. Normalnie stosu dla kazdego programu starcza.

PS. Weterynarz byl przenosnia. Sam dales odpowiedz - stosuje sie lekarstwo, zeby usunac przyczyne, a nie leczy skutki.

0
johny_bravo napisał(a)

No to inaczej - skad gwarancja, ze po wielu obiegach stosu nie braknie? Rekurencja tej gwarancji nie daje. Zwiekszanie pamieci tylko dlatego, ze program ja zzera (a nie musi) jest bez sensu.

To jest zwiększanie rezerw, nie commitu

To nie jest optymalizacja tylko podstawa - napisanie algorytmu, zeby dzialal w normalnych warunkach. Normalnie stosu dla kazdego programu starcza.

W życiu. Dla większości programów w których jest trochę więcej algorytmów trzeba go zwiększyć do conajmniej 32 MB.
Problem znika w takim .net. Ten problem to po prostu cena za niskopoziomowość C++, zwiększenie stosu to jedyne sensowne rozwiązanie.

0

Pamięc jest po to, żeby jej używać. Co za różnica czy na stosie czy na stercie?
W przypadku dynamicznie alokowanej sterty nieduża. Ty piszesz o statycznym limicie, który obowiązuje od startu do końca działania programu i niepotrzebnie zżera zasoby.

Dla większości programów w których jest trochę więcej algorytmów trzeba go zwiększyć do conajmniej 32 MB.
Zależność między ilością algorytmów, a wielkością stosu jest znikoma.

W algorytmie chodzi o to, aby wycisnął jak najwięcej z dostępnych zasobów. Samo zwiększenie stosu to zwykłe marnotrawstwo. Fuszerka !

0
adf88 napisał(a)

W przypadku dynamicznie alokowanej sterty nieduża. Ty piszesz o statycznym limicie, który obowiązuje od startu do końca działania programu i niepotrzebnie zżera zasoby.

Mam dla ciebie misję: zdobądz informacje, czym się różnią strony zarezerwowane od zacommitowanych. :)

Zależność między ilością algorytmów, a wielkością stosu jest znikoma.

Tak, oczywiście :D. Każdy algorytm można zapisać rekurencyjnie, niewielką część iteracyjnie.
Algorytmy w książkach (najprostszy przykład: BFS) są zapisywane z kolejką/itd z powodów historycznych, kiedyś stos był bardzo mały (czy nawet stanowił całkowicie oddzielną pamięć) i trzeba było tę rekurencję EMULOWAĆ. Zwiększa to jednak stałe współczynniki, a dzisiaj, poza kilkoma wyjątkami, jest bezsensowne.

W algorytmie chodzi o to, aby wycisnął jak najwięcej z dostępnych zasobów. Samo zwiększenie stosu to zwykłe marnotrawstwo. Fuszerka !

J/w + przydałyby ci się podstawy z teorii informacji. Algorytm rekurencyjny potrzebuje tych informacji, więc emulacja rekurencji ZWIĘKSZA ZUŻYCIE zasobów przez dodatkowe informacje potrzebne do uzyskania struktury.
W dodatku informacje w rekurencji mają ściśle określony termin (zasięg) ważności - ramka danej funkcji. Są ułożone na stosie hierarchicznie wraz z drzewem wywołań. NIE MA fragmentacji. Na stercie tracisz te informację i wprowadzasz dodatkowy koszt podczas alokacji/dealokacji.
Dodatkowo może zaistnieć sytuacja, w której wolna pamięc (sumarycznie) to A, ale największy ciągły obszar to 0.01A. Ty potrzebujesz buforu o rozmiarze 0.2A.

Dochodzi jeszcze problem cache procesora - obecna strona stosu na 100% będzie w cache, zapewne wraz z sąsiednimi; sterta jest sfragmentowana, więc prawdopodobieństwo, że potrzebna w danej chwili informacja będzie w cache jest o wiele mniejsze.

0

Mam dla ciebie misję: zdobądz informacje, czym się różnią strony zarezerwowane od zacommitowanych. :)
Przecież stos jest od kopa rezerwowany. Nie jest ?

bodziobudowniczy napisał(a)
adf88 napisał(a)

Zależność między ilością algorytmów, a wielkością stosu jest znikoma.

Tak, oczywiście :D ...
Ale o czym ty prawisz ?
Jaką różnicę robi czy program zawiera 1000 algortmów czy 10 ? Ten drugi może wymagać o wiele większego stosu niż ten pierwszy.
Jeśli algorytmów jest sporo (spory projekt) to i zagnieżdżane mogą być głębiej - i stąd ta znikoma zależność.

emulacja rekurencji ...
Wiadomo, że sterta jest mniej wydajna, jednak jeśli nie chcielibyśmy sztywnych ograniczeń to tylko emulacja rekurencji.

Poza tym nie o to się rozchodzi. Rozchodzi się o ulepszenie algorytmu. Leczyć a nie zapobiegać.
Przedstawione przeze mnie rozwiązanie zjada stos 3 razy wolniej.

Ale pewnie, po co się martwić. Piszmy byle jak, niech userzy wydają tysiaki na sprzęt...

0

Niektórym przydałaby się chyba wiedza o różnicach pomiędzy rezerwacją fragmentu przestrzeni adresowej a jej fizyczną alokacją.

0

to jak zwiększyć stos

0

Dorzuć drewna.

<font size="1">A poważnie to tak ciężko wpisać w Google'a "borland C++ stack size"? Tak ciężko przejrzeć w helpie opcje linkera?</span>

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