Johannes Ahl mann wrote: > i am in the process of profiling an application and noticed how much > time my depth first generator for walking a tree data structure took. > > i wrote the same thing as a recursive function producing an array, and > this non-generator version is nearly 10 times faster! > > any ideas why this is, what i did wrong... > for some reason the generator version appears as being called > much more > often than the recursive one. no idea why that is, but the data is > definitely identical! > > here the output from the python profiler and the respective code: > > ### snip ### > > ncalls tottime percall cumtime percall filename:lineno(function) > 94209/8191 0.560 0.000 0.590 0.000 > :71(depthFirstIterator2) > 4095/1 0.060 0.000 0.080 0.080 :62(depthFirstIterator1) > > ### snip ### > > def depthFirstIterator1(self, depth = 0): > ret = [[self, True, depth]] > > if self.isFolder(): > for c in self.children: > ret = ret + c.depthFirstIterator(depth = depth + 1) > > return ret + [[self, False, depth]] > > def depthFirstIterator2(self, depth = 0): > yield [self, True, depth] > > if self.isFolder(): > for c in self.children: > for y in c.depthFirstIterator(depth = depth + 1): > yield y > > yield [self, False, depth] > > ### snip ### > > i'd appreciate any comments or explanations why the generator might be > so much slower, as i had just decided to use generators more > frequently > and in the respective PEP they are praised as generally fast.
Um. Under my definition of "recursion", you haven't really removed recursion in the generator version. That is, you're still calling the depthFirstIterator method upon each iteration--you've just changed from list-concatenation to yielding instead, which trades off list-management overhead for closure-maintenance overhead. A truly non-recursive implementation would probably exist outside of whatever class you've got this method in, and would keep its own pointer to the current node as it traversed the tree. Hope that helps, Robert Brewer MIS Amor Ministries [EMAIL PROTECTED] -- http://mail.python.org/mailman/listinfo/python-list