14.01.2011, 14:15, "Alex Boyko" <alex.kyr...@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
Forgot to make new-style object)
class Node(object):
The results for new-style objects are:
$ python postorder.py
building tree...done
0:00:26.180799
doing generator post_order...done
0:00:00.000017
doing non-generator post_order...done
0:00:01.117986
--
jabber: k...@ya.ru
--
http://mail.python.org/mailman/listinfo/python-list
