Method calls and stack consumption

[Martin Manns]

On Sun, 15 Apr 2007 07:27:25 +0200
Peter Otten <__peter__ at web.de> wrote:

> Martin Manns wrote:
> 
> > Calling methods of other object instances seems quite expensive on
> > the stack (see example below). Is there a better way of traversing
> > through methods of instances that are connected in a cyclic graph?
> > (The real program's graph contains multiple successors in lists.)

> a = a.a
> while True:
>     a = a()
> 
> That's how you can do it if your real program is similar enough to the
> example...

Thanks for pointing out the oversimplified nature of the original
example.I hope that the following one clarifies the problem.

(I do not know, what has to be stored on the stack, but it should not be
that much, because all recursion calls originate from inside the return
statement.)


from random import randint,seed
import sys
seed()
sys.setrecursionlimit(1000000)

class Node(object):
    def __init__(self):
        self.state = abs(randint(1,1000))
    def GetDepState(self):
        return self.state + max(s.GetDepState() for s in S[self])

class ConditionalBreakNode(Node):
    def GetDepState(self):
        if randint(1,5) > 1:
            return Node.GetDepState(self)
        else:
            return self.state

S = {}
nodes = [Node()]

def AppendNode(curr_node, depth=1):
    global nodes
    r = randint(1,30)
    if r >= depth:
        for i in xrange(randint(1,3)):
            newnode = Node()
            nodes += [newnode]
            try: S[curr_node] += [newnode]
            except: S[curr_node] = [newnode]
            AppendNode(newnode, depth+1)
    else:
        newnode = ConditionalBreakNode()
        nodes += [newnode]
        try: S[curr_node] += [newnode]
        except: S[curr_node] = [newnode]
        S[newnode] = [nodes[0]]
        
AppendNode(nodes[0])
print len(nodes)
print nodes[0].GetDepState()