So I mean, your approach with generators showed good results in terms of
time efficiency 'cos iteration was done for root and root's children.
On 14 January 2011 18:57, Alex Boyko <alex.kyr...@gmail.com> wrote:
> Thank you for your reply, but I have question about your code. Your
> defined:
>
> def post_order(self):
> for child in self.childs:
> yield child
> yield self
>
> just for "Node" , not for "Tree", and do
>
> w("doing generator post_order...")
> _t = datetime.now()
> for item in root.post_order():
> fake = item.value
> w("done\n")
> w(datetime.now() - _t)
> w("\n")
>
> what give us only iterating along root's children, not iterating along
> tree...Or I didn't catch your though?
>
> Best Regards
> Alex
>
> 2011/1/14 kost BebiX <k...@ya.ru>
>
> 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
>>
>> Well, I think it's actually because the difference is that you would not
>> do yielding, you would just put everything in memory and then return it.
>>
>> ret_val = [x for x in self.postorder(child)]
>> return ret_val + [self]
>>
>> or something like that (but beware of memory). But that's strange. This
>> code works fast:
>>
>> #!/usr/bin/env python
>> # -*- coding: utf-8 -*-
>>
>> import sys
>>
>> def w(s):
>> sys.stdout.write("%s" % s)
>> sys.stdout.flush()
>>
>> class Node():
>> __slots__ = ('childs', 'value',)
>>
>> def __init__(self, value):
>> self.childs = []
>> self.value = value
>>
>> def post_order(self):
>> for child in self.childs:
>> yield child
>> yield self
>>
>> def build_tree():
>> def append_1000_childs(node):
>> for i in xrange(20):
>> node.childs.append(Node(10))
>>
>> def append_n_levels(node, levels=1):
>> if levels >= 1:
>> append_1000_childs(node)
>> if levels > 1:
>> for child in node.childs:
>> append_n_levels(child, levels - 1)
>>
>> root = Node(10)
>> append_n_levels(root, 5)
>> return root
>>
>> if __name__ == '__main__':
>> from datetime import datetime
>>
>> w("building tree...")
>> _t = datetime.now()
>> root = build_tree()
>> w("done\n")
>> w(datetime.now() - _t)
>> w("\n")
>>
>> w("doing generator post_order...")
>> _t = datetime.now()
>> for item in root.post_order():
>> fake = item.value
>> w("done\n")
>> w(datetime.now() - _t)
>> w("\n")
>>
>> def post_order(root):
>> for child in root.childs:
>> post_order(child)
>> fake = item.value
>>
>> w("doing non-generator post_order...")
>> _t = datetime.now()
>> post_order(root)
>> w("done\n")
>> w(datetime.now() - _t)
>> w("\n")
>>
>> $ python postorder.py
>> building tree...done
>> 0:01:34.422288
>> doing generator post_order...done
>> 0:00:00.000018
>> doing non-generator post_order...done
>> 0:00:01.232272
>>
>> --
>> jabber: k...@ya.ru
>>
>
>
--
http://mail.python.org/mailman/listinfo/python-list
