raynus - 1 year ago 76
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]:
parent[table]=getParent2(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]:
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,

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

`getParent(3)`
will gives
`0`
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:
table1=table
table=stack_rec[x[0]][1]

if parent[table]==table:
return parent[table]
else:
stack_rec.pop(x[0])
while table != parent[table]:
table = parent[table]
stack_rec.append([table1,table])

return table

elif len(x)>1:
print("Duplication!")
else:
return parent[table]
``````

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

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]:
chain.append(table)
table = parent[table]