Home Original page

unbalanced tree iteration issue

kost BebiX k.bx at ya.ru
Fri Jan 14 08:33:34 EST 2011 
14.01.2011, 14:17, "Alex Boyko" <alex.kyrish at gmail.com>:
> Dear All!
>
> I have deal with large unbalanced trees and I have to implement post-order tree traversal. My first attempt is shown below ("Node" and "Tree" classes) and based on recursive generators approach.
>
> class Node():
>     def __init__(self,value):
>         self.childs = []
>         self.value = value
>
> class Tree():
>
>     def __init__(self, root):
>         self.root = root
>         self.numberCells = 1
>
>     def add(self, node, child):
>         node.childs.append(child)
>         self.numberCells+=1
>
>     def __iter__(self):
>         return self.postorder(self.root)
>
>     def postorder(self, node):
>         if node:
>             for child in node.childs:
>                 for n in self.postorder(child):
>                     yield n
>             yield node
>
> It works fine for small test trees. But, my tree has approximately 300000 nodes, and shown post order traversal with generators takes 80 sec against 1 sec with simple recursive routine:
>
> def recursiveFromTop(node):
>     for child in node.childs:
>         recursiveFromTop(child)
>         ## here I can do some computations with current node's data
>
> So, I'd like to know how should I implement (if it's possible of course) __iter__ for my tree class based on recursion without generators? Please, can You show me the ways?
> because I'm very passionate in idea iterate through my tree with simple:
>
> for node in tree:
>    do something with node
>
> Thanks in Advance!
> Best Regards!
> Alex
>
> --
> http://mail.python.org/mailman/listinfo/python-list

God damn pypy is fast))

$ ~/bin/pypy-1.4.1-linux64/bin/pypy ./postorder.py 
building tree...done
0:00:03.000854
doing generator post_order...done
0:00:00.000069
doing non-generator post_order...done
0:00:00.240168

-- 
jabber: k.bx at ya.ru
More information about the Python-list mailing list