unbalanced tree iteration issue

[kost BebiX]

14.01.2011, 18:57, "Alex Boyko" <alex.kyrish at gmail.com>:
> 2011/1/14 kost BebiX <k.bx at ya.ru>
>> 14.01.2011, 14:15, "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
>>
>> 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.bx at ya.ru
> 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
>

Well, isn't tree is a root node and it's children? Why do you need Tree class anyway?

p.s.: please, do not top-post the messages, write your reply at bottom because it will then be easier to read for those who will google this page.

-- 
jabber: k.bx at ya.ru