我的 recursive/iterative 方法有任何替代或改进吗？

Question

我正在尝试使用 python 3.

编写父搜索代码

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

第一个元素的父元素是它自己。
第二个元素的父元素是第一个元素，因此是第二个元素值等于第一个元素的值

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

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

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

我的 recursive/iterative 方法有任何替代或改进吗？

Any alternative or improvement of my recursive/iterative approach?

python

algorithm

python-3.x

recursion

genetic-algorithm