python - 我的递归/迭代方法有任何替代或改进吗？

Question

我正在尝试使用 python 3 编写父搜索代码。

Parent 是一个基于 0 的数组，其中包含该元素的父元素。例如parent=[0,0]表示

1. 第一个元素的父元素是它自己。

2. 第二个元素的父元素是第一个元素，因此是第二个元素值等于第一个元素的值

首先，我尝试使用递归方法。

def getParent2(table):
    # find parent and compress path
    if table!=parent[table]:
        parent[table]=getParent2(parent[table])
    return parent[table]

尽管这种方法似乎显示出非常快的速度，但它在非常大的父数组中遇到了堆栈溢出问题。

(*设置递归限制也会导致系统错误代码 7。)

我尝试将其修改为迭代方法

def getParent3(table):

    while table!=parent[table]:
        table=parent[table]    

    return table

不幸的是，它在同一个大型父数组上运行速度慢得令人无法接受。

有什么想法可以在不改变递归限制的情况下改进这段代码吗？

谢谢。

---

很抱歉没有样本数据，它真的很大(10000+)所以这里是这个函数的一个小样本。

例如，

parent=[0,0,2,1,2]

getParent(3) 将返回 0 作为结果

因为第 4 个元素(0-base)的父元素是第 2 个元素，而第 2 个元素的父元素是第 1 个元素

它是这样的，3-->1-->0

Answer 1

你没有给我们任何数据来测试它，所以我假设@Cel Skeggs 在她的评论中确定了关键差异。充实她的建议(但未经测试，因为 - 再一次 - 你没有提供任何数据):

def getParent4(table):
    chain = []
    while table != parent[table]:
        chain.append(table)
        table = parent[table]    
    for link in chain:
        parent[link] = table
    return table

但是您看到的速度差异并没有真正意义，除非您在顶层多次调用该函数 - 在这种情况下，折叠路径会产生巨大的差异。但是，你也没有说什么 ;-)