Как избежать изменения размера стека и избежать переполнения стека в C #

Question

Я уже несколько часов пытаюсь найти ответ на этот вопрос в Интернете и на этом сайте, и я не совсем там.

Я понимаю, что .NET выделяет приложениям 1 МБ, и что лучше избегать переполнения стека путем перекодирования, а не форсировать размер стека.

Я работаю над приложением "кратчайший путь", которое прекрасно работает примерно до 3000 узлов, после чего оно переполняется. Вот метод, который вызывает проблемы:

    public void findShortestPath(int current, int end, int currentCost)
    {
        if (!weight.ContainsKey(current))
        {
            weight.Add(current, currentCost);
        }
        Node currentNode = graph[current];
        var sortedEdges = (from entry in currentNode.edges orderby entry.Value ascending select entry);
        foreach (KeyValuePair<int, int> nextNode in sortedEdges)
        {
            if (!visited.ContainsKey(nextNode.Key) || !visited[nextNode.Key])
            {
                int nextNodeCost = currentCost + nextNode.Value;
                if (!weight.ContainsKey(nextNode.Key))
                {
                    weight.Add(nextNode.Key, nextNodeCost);
                }
                else if (weight[nextNode.Key] > nextNodeCost)
                {
                    weight[nextNode.Key] = nextNodeCost;
                }
            }
        }
        visited.Add(current, true);
        foreach (KeyValuePair<int, int> nextNode in sortedEdges)
        {
            if(!visited.ContainsKey(nextNode.Key) || !visited[nextNode.Key]){
                findShortestPath(nextNode.Key, end, weight[nextNode.Key]);
            }
        }
    }//findShortestPath

Для справки, класс Node имеет одного члена:

 public Dictionary<int, int> edges = new Dictionary<int, int>();

График []:

  private Dictionary<int, Node> graph = new Dictonary<int, Node>();

Я попытался оптимизировать код, чтобы он не переносил больше багажа, чем нужно, от одной итерации (рекурсии?) К следующей, но с графом 100K-узла, где каждый узел имеет от 1 до 9 ребер он достигнет лимита в 1 МБ довольно быстро.

Во всяком случае, я новичок в C # и оптимизации кода, если кто-нибудь может дать мне несколько указателей ( не так ), я был бы признателен.

Answer 1

Классическая техника, позволяющая избежать глубоких рекурсивных погружений в стеке, - это просто избежать рекурсии, написав алгоритм итеративно и управляя своим собственным «стеком» с соответствующей структурой данных списка. Скорее всего, вам понадобится такой подход, учитывая размер вашего входного набора.

Answer 2

Некоторое время назад я исследовал эту проблему в своем блоге. Или, скорее, я исследовал смежную проблему: как найти глубину двоичного дерева без использования рекурсии? Рекурсивное решение по глубине дерева тривиально, но уносит стек, если дерево сильно разбалансировано.

Моя рекомендация состоит в том, чтобы изучить пути решения этой более простой проблемы, а затем решить, какой из них, если таковой имеется, можно адаптировать к вашему чуть более сложному алгоритму.

Обратите внимание, что в этих статьях примеры приведены полностью на JScript. Тем не менее, это не должно быть сложно адаптировать их к C #.

Здесь мы начнем с определения проблемы.

http://blogs.msdn.com/ericlippert/archive/2005/07/27/recursion-part-one-recursive-data-structures-and-functions.aspx

Первая попытка решения - это классический метод, который вы, вероятно, примете: определите явный стек; используйте его, а не полагайтесь на операционную систему и компилятор, реализующий для вас стек. Именно это и делает большинство людей, сталкиваясь с этой проблемой.

http://blogs.msdn.com/ericlippert/archive/2005/08/01/recursion-part-two-unrolling-a-recursive-function-with-an-explicit-stack.aspx

