0

我有简单的递归程序来查找连接的子图。该代码通过从图中每个未访问的顶点遍历所有边（递归地）并在过程中用“ingraph=False”标记已访问的边来工作。（图总是无向无权图）。

我遇到的问题是，对于大型图（具有约 100,000 个顶点的子图）python(-2.7) 返回分段错误。但这在 python-2.6 中工作得很好（现在仍然如此）。

有人可以向我解释一下两者之间发生了什么变化（或者可能完全是别的东西）？有没有办法用 python-2.7 修复它（在某些时候迁移到 python-3 时最好也不会中断）？或者我应该以非递归方式重写它？

谢谢！

这是源更新：有关非递归解决方案，请参阅下面的更新 3

def floodfill(g):
  for v in g.vertices: v.ingraph = True
  sys.setrecursionlimit(g.size)
  subgraph = 1
  for v in g.vertices:
    if v.ingraph:
      v.ingraph = False
      v.subgraph = subgraph
      g.floodfill_search(v,subgraph)
      subgraph += 1

def floodfill_search(g,v,subgraph):
  for n in v.neighbors:
    if n.ingraph:
      n.ingraph = False
      n.subgraph = subgraph
      g.floodfill_search(n,subgraph)

- - - 更新 - - - -

我做了一个小的递归测试，它为 3 台不同的计算机提供了 ~16,000、~24,000 和 ~28,000 的递归限制。此外，对于一台电脑来说，结果甚至不是恒定的。运行两次测试给出的限制略有不同。例如，对于第二个，我发现结果介于 23800 和 23819 之间。

#!/usr/bin/python
import sys
def callme(i):
  print(i)
  i+=1
  callme(i)

sys.setrecursionlimit(int(1e6))
callme(0)

我真的不知道指的是哪个“C 堆栈”，据我所知，在 C 中没有实现默认的“堆栈”。在 C++ 中有堆栈，但它没有相同的限制。以下 C++ 示例运行良好（至少最多 1M 次推送）。

#include <iostream>   
#include <stack>
using namespace std;

int main () {
  stack<int> s;
  for(int i=0;i<1000000;i++) {
    cout << "push " << i << endl;
    s.push(i);
  }
}

下面的 C 代码也更深入（大约 10 倍，~262,000）

#include "stdio.h"
void callme(i) { 
  printf("calling %d\n",i);
  callme(++i);
}

int main() {
  int i=0;
  callme(i);
}

---- 更新 2 -----

好的，这显然是 python 的意图。迫使程序员避免深度递归。 http://neopythonic.blogspot.ch/2009/04/tail-recursion-elimination.html

无论如何，我现在认为最好迭代地重写它。但是我可能会在 C++ 中重新开始，使用一些图论库，比如 boost 库。如果我无论如何都要重写它，我还不如正确地完成它。

尽管如此，我仍然希望有任何评论来理解为什么会在这些特定尺寸下发生这种情况。

---- 更新 3 -----

这至少是一个快速而肮脏的python重写。脏因为它是 O(N^2) 因为最后一行。应该有一个更好的 O(N) 解决方案，通过跟踪哪些顶点没有被访问，但没有这么快看到它，这适用于我的应用程序。

def floodfill_nonrecursive(g):
    for v in g.vertices: v.ingraph = True
    start = g.vertices
    subg = 1
    while start:
      q = [start[0]]
      while q:
        v = q.pop()
        v.ingraph = False
        v.subgraph = subg
        for n in v.neighbors:
          if n.ingraph:
            n.ingraph = False
            q.append(n)
      subg += 1
      start = [v for v in g.vertices if v.ingraph]
4

2 回答 2

3

因为您的 Python 使用 C 堆栈，所以它已溢出。setrecursionlimit无法扩展 cstack 大小。它只是限制在 cstack 溢出之前引发异常。Python 的递归深度有限。2.6 的成功只是幸运的情况。

您应该将代码从递归更改为迭代样式或使用无堆栈 python（或 PyPy）。阅读http://docs.python.org/2/library/sys.html#sys.setrecursionlimit

于 2013-10-04T10:48:30.603 回答
2

您可能会在 Python 实现的某个地方使用深度递归溢出堆栈。您可以尝试使用sys.setrecursionlimit更改堆栈部门

另一种可能性是您耗尽了动态内存。递归通常更费力。

你对 Python 2.6 有更多的运气。以前的版本需要更少的内存用于您的算法。

Python 不是函数式语言，也不优化尾递归。迭代地重写算法可能是更好的方法。

于 2013-10-04T10:27:54.763 回答