나는 연결된 서브 그래프를 찾는 간단한 재귀 프로그램을 가지고있다. 코드는 그래프의 각 방문하지 않은 정점에서 (재귀 적으로) 모든 가장자리를 탐색하고 프로세스에서 'ingraph = False'로 방문한 항목을 표시하여 작동합니다. (그래프는 항상 가중치가 부여되지 않은 그래프의 방향이 지정되지 않습니다).파이썬 2.6에서 2.7로 갈 때 깊은 재귀를위한 세그먼트 화 오류
큰 그래프 (~ 100,000 정점의 서브 그래프가있는 경우) 파이썬 (-2.7)은 세그먼트 오류를 반환합니다. 그러나 이것은 파이썬 2.6에서 잘 돌아갔다.
누군가 둘 사이에 어떤 변화가 있었는지 설명 할 수 있습니까 (아니면 완전히 다른 것일 수 있습니다)? 파이썬 -2.7로 해결할 수있는 방법이 있는가? (어떤 점에서 파이썬 -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의 재귀 제한을 제공합니다. 또한 결과는 한 PC에 대해서도 일정하지 않습니다. 테스트를 두 번 실행하면 약간 다른 한계가 있습니다. 나는 지금까지 내가 말할 수있는 C에서 구현 디폴트 '스택'이없는, 정말 언급되는 'C 스택'하지 않는 23800 및 23819.#!/usr/bin/python
import sys
def callme(i):
print(i)
i+=1
callme(i)
sys.setrecursionlimit(int(1e6))
callme(0)
사이에 결과를 찾을 두 번째 예를 들어 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, 이것은 파이썬의 의도 분명히. 심각한 재귀를 피하도록 프로그래머를 강요합니다. http://neopythonic.blogspot.ch/2009/04/tail-recursion-elimination.html
나는 지금 그것을 반복적으로 다시 쓰는 것이 낫다고 생각한다. 그렇다면 아마도 C++에서 시작하여 부스트 그래프 라이브러리와 같은 그래프 이론 라이브러리를 사용할 것입니다. 어쨌든 그것을 다시 작성해야한다면 제대로 할 수도 있습니다.
그럼에도 불구하고이 특정 크기에서 이것이 발생하는 이유를 이해하려면 모든 의견을 보내 주시면 감사하겠습니다.
---- UPDATE 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]
docs.python.org/2/library/sys.html#sys.setrecursionlimit 읽어 반복 스타일이나 사용 스택리스 파이썬 (또는 pypy)에 재귀에서 코드를 변경해야 그래프 크기 'sys.setrecursionlimit (g.size)'하지만 여전히 충돌합니다. – jaap
또한 스택리스 파이썬 또는 스택리스 기능이있는 pypy를 사용할 수 있습니다. – Curry