Diskuze: Jak zabránit přetečení zásobníku

C# .NET .NET (C# a Visual Basic) Jak zabránit přetečení zásobníku American English version English version

Aktivity (1)
Avatar
Ondřej Krsička
Redaktor
Avatar
Ondřej Krsička:16.7.2016 15:32

Ahoj, mám tento kód.

class Uzel
{
    public Uzel Předek { get; set; }
    public List<Uzel> Potomci { get; set; }
    public Uzel()
    {
        Předek = null;
        Potomci = new List<Uzel>();
    }
    public int Hloubka(int hloubka)
    {
        if (Předek == null)
        {
            return hloubka;
        }
        else
        {
            return Předek.Hloubka(hloubka + 1);
        }
    }
    public int Hloubka()
    {
        return Hloubka(0);
    }
}

Když zjišťuju hloubky stromu odhadem v řádu tisíců, maximálně však 1 mil., vyhodí to na mě stack overflow. U menších hloubek to však funguje správně.

Napadlo mě, že by metoda byla typu void a upravovala by statickou proměnnou. Fungovalo by to takhle?

 
Odpovědět 16.7.2016 15:32
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na Ondřej Krsička
Ondřej Krsička:16.7.2016 15:37

Ta proměnná by ani nemusela být statická, stačilo by private field. No nic, jdu to nakódit.

 
Nahoru Odpovědět 16.7.2016 15:37
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Ondřej Krsička
patrik.valkovic:16.7.2016 15:48

StackOverfow ti může způsobit i samotná rekurze. Máš-li tam houbku 1 mil, nepoužívej rekurzi ale pomož si spíše zásobníkem.

Nahoru Odpovědět 16.7.2016 15:48
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na Ondřej Krsička
Martin Dráb:16.7.2016 15:58

Pokud víš, že sice budeš hodně využívat zásobník, ale přecejen nějak omezeně, můžeš jeho velikost ovlivnit v nataveních projektu/překla­dače.

Jinak každý kód provádějící rekurzi můžeš přepsat na ekvivalentní kód používající tebou deklarovaný zásobník (co jiného rekurze je než použití zásobníku, ale toho "procesorového"). Stejně jako každá proměnná alokovaná na zásobníku může být alokována dynamicky.

Nahoru Odpovědět 16.7.2016 15:58
2 + 2 = 5 for extremely large values of 2
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na patrik.valkovic
Ondřej Krsička:16.7.2016 16:02

pomož si spíše zásobníkem

Tak teď vůbec nevím, o čem mluvíš.

 
Nahoru Odpovědět 16.7.2016 16:02
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na Martin Dráb
Ondřej Krsička:16.7.2016 16:03

A nevíš, jak to nastavím?

 
Nahoru Odpovědět 16.7.2016 16:03
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na Ondřej Krsička
Martin Dráb:16.7.2016 18:29

Hm, zdá se, že pro .NET na to bude nejlepší použít utilitku EDITBIN, konkrétně s parametrem /STACK.

Viz reference k utilitce
https://msdn.microsoft.com/…25ddyfc.aspx

Nahoru Odpovědět 16.7.2016 18:29
2 + 2 = 5 for extremely large values of 2
Avatar
Marian Benčat
Redaktor
Avatar
Marian Benčat:16.7.2016 20:04

Doporučuji nevymýšlet žádné hlouposti typu simulace zásobníků, ale místo rekurze to implementovat iteračně. Není přeci problém si někde držet referenci na "aktuální node" a celé to narvat do
While(aktualni­.predek!=null) {
pocet++;
aktualni = aktualni.predek;
}

nebo něco podobného..

Editováno 16.7.2016 20:04
Akceptované řešení
+20 Zkušeností
Řešení problému
Nahoru Odpovědět 16.7.2016 20:04
"C# 3.0 (2007) volal Java 8 (2014), že chce svoje featury zpět"
Avatar
Ondřej Krsička
Redaktor
Avatar
Odpovídá na Marian Benčat
Ondřej Krsička:17.7.2016 10:19

Jasný, proč to dělat složitě, když to jde jednoduše.

 
Nahoru Odpovědět 17.7.2016 10:19
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Marian Benčat
patrik.valkovic:17.7.2016 11:17

Obvykle se stromy dělají bez ukazatele na rodiče, v takových situacích je použitá zásobníku jediná možnost.

Nahoru Odpovědět  +1 17.7.2016 11:17
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Marian Benčat
Redaktor
Avatar
Odpovídá na patrik.valkovic
Marian Benčat:17.7.2016 11:20

too máte pravdu-. často je vlastní zásobník jediná možnost. zde ne :-)

Nahoru Odpovědět 17.7.2016 11:20
"C# 3.0 (2007) volal Java 8 (2014), že chce svoje featury zpět"
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 11 zpráv z 11.