python - 对于 Kosaraju 的算法,我怎样才能摆脱 python 中的堆栈溢出问题?
问题描述
我是一名新程序员,正在学习斯坦福大学的 edX 算法课程。
其中一项编程任务是使用 Kosaraju 算法在具有约 1,000,000 个顶点的图上找到强连通分量。我的实现是从教科书的伪代码到 Python 的最基本的翻译,它在较小的图上运行良好,所以我认为它是正确的。
Python 的默认递归限制为 1000,它达到了限制。
我试过sys.setrecursionlimit(1000000)
了,但这并没有帮助,而是我得到“进程完成,退出代码 -1073741571”,这是一个堆栈溢出。
我发现这两个页面用于增加堆栈大小限制,但不确定如何使用它们中的任何一个:设置堆栈大小、ulimit 命令。
另一个相关的信息是 Python 没有优化尾递归,但我不确定它是否适用于我的代码。
G = {}
for i in range(1, 875715):
G[i] = [0]
for l in open('SCC.txt'):
items = list(map(int, l.split()))
G[items[0]].append(items[1])
Grev = {}
for i in range(1, 875715):
Grev[i] = [0]
for l in open('SCC.txt'):
items = list(map(int, l.split()))
Grev[items[1]].append(items[0])
def TopoSort(G):
for v in G:
if G[v][0] == 0:
DFStopo(G, v)
def DFStopo(G, s):
G[s][0] = 1
global orderedVertexList
for v in G[s][1:]:
if G[v][0] == 0:
DFStopo(G, v)
orderedVertexList.insert(0, s)
def Kosaraju(G, Grev):
TopoSort(Grev)
global numSCC
for v in orderedVertexList:
if G[v][0] == 0:
numSCC = numSCC + 1
DFSSCC(G, v)
def DFSSCC(G, s):
G[s][0] = 1
global SCC
SCC.append(numSCC)
for v in G[s][1:]:
if G[v][0] == 0:
DFSSCC(G, v)
numSCC = 0
orderedVertexList = []
SCC = []
Kosaraju(copy.deepcopy(G), copy.deepcopy(Grev))
解决方案
推荐阅读
- sql - 解析包含整数的列
- c++ - 无法从大括号括起来的初始值设定项列表转换为标准元组
- jenkins - 詹金斯。更改文件中的版本并提交
- vba - VBA MS Word - 一次将所有邮件合并字段插入 Word 文档
- reactjs - 使用地图功能对网页样式做出反应
- sql-server - t-sql,用最后一个值替换 Null - 包含联合
- swift - 设备锁定时全局线程停止
- centos7 - cherrypy 2.3.0 与 Python 2.7.5 兼容吗?
- elixir - Elixir:fs 的编译突然因 rebar_abort 而失败
- php - 找不到本地主机子域 nginx wordpress 的文件