Проблема с этим решением в том, что это немного беспорядок. Мы можем пойти еще дальше, чем просто сделать свой собственный стек. Мы можем создать собственную маленькую доменную виртуальную машину с собственным стеком, выделенным в куче, а затем решить проблему, написав программу, предназначенную для этой машины! Это на самом деле проще, чем кажется; операции машины могут быть чрезвычайно высокого уровня.

http://blogs.msdn.com/ericlippert/archive/2005/08/04/recursion-part-three-building-a-dispatch-engine.aspx

И, наконец, если вы действительно жаждете наказания (или разработчик компилятора), вы можете переписать вашу программу в Continuation Passing Style, тем самым полностью исключив необходимость в стеке:

http://blogs.msdn.com/ericlippert/archive/2005/08/08/recursion-part-four-continuation-passing-style.aspx

http://blogs.msdn.com/ericlippert/archive/2005/08/11/recursion-part-five-more-on-cps.aspx

http://blogs.msdn.com/ericlippert/archive/2005/08/15/recursion-part-six-making-cps-work.aspx

CPS - это особенно умный способ перемещения неявной структуры данных стека из системного стека в кучу путем кодирования ее в отношениях между группой делегатов.

Вот все мои статьи по рекурсии:

http://blogs.msdn.com/ericlippert/archive/tags/Recursion/default.aspx

Answer 3

Вы можете преобразовать код для использования «рабочей очереди», а не быть рекурсивным. Что-то вроде следующего псевдокода:

Queue<Task> work;
while( work.Count != 0 )
{
     Task t = work.Dequeue();
     ... whatever
     foreach(Task more in t.MoreTasks)
         work.Enqueue(more);
}

Я знаю, что это загадочно, но это основная концепция того, что вам нужно сделать. Поскольку вы получаете только 3000 узлов с вашим текущим кодом, в лучшем случае вы получите 12 ~ 15k без каких-либо параметров. Так что вам нужно полностью убить рекурсию.

Answer 4

Ваш Node - это структура или класс? Если это первое, сделайте его классом, чтобы он размещался в куче, а не в стеке.

Answer 5

Я бы сначала проверил, что вы на самом деле переполняете стек: вы на самом деле видите StackOverflowException , генерируемое во время выполнения.

Если это действительно так, у вас есть несколько вариантов:

1. Измените вашу рекурсивную функцию, чтобы среда выполнения .NET могла преобразовать ее в хвостовую рекурсивную функцию .
2. Измените вашу рекурсивную функцию, чтобы она была итеративной и использовала пользовательскую структуру данных, а не управляемый стек.

Вариант 1 не всегда возможен и предполагает, что правила, используемые CLR для генерации хвостовых рекурсивных вызовов, останутся стабильными в будущем. Основное преимущество заключается в том, что, когда это возможно, хвостовая рекурсия на самом деле является удобным способом написания рекурсивных алгоритмов без ущерба для ясности.

Вариант 2 является более трудоемким, но он не чувствителен к реализации CLR и может быть реализован для любого рекурсивного алгоритма (где хвостовая рекурсия не всегда возможна). Как правило, вам нужно захватывать и передавать информацию о состоянии между итерациями некоторого цикла, а также информацию о том, как «развернуть» структуру данных, занимающую места в стеке (обычно это List <> или Stack <>). Один из способов развернуть рекурсию в итерацию - это продолжение, передающее шаблон.

Дополнительные ресурсы по хвостовой рекурсии C #:

Почему .NET / C # не оптимизируется для рекурсии хвостового вызова?

http://geekswithblogs.net/jwhitehorn/archive/2007/06/06/113060.aspx

Answer 6

Сначала я должен убедиться, что знаю, почему у меня переполнение стека. Это на самом деле из-за рекурсии? Рекурсивный метод не помещает много в стек. Может быть, это из-за хранения узлов?

Кроме того, кстати, я не вижу, чтобы параметр end менялся. Это говорит о том, что это не обязательно должен быть параметр, передаваемый в каждом кадре стека.