7

几个小时以来，我一直试图在网上和这个网站上找到这个问题的答案，但我并不完全在那里。

我知道 .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>();

图 [] 是：

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

我试图优化代码，以便它不会携带比从一次迭代（递归？）到下一次迭代所需的更多包袱，但是使用 100K 节点图，每个节点都有 1-9 条边它会很快就达到了 1MB 的限制。

无论如何，我是 C# 和代码优化的新手，如果有人能给我一些指示（不是这样），我将不胜感激。

4

6 回答 6

16

避免深度递归堆栈潜水的经典技术是通过迭代编写算法并使用适当的列表数据结构管理您自己的“堆栈”来简单地避免递归。考虑到输入集的庞大规模，您很可能在这里需要这种方法。

于 2009-10-05T17:07:52.333 回答
9

不久前，我在博客中探讨了这个问题。或者，更确切地说，我探讨了一个相关问题：如何在不使用递归的情况下找到二叉树的深度？递归树深度解决方案是微不足道的，但如果树高度不平衡，则会破坏堆栈。

我的建议是研究解决这个更简单问题的方法，然后决定哪些方法（如果有的话）可以适应你稍微复杂的算法。

请注意，在这些文章中，示例完全用 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

最后，如果你真的是一个喜欢惩罚的人（或编译器开发者），你可以用延续传递风格重写你的程序，从而完全不需要堆栈：

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

于 2009-10-05T17:50:52.170 回答
7

您可以将代码转换为使用“工作队列”而不是递归的。沿着以下伪代码的东西：

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

我知道这很神秘，但这是您需要做的基本概念。由于您当前的代码只能获得 3000 个节点，因此您最多可以在没有任何参数的情况下达到 12~15k。所以你需要完全终止递归。

于 2009-10-05T17:28:28.580 回答
3

您的节点是结构还是类？如果是前者，请将其设为一个类，以便将其分配在堆上而不是堆栈上。

于 2009-10-05T17:00:09.170 回答
1

我将首先验证您实际上是在溢出堆栈：您实际上看到运行时抛出了StackOverflowException 。

如果确实如此，您有几个选择：

  1. 修改您的递归函数，以便 .NET 运行时可以将其转换为尾递归函数。
  2. 修改您的递归函数，使其可迭代并使用自定义数据结构而不是托管堆栈。

选项 1 并不总是可行的，它假定 CLR 用于生成尾递归调用的规则在未来将保持稳定。主要的好处是，在可能的情况下，尾递归实际上是一种在不牺牲清晰度的情况下编写递归算法的便捷方式。

选项 2 的工作量更大，但对 CLR 的实现不敏感，可以为任何递归算法实现（尾递归可能并不总是可能的）。通常，您需要在某个循环的迭代之间捕获和传递状态信息，以及有关如何“展开”占据堆栈位置的数据结构（通常是 List<> 或 Stack<>）的信息。将递归展开到迭代中的一种方法是通过延续传递模式。

有关 C# 尾递归的更多资源：

为什么 .NET/C# 不针对尾调用递归进行优化？

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

于 2009-10-05T17:52:23.417 回答
0

我首先要确保我知道为什么会出现堆栈溢出。真的是因为递归吗？递归方法并没有在堆栈上放太多东西。也许是因为节点的存储？

另外，顺便说一句，我看不到end参数会发生变化。这表明它不需要是每个堆栈帧上携带的参数。

于 2009-10-05T17:35:25.663 回答