bad generator performance
hi, 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/81910.5600.0000.5900.000 :71(depthFirstIterator2) 4095/10.0600.0000.0800.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. thx, Johannes -- http://mail.python.org/mailman/listinfo/python-list
Re: bad generator performance
sorry, forgot to post the profiling info for the recursive helper function. but generator is still FAR slower... 4095/10.0500.0000.1200.120 file.py:135(rek) Johannes -- http://mail.python.org/mailman/listinfo/python-list
Re: bad generator performance
> 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. yup, i am aware that my generator version is also recursive. but what i thought this would do is "generate" a lazy list of return values (in theory at least). but this still doesn't explain why the yielding is so much slower than the list concatenation! > 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. i loved the generator solution because it was short, concise and lazy, but if i am going to write the closure/continuation/recursion handling manually i'd rather go with the memory-consuming list concatenation... a non-recursive solution to traversing a recursive data type is bound to get ugly, isn't it? i just wondered if there was a concise, clean way of doing this with generators which i had overlooked, or whether there was some blatant mistake in my code. thx, Johannes -- http://mail.python.org/mailman/listinfo/python-list
Re: bad generator performance
> You don't really give the complete story so it's hard to tell what > exactly is going on. For example, I would assume the recursion is > calling the same method (i.e., depthFirstIterator1 or > depthFirstIterator2), but then you posted separate timing information > for a "recursive helper function" so I'm not so sure. Also there is not > much of a hint as to the nature of your data. yeah, sorry. i'm not myself lately ;-)) forget about the helper function, that was nonsense! i used a helper function to build a huge tree as test data, but that is the same function for both cases! the program is supposed to manage bookmarks and i thought it would be a good idea to represent the bookmarks as a tree (with folders as internal nodes and bookmarks as leaves). so, a tree is never going to hold more than say 2000 nodes and is going to be rather wide than deep! > In my testing (on Python 2.3.4 on > Windows XP), the generator version takes about 1/4 of the time that the > list version takes. If both versions call the list version of the method > recursively (i.e., you're only getting the benefit of the generator at > the top level of the recursion), the generator version is still about > 20% faster. > > Timing differences could potentially depend on your data also - things > like how deep vs. wide your tree is. thx a lot and sorry for not supplying my data type and test data! hmm, that totally contradicts my profiling results... on my machine the generator version is repeatedly 10 times slower than the list version as well with python2.3 as with python2.4. i don't want to spam the list with hundreds of lines of source code, so i'll just cry a little and try to do something else than prematurely optimising my bookmark script *gg* thx, Johannes -- http://mail.python.org/mailman/listinfo/python-list
image fourier transform
hi, i've been looking all around the net (google is my friend ;-) for a module to apply fourier transformations on images. the different ones in numerical python and scientific python seem all to be operating on sequences and therefore seem to be 1D fourier transform. anyone know a library/module to do 2D image FFT in a simple manner. or am i just too dumb to see how this is supposed to work with the 1D fourier transforms?? thx, Johannes -- http://mail.python.org/mailman/listinfo/python-list
