14.01.2011, 18:57, "Alex Boyko" <alex.kyr...@gmail.com>:
> 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
> 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...@ya.ru
--
http://mail.python.org/mailman/listinfo/python-list
