再帰制限に達し、セグメンテーションフォールト

Question

これらの種類の質問にはかなり多くの質問があり、いずれも私を助けませんでした。

以下の問題では、のの有向グラフのStrong Connected Componentsを実装しようとしています。 ここに私のコードです。

import os 
import sys 
os.system('cls') 
sys.setrecursionlimit(22764) 

from itertools import groupby 
from collections import defaultdict 

## Reading the data in adjacency list form 
data = open("data.txt", 'r') 
G = defaultdict(list) 

for line in data: 
    lst = [int(s) for s in line.split()] 
    G[lst[0]].append(lst[1]) 


print 'Graph has been read!' 



def rev_graph(): 
    revG = defaultdict(list) 
    data = open("data.txt", 'r')  


    for line in data: 
     lst = [ int(s) for s in line.split() ] 
     revG[ lst[1] ].append(lst[0]) 

    print 'Graph has been reversed!' 
    return revG 


class Track(object): 
    """Keeps track of the current time, current source, component leader, 
    finish time of each node and the explored nodes.""" 

    def __init__(self): 
     self.current_time = 0 
     self.current_source = None 
     self.leader = {} 
     self.finish_time = {} 
     self.explored = set() 


def dfs(graph_dict, node, track): 
    """Inner loop explores all nodes in a SCC. Graph represented as a dict, 
    {tail node: [head nodes]}. Depth first search runs recrusively and keeps 
    track of the parameters""" 

    # print 'In Recursion node is ' + str(node) 
    track.explored.add(node) 
    track.leader[node] = track.current_source 
    for head in graph_dict[node]: 


     if head not in track.explored: 
       dfs(graph_dict, head, track) 

    track.current_time += 1 

    track.finish_time[node] = track.current_time 


def dfs_loop(graph_dict, nodes, track): 
    """Outter loop checks out all SCCs. Current source node changes when one 
    SCC inner loop finishes.""" 

    for node in nodes: 

     if node not in track.explored: 


      track.current_source = node 
      dfs(graph_dict, node, track) 


def scc(graph, nodes): 
    """First runs dfs_loop on reversed graph with nodes in decreasing order, 
    then runs dfs_loop on orignial graph with nodes in decreasing finish 
    time order(obatined from firt run). Return a dict of {leader: SCC}.""" 

    out = defaultdict(list) 
    track = Track() 

    reverse_graph = rev_graph() 


    global G 
    G = None 

    dfs_loop(reverse_graph, nodes, track) ## changes here 

    sorted_nodes = sorted(track.finish_time, 
          key=track.finish_time.get, reverse=True) 

    # print sorted_nodes 
    track.current_time = 0 
    track.current_source = None 
    track.explored = set() 

    reverse_graph = None 


    dfs_loop(graph, sorted_nodes, track) 
    for lead, vertex in groupby(sorted(track.leader, key=track.leader.get), 
           key=track.leader.get): 
     out[lead] = list(vertex) 
    return out 


maxNode = max(G.keys()) 
revNodes = list(reversed(range(1, (maxNode + 1)))) 

ans = scc(G, revNodes) 
print 'naman' 
print ans 

ここで、この再帰制限で、セグメンテーションフォルト（コアダンプ）エラーが発生します。この制限より下では、「最大再帰深度がcmpを超えました」というエラーが発生します。

データファイルも添付しています。ここにはlinkがあります。

Answer 1

Rakete1111は、基本的な原則を示しました。これには再帰を使用しないでください。探索され待機しているノードのグローバルリストを簡単に管理できます。それはあなたのメソッドの周りにこれらを渡すために多くのオーバーヘッドを行ってきました。

これを素早く処理するための小さな試みが必要な場合は、トラックをグローバルにして始めます。今では、トラバースルーチンを一意のインスタンスに渡しています。毎回、ローカルコピーをインスタンス化しなければならず、かなりの量のストレージが消費されます。

また、各コールは、ステータスリストを次のコールレベルに渡すと、メモリペナルティが比較的大きくなります。再帰を "while list not empty"というループで置き換えると、たくさんのメモリとその再帰呼び出しをすべて保存することができます。あなたはそれをやわらげることができますか？コーディングヘルプが必要な場合は、コメントを投稿してください。