Thank you for your reply, but I have question about your code. Your defined:<div><br></div><div><div> def post_order(self):</div><div> for child in self.childs:</div><div> yield child</div><div> yield self</div>
<div><br></div><div>just for "Node" , not for "Tree", and do</div><div><br></div><div> w("doing generator post_order...")<br> _t = datetime.now()<br> for item in root.post_order():<br> fake = item.value<br>
w("done\n")<br> w(datetime.now() - _t)<br> w("\n")</div><div><br></div><div>what give us only iterating along root's children, not iterating along tree...Or I didn't catch your though?</div>
<div><br></div><div>Best Regards</div><div>Alex</div><div><div><br><div class="gmail_quote">2011/1/14 kost BebiX <span dir="ltr"><<a href="mailto:k.bx@ya.ru">k.bx@ya.ru</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
14.01.2011, 14:15, "Alex Boyko" <<a href="mailto:alex.kyrish@gmail.com">alex.kyrish@gmail.com</a>>:<br>
<div><div></div><div class="h5">> Dear All!<br>
><br>
> 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.<br>
><br>
> class Node():<br>
> def __init__(self,value):<br>
> self.childs = []<br>
> self.value = value<br>
><br>
> class Tree():<br>
><br>
> def __init__(self, root):<br>
> self.root = root<br>
> self.numberCells = 1<br>
><br>
> def add(self, node, child):<br>
> node.childs.append(child)<br>
> self.numberCells+=1<br>
><br>
> def __iter__(self):<br>
> return self.postorder(self.root)<br>
><br>
> def postorder(self, node):<br>
> if node:<br>
> for child in node.childs:<br>
> for n in self.postorder(child):<br>
> yield n<br>
> yield node<br>
><br>
> 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:<br>
><br>
> def recursiveFromTop(node):<br>
> for child in node.childs:<br>
> recursiveFromTop(child)<br>
> ## here I can do some computations with current node's data<br>
><br>
> 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?<br>
> because I'm very passionate in idea iterate through my tree with simple:<br>
><br>
> for node in tree:<br>
> do something with node<br>
><br>
> Thanks in Advance!<br>
> Best Regards!<br>
> Alex<br>
><br>
</div></div>> --<br>
> <a href="http://mail.python.org/mailman/listinfo/python-list" target="_blank">http://mail.python.org/mailman/listinfo/python-list</a><br>
<br>
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.<br>
<br>
ret_val = [x for x in self.postorder(child)]<br>
return ret_val + [self]<br>
<br>
or something like that (but beware of memory). But that's strange. This code works fast:<br>
<br>
#!/usr/bin/env python<br>
# -*- coding: utf-8 -*-<br>
<br>
import sys<br>
<br>
def w(s):<br>
sys.stdout.write("%s" % s)<br>
sys.stdout.flush()<br>
<br>
class Node():<br>
__slots__ = ('childs', 'value',)<br>
<div class="im"><br>
def __init__(self, value):<br>
self.childs = []<br>
self.value = value<br>
<br>
</div> def post_order(self):<br>
for child in self.childs:<br>
yield child<br>
yield self<br>
<br>
def build_tree():<br>
def append_1000_childs(node):<br>
for i in xrange(20):<br>
node.childs.append(Node(10))<br>
<br>
def append_n_levels(node, levels=1):<br>
if levels >= 1:<br>
append_1000_childs(node)<br>
if levels > 1:<br>
<div class="im"> for child in node.childs:<br>
</div> append_n_levels(child, levels - 1)<br>
<br>
root = Node(10)<br>
append_n_levels(root, 5)<br>
return root<br>
<br>
if __name__ == '__main__':<br>
from datetime import datetime<br>
<br>
w("building tree...")<br>
_t = datetime.now()<br>
root = build_tree()<br>
w("done\n")<br>
w(datetime.now() - _t)<br>
w("\n")<br>
<br>
w("doing generator post_order...")<br>
_t = datetime.now()<br>
for item in root.post_order():<br>
fake = item.value<br>
w("done\n")<br>
w(datetime.now() - _t)<br>
w("\n")<br>
<br>
def post_order(root):<br>
for child in root.childs:<br>
post_order(child)<br>
fake = item.value<br>
<br>
w("doing non-generator post_order...")<br>
_t = datetime.now()<br>
post_order(root)<br>
w("done\n")<br>
w(datetime.now() - _t)<br>
w("\n")<br>
<br>
$ python postorder.py<br>
building tree...done<br>
0:01:34.422288<br>
doing generator post_order...done<br>
0:00:00.000018<br>
doing non-generator post_order...done<br>
0:00:01.232272<br>
<font color="#888888"><br>
--<br>
jabber: <a href="mailto:k.bx@ya.ru">k.bx@ya.ru</a><br>
</font></blockquote></div><br></div></div></div>