Method calls and stack consumption

Martin Manns mmanns at gmx.net
Sun Apr 15 20:43:05 CEST 2007


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()




More information about the Python-list mailing list