aurora wrote: > I love generator and I use it a lot. Lately I've been writing some > recursive generator to traverse tree structures. After taking closer > look I have some concern on its performance. > > Let's take the inorder traversal from > http://www.python.org/peps/pep-0255.html as an example. > > def inorder(t): > if t: > for x in inorder(t.left): > yield x > yield t.label > for x in inorder(t.right): > yield x > > Consider a 4 level deep tree that has only a right child: > > 1 > \ > 2 > \ > 3 > \ > 4 > > > Using the recursive generator, the flow would go like this: > > main gen1 gen2 gen3 gen4 > ---------------------------------------------------- > > inorder(1..4) > > yield 1 > inorder(2..4) > yield 2 > yield 2 > inorder(3..4) > yield 3 > yield3 > yield 3 > inorder(4) > yield 4 > yield 4 > yield 4 > yield 4 > > > Note that there are 4 calls to inorder() and 10 yield. Indeed the > complexity of traversing this kind of tree would be O(n^2)!
You seem to be assuming that a yield statement and a function call are equivalent. I'm not sure that's a valid assumption. Anyway, here's some data to consider: -------------------- test.py -------------------- def gen(n): if n: for i in gen(n/2): yield i yield n for i in gen(n/2): yield i def gen_wrapper(n): return list(gen(n)) def nongen(n, func): if n: nongen(n/2, func) func(n) nongen(n/2, func) def nongen_wrapper(n): result = [] nongen(n, result.append) return result ------------------------------------------------- D:\steve>python -m timeit -s "import test" "test.gen_wrapper(100)" 1000 loops, best of 3: 395 usec per loop D:\steve>python -m timeit -s "import test" "test.nongen_wrapper(100)" 1000 loops, best of 3: 216 usec per loop D:\steve>python -m timeit -s "import test" "test.gen_wrapper(1000)" 100 loops, best of 3: 3.58 msec per loop D:\steve>python -m timeit -s "import test" "test.nongen_wrapper(1000)" 1000 loops, best of 3: 1.59 msec per loop D:\steve>python -m timeit -s "import test" "test.gen_wrapper(10000)" 10 loops, best of 3: 70.5 msec per loop D:\steve>python -m timeit -s "import test" "test.nongen_wrapper(10000)" 10 loops, best of 3: 26.6 msec per loop The non-generator version is consistently faster, somewhere around twice as fast. Of course, I'll still be writing generator-based solutions util I'm certain the recursion's the speed bottleneck in my application. STeVe -- http://mail.python.org/mailman/listinfo/python-list