從python 2.6到2.7深度遞歸的分段錯誤

我有簡單的遞歸程序來查找連接的子圖。該代碼的工作原理是從圖中每個未訪問的頂點遍歷所有邊（遞歸地），並在過程中用'ingraph = False'標記已經訪問的那些邊。（這些圖總是不受加權的圖）。從python 2.6到2.7深度遞歸的分段錯誤

我的問題是，對於大圖（約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)

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

我做了一個小的遞歸這個測試爲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); 
}

---- UPDATE 2 -----

沒關係，這是python的意圖顯然。迫使程序員避免深度遞歸。 http://neopythonic.blogspot.ch/2009/04/tail-recursion-elimination.html

無論如何，我現在認爲最好是迭代地重寫它。但是，我可能會從C++開始，使用一些圖形理論庫，比如boost圖庫。如果我不得不重寫它，我不妨做好。

儘管如此，我仍然很感激任何意見，以瞭解爲什麼發生在這些特定的大小。

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

這裏的至少一個快速和骯髒的蟒蛇重寫。髒，因爲它是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]

來源

2013-10-04 jaap

您可能會在Python實現中的某處深度遞歸堆棧。您可以嘗試更改堆棧部門sys.setrecursionlimit

另一種可能性是您耗盡動態內存。遞歸通常更重要。

你有更多的運氣與Python 2.6。以前的版本需要較少的內存爲您的算法。

Python不是一種功能性語言，不會優化尾遞歸。迭代地重寫算法可能是更好的方法。

來源

2013-10-04 10:27:54 dmitri

我有遞歸限制集到圖表大小'sys.setrecursionlimit（g.size）'，但它仍然崩潰。 – jaap

也可以使用無堆棧的python或pypy。 – Curry

因爲你的python使用c堆棧，它溢出了。 setrecursionlimit不能擴展堆棧大小。它只是在堆棧溢出之前提高異常的限制。 python的遞歸深度有限。 2.6的成功只是幸運的情況。

，你應該從遞歸更改您的代碼迭代式的或使用無堆棧的Python（或pypy）閱讀docs.python.org/2/library/sys.html#sys.setrecursionlimit

來源

2013-10-04 10:48:30 Curry

好吧，我沒有想到它會這麼小，我認爲一層遞歸應該花費一個指針。我進行了一個小測試，給出一個PC的遞歸限制約爲16,000，另一個約爲24,000，另一個約爲28,000。而且，一臺電腦的結果甚至不是恆定的。兩次運行測試給出了稍微不同的限制。（查看更新後的問題）。任何想法如何發生？ – jaap

從python 2.6到2.7深度遞歸的分段錯誤

回答

相關問題