如何避免更改堆栈大小并避免在C#中获得堆栈溢出

Question

我一直想在网上和这个网站上找几个小时回答这个问题的答案,我不在那里.

我知道.NET会为应用程序分配1MB,并且最好通过重新编码而不是强制堆栈大小来避免堆栈溢出.

我正在开发一个"最短路径"的应用程序,可以运行大约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>();

graph []是:

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

我试图优化代码,以便它不会携带超过一次迭代(递归？)到下一次迭代所需的任何行李,但是使用100K节点图形,每个节点具有1-9个边缘,它将会很快就达到了1MB的限制.

无论如何,我是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.所以你需要完全杀死递归.