Każdy programista, czy to C#, C++ czy Java, musiał się kiedyś spotkać z przepełnieniem stosu, który, w przypadku platformy .NET, objawia się wyjątkiem StackOverflowException. Najłatwiej do takiego błędu doprowadzić pisząc nieskończoną rekursję. W tym poście zajmę się jednak tym jak poradzić sobie z przepełnieniem stosu, kiedy napisana metoda rekurencyjna wcale nie jest nieskończona. Zacznijmy od przykładu. Załóżmy, że mamy klasę Node i przy jej pomocy tworzymy drzewo binarne, w którym dla uproszczenia będziemy przechowywać liczby. Drzewa, które rozpatrujemy w tym przypadku nie są drzewami przeszukiwań i mogą być niezrównoważone.
Napisaliśmy również metodę rekurencyjną przeszukującą zadane drzewo w poszukiwaniu węzła przechowującego określoną wartość.
Metoda ta będzie działać, ale do czasu. Utwórzmy zdegenerowane drzewo czyli takie, które w rzeczywistości jest listą. Do wygenerowania takiego drzewa użyjemy następującego kodu:
W przypadku wystarczająco dużej liczby węzłów w zdegenerowanym drzewie (patrz parametr noOfNodes) wywołanie FindRec zakończy się wyjątkiem StackOverflowException. Wbrew pozorom, nie musi to być jakaś ogromna wartość. Na komputerze, na którym testowałem ten kod, wystarczyło aby drzewo zawierało 10 tyś węzłów. Trochę mało, czyż nie?
W takiej sytuacji musimy zrezygnować z rekursji na rzecz poczciwej pętli. Ja bym napisał taki kod:
Korzystam w nim z pomocniczej kolekcji, do której wrzucam kolejne węzły do sprawdzenia. Pętla kręci się dopóki nie zostanie znaleziony szukany węzeł albo dopóki wszystkie węzły nie zostaną sprawdzone. Podobne podejście możemy zastosować dla innych dla innych zagadnień tego typu.
Problem z StackOverflowException można również rozwiązać w sposób nie algorytmiczny, poprzez zwiększenie domyślnego rozmiaru stosu (1MB) przy pomocy narzędzia editbin albo tworząc nowy wątek o odpowiedniej wielkości stosu. Ja był jednak tego nie robił. Jeśli można osiągnąć jakiś efekt pisząc kod w odpowiedni sposób, to należy tak zrobić. W swojej karierze nie spotkałem jeszcze przypadku kiedy musiałbym zwiększyć wielkość stosu.
Na koniec załączam jeszcze kod metody Main. Cały program pozwala pobawić się pokazanymi powyżej metodami do wyszukiwania (iteracyjną i rekurencyjną) dla zdegenerowanego drzewa o zadanej liczbie węzłów. Program umożliwia również ustalenie wielkości stosu (w celach edukacyjnych :)). Kod może i jest trochę pokraczny, ale dla celów edukacyjnych się nada. Uwaga! Podanie zbyt dużej wartości jako Stack size in kilobytes (0 for default): albo Number of nodes in tree: może zakończyć się OutOfMemoryException.
public class Node
{
public uint Data { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}
Napisaliśmy również metodę rekurencyjną przeszukującą zadane drzewo w poszukiwaniu węzła przechowującego określoną wartość.
public static Node FindRec(Node root, uint i)
{
if (root == null)
return null;
if (root.Data == i)
return root;
var res = FindRec(root.Right, i);
if (res != null)
return res;
return FindRec(root.Left, i);
}
Metoda ta będzie działać, ale do czasu. Utwórzmy zdegenerowane drzewo czyli takie, które w rzeczywistości jest listą. Do wygenerowania takiego drzewa użyjemy następującego kodu:
public static Node CreateDegeneratedTree(uint noOfNodes)
{
Node root = new Node() { Data = 0 };
Node temp = root;
for (uint i = 0; i <= noOfNodes; ++i)
{
temp.Right = new Node() { Data = i };
temp = temp.Right;
}
return root;
}
W przypadku wystarczająco dużej liczby węzłów w zdegenerowanym drzewie (patrz parametr noOfNodes) wywołanie FindRec zakończy się wyjątkiem StackOverflowException. Wbrew pozorom, nie musi to być jakaś ogromna wartość. Na komputerze, na którym testowałem ten kod, wystarczyło aby drzewo zawierało 10 tyś węzłów. Trochę mało, czyż nie?
W takiej sytuacji musimy zrezygnować z rekursji na rzecz poczciwej pętli. Ja bym napisał taki kod:
public static Node Find(Node root, uint i)
{
Queue<Node> toCheck = new Queue<Node>();
toCheck.Enqueue(root);
while (toCheck.Count > 0)
{
var node = toCheck.Dequeue();
if (node != null)
{
if (node.Data == i)
return node;
toCheck.Enqueue(node.Right);
toCheck.Enqueue(node.Left);
}
}
return null;
}
Korzystam w nim z pomocniczej kolekcji, do której wrzucam kolejne węzły do sprawdzenia. Pętla kręci się dopóki nie zostanie znaleziony szukany węzeł albo dopóki wszystkie węzły nie zostaną sprawdzone. Podobne podejście możemy zastosować dla innych dla innych zagadnień tego typu.
Problem z StackOverflowException można również rozwiązać w sposób nie algorytmiczny, poprzez zwiększenie domyślnego rozmiaru stosu (1MB) przy pomocy narzędzia editbin albo tworząc nowy wątek o odpowiedniej wielkości stosu. Ja był jednak tego nie robił. Jeśli można osiągnąć jakiś efekt pisząc kod w odpowiedni sposób, to należy tak zrobić. W swojej karierze nie spotkałem jeszcze przypadku kiedy musiałbym zwiększyć wielkość stosu.
Na koniec załączam jeszcze kod metody Main. Cały program pozwala pobawić się pokazanymi powyżej metodami do wyszukiwania (iteracyjną i rekurencyjną) dla zdegenerowanego drzewa o zadanej liczbie węzłów. Program umożliwia również ustalenie wielkości stosu (w celach edukacyjnych :)). Kod może i jest trochę pokraczny, ale dla celów edukacyjnych się nada. Uwaga! Podanie zbyt dużej wartości jako Stack size in kilobytes (0 for default): albo Number of nodes in tree: może zakończyć się OutOfMemoryException.
static void Main(string[] args)
{
Console.Write("Do you want to use recursion (Y for yes)?: ");
string line = Console.ReadLine();
bool useRecursion = String.Equals(line, "Y", StringComparison.OrdinalIgnoreCase);
if(useRecursion)
Console.WriteLine("Recursion search will be used");
Console.Write("Stack size in kilobytes (0 for default): ");
line = Console.ReadLine();
uint stackSize;
if (!UInt32.TryParse(line, out stackSize))
stackSize = 1024
Console.WriteLine("Stack size is {0} kilobytes ", stackSize);
var th = new Thread(
new ThreadStart(() =>
{
Console.Write("Number of nodes in tree: ");
while ((line = Console.ReadLine()) != String.Empty)
{
uint noOfNodes;
if (UInt32.TryParse(line, out noOfNodes))
{
Node root = CreateDegeneratedTree(noOfNodes);
Stopwatch sw = new Stopwatch();
if (useRecursion)
{
sw.Start();
var res = FindRec(root, noOfNodes);
sw.Stop();
}
else
{
sw.Start();
var res = Find(root, noOfNodes);
sw.Stop();
}
root = null;
Console.Write("Processing time (ms): {0}\n\n", sw.ElapsedMilliseconds);
}
Console.Write("Number of nodes in tree: ");
}
}), (int)stackSize * 1024);
th.Start();
}
orcid.org/0000-0002-6838-2135