raynus raynus - 1 year ago 51
Python Question

Any alternative or improvement of my recursive/iterative approach?

I'm trying to write a parent searching code using python 3.

Parent is a 0-based-array that contain a parent of that element.
For example, parent=[0,0] means that

  1. Parent of the first element is itself.

  2. Parent of the second element is the first element, therefore second element
    value is equal to first element's value

First, I tried using a recursive approach.

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

Even though this approach seems to shows a very good speed, it faced a stack-overflow problem in a very large parent array.

(*Setting recursionlimit also resulted in a system error code 7.)

I tried modified it in to iterative approach

def getParent3(table):

while table!=parent[table]:

return table

Unfortunately it's running unacceptably slow on the same large parent array.

Any ideas to improve this code without changing the recursionlimit?

Thank you.

Sorry for not having a sample data, it's a really a large one (10000+) so here is a small sample of this function.

For example,


will gives
as a result

Since parent of the 4th element (0-base) is the 2nd element, and the parent of the 2nd element is 1st element

It goes like this, 3-->1-->0

-- Update--

Unfortunately, even though all of the code provides an accurate answer. None of them can make it within time constraint. (except for the recursive approach, if it's not facing a stackoverflow problem)

I tried to implement stack as shown below but it seems to slower the code :(

def getParent6_old(table):

if parent[table]!=table:
x=[i for i , x in enumerate(stack_rec) if x[0] ==table ]

if len(x)!=0:

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

return table

elif len(x)>1:
return parent[table]

I think it's time to give up as I already spend more than a week on this.

Thank you for your help.

Answer Source

You didn't give us any data to test it on, so I'm assuming @Cel Skeggs identified the key difference in her comment. Fleshing out her suggestion (but untested because - again - you supplied no data):

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

But the speed difference you saw doesn't really make sense unless you're calling the function multiple times at the top level - in which case, collapsing paths can make a huge difference. However, you didn't say anything about that either ;-)