我的递归/迭代方法有什么替代或改进吗？

Question

我正在尝试使用python3编写一个父级搜索代码。你知道吗

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]

尽管这种方法似乎显示出很好的速度，但它在非常大的父数组中面临堆栈溢出问题。你知道吗

（*设置recursionlimit也会导致系统错误代码7。）

我试着把它改成迭代法

def getParent3(table):

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

    return table

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

在不改变recursionlimit的情况下，有没有改进这段代码的方法？你知道吗

谢谢你。你知道吗

---

很抱歉没有一个示例数据，这是一个非常大的数据（10000+），所以这里是这个函数的一个小示例。你知道吗

例如

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

getParent(3)将作为结果给出0

因为第四个元素的父元素（0-base）是第二个元素，而第二个元素的父元素是第一个元素

它是这样的，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

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