从python 2.6到2.7进行深度递归的细分错误 [英] segmentation fault for deep recursion upon going from python 2.6 to 2.7

问题描述

我有一个简单的递归程序来查找连接的子图. 该代码通过从图中的每个未访问顶点遍历所有边(递归)，并在处理过程中用"ingraph = False"标记已访问的那些边来工作. (这些图始终是无向的非加权图).

I have simple recursive program to find connected subgraphs. The code works by traversing, from each unvisited vertex in the graph, all the edges (recursively) and marking those which have been visited with 'ingraph=False' in the process. (the graphs are always undirected unweighted graphs).

我遇到的问题是，对于大型图(子图约为100,000个顶点)，python(-2.7)返回分段错误. 但这在python-2.6中仍然可以正常工作(并且仍然可以).

The problem I have is that for large graphs (with a subgraph of ~100,000 vertices) python(-2.7) returns a segmentation fault. But this worked just fine in python-2.6 (and still does).

有人可以向我解释一下两者之间发生了什么变化(或者可能完全是另外一回事)?有没有办法用python-2.7修复它(最好在迁移到python-3时也不会破裂)?还是应该以非递归方式重写它?

Can someone explain to me what has changed between two (or maybe it's something else entirely)? Is there a way to fix it with python-2.7 (which preferably also doesn't break upon migrating to python-3 at some point)? Or should I rewrite it in a non-recursive way?

谢谢！

这是来源更新:有关非递归解决方案，请参见下面的更新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)

------更新--------

------ UPDATE --------

我做了一个小的递归测试，得出了3台不同计算机的递归限制分别为〜16,000，〜24,000和〜28,000.此外，对于一台PC，结果甚至不是恒定的.两次运行测试给出的限制略有不同.例如，对于第二个，我发现结果在23800和23819之间.

I made a small recursion test which gives recursions limit of ~16,000, ~24,000 and ~28,000 for 3 different computers. Moreover the result is not even constant for one pc. Running the test twice gives slightly different limits. For example for the second I find results between 23800 and 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 ++示例运行良好(至少1百万次推送).

I don't really get which 'C stack' is referred to, as far I can tell there is no default 'stack' implemented in C. In C++ there are stacks but it doesn't have the same limitations. The following C++ example runs fine (at least up to 1M pushes).

#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)

The following C code also goes much deeper (about 10x, ~262,000)

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

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

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

---- UPDATE 2 -----

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

Ok, this is python's intention apparently. Forcing programmers to avoid deep recursion. http://neopythonic.blogspot.ch/2009/04/tail-recursion-elimination.html

无论如何，我现在认为最好以迭代方式重写它.但是然后我可能会使用诸如升压图库之类的图论库从C ++重新开始.如果仍然要重写它，那我也最好做一下.

In any case I now think it is better to rewrite it iteratively. But then I will probably start over in C++, using some graph theory library like the boost graph library. If I am going to have to rewrite it anyway, I might as well do it properly.

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

Nevertheless, I would still appreciate any comments to understand why this happens at these specific sizes.

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

---- UPDATE 3 -----

这里至少是一个快速而肮脏的python重写. 脏，因为最后一行是O(N ^ 2). 通过跟踪尚未访问过哪些顶点的列表，应该有一个更好的O(N)解决方案，但是并没有那么快地看到它，因此这对于我的应用程序是有效的.

Here's at least a quick and dirty python rewrite. Dirty because it's O(N^2) because of the last line. There should be a nicer O(N) solution by keeping track a list of which vertices have not been visited, but didn't see it so quickly and this works for my applications.

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]

推荐答案

您可能在Python实现中的某个地方进行深度递归的堆栈溢出.您可以尝试使用 sys.setrecursionlimit

You probably overflow stack with deep recursion somewhere in Python implementation. You may try changing stack dept with sys.setrecursionlimit

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

Another possibility is that you exhaust dynamic memory. Recursion is normally more taxing.

Python 2.6给您带来了更多的运气.以前的版本需要较少的内存来存储您的算法.

You had more luck with Python 2.6. Previous version required less memory for your algorithm.

Python不是一种功能语言，并且无法优化尾递归.迭代地重写算法可能是一种更好的方法.

Python isn't a functional language and doesn't optimise tail recursion. Rewriting the algorithm iteratively may be a better approach.

这篇关于从python 2.6到2.7进行深度递归的细分错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！