473,729 Members | 1,873 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

performance of recursive generator

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)!
Compare that with a similar recursive function using callback instead of
generator.

def inorder(t, foo):
if t:
inorder(t.left, foo):
foo(t.label)
inorder(t.right , foo):
The flow would go like this:

main stack1 stack2 stack3 stack4
----------------------------------------------------

inorder(1..4)
foo(1)
inorder(2..4)
foo(2)
inorder(3..4)
foo(3)
inorder(4)
foo(4)
There will be 4 calls to inorder() and 4 call to foo(), give a reasonable
O(n) performance.

Is it an inherent issue in the use of recursive generator? Is there any
compiler optimization possible?
Aug 11 '05 #1
7 2656
Is it an inherent issue in the use of recursive generator? Is there any
compiler optimization possible?
Hi, I could be misunderstandin g it myself, but I think the short answer to
your question is that its an inherent limitation.
def inorder(t):
if t:
for x in inorder(t.left) :
yield x
yield t.label
for x in inorder(t.right ):
yield x
Using the generator you pass the tree node labels back up through each
nested generator - therefore the deeper you are, obviously, the more
yields it will take to pass the data back up.

As you seem to have realised, you are, in effect traversing back up the
tree from every node you visit, in order to deliver the data.
def inorder(t, foo):
if t:
inorder(t.left, foo):
foo(t.label)
inorder(t.right , foo):
Inherently, by using callbacks you are shortcutting this - delivering
direct. (I assume foo is a list you're building or something similar) Of
course there might be some cunning alternative formulation, but I can't
think of it :-)

To optimise this away, I guess python would need to see this:
for x in inorder(t.left) :
yield x


And understand that you're just asking it to pass on all yields from a
nested generator as if they were coming from this generator.

Perhaps if there existed some kind of syntax to hint this to python it
could optimise it away, eg:

yield *inorder(t.left )

.... but AFAIK there isn't :-( so I guess you'll have to avoid recursive
generators for this app!

Matt

--

| Matt Hammond
| R&D Engineer, BBC Research and Development, Tadworth, Surrey, UK.
Aug 11 '05 #2
aurora wrote:

<generator example>
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)!
<recursive function>
There will be 4 calls to inorder() and 4 call to foo(), give a
reasonable O(n) performance.

Is it an inherent issue in the use of recursive generator? Is there
any compiler optimization possible?


Do you actually have timing evidence that this is a problem with the data
you are processing? The complexity of the algorithm may be important for
very large data sets, but until you time it you won't know whether it is
likely to be an issue for realistic data.

Your O(n^2) for the generator example is only n^2 if the tree is, as in
your example, completely unbalanced. If you can keep your binary tree
balanced it is n log n. If the tree is likely to become as wildly
unbalanced as in your example then you should consider using a different
data structure (e.g. a btree) where O(n log n) would be the worst case.

If you make the more realistic comparison of n calls to foo, versus nlogn
yields the question is at what point the greater number of fast yields
outweighs the lesser number of slow Python function calls. Until you know
speed really is an issue, go with whichever method makes the programming
easier.
Aug 11 '05 #3

"aurora" <au******@gmail .com> wrote in message
news:op******** *******@news.ci sco.com...
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.


When the stacked yields become a measureable problem over the anticipated
future use of the code, then you can rewrite the obviously correct
recursive generator as a less-obviously correct iterative generator, using
the first to generate test results to check the second.

Terry J. Reedy

Aug 11 '05 #4
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_wrapp er(100)"
1000 loops, best of 3: 395 usec per loop

D:\steve>python -m timeit -s "import test" "test.nongen_wr apper(100)"
1000 loops, best of 3: 216 usec per loop

D:\steve>python -m timeit -s "import test" "test.gen_wrapp er(1000)"
100 loops, best of 3: 3.58 msec per loop

D:\steve>python -m timeit -s "import test" "test.nongen_wr apper(1000)"
1000 loops, best of 3: 1.59 msec per loop

D:\steve>python -m timeit -s "import test" "test.gen_wrapp er(10000)"
10 loops, best of 3: 70.5 msec per loop

D:\steve>python -m timeit -s "import test" "test.nongen_wr apper(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
Aug 11 '05 #5
On Thu, 11 Aug 2005 01:18:11 -0700, Matt Hammond
<ma**********@r d.bbc.co.uk> wrote:
Is it an inherent issue in the use of recursive generator? Is there any
compiler optimization possible?
Hi, I could be misunderstandin g it myself, but I think the short answer
to your question is that its an inherent limitation.


....
Perhaps if there existed some kind of syntax to hint this to python it
could optimise it away, eg:

yield *inorder(t.left )

... but AFAIK there isn't :-( so I guess you'll have to avoid recursive
generators for this app!

That would be unfortunately. I think generator is most elegant in
traversing recursive structure. It is non-trivial to use most other
methods. But the O(n^2) price tag is a big caveat to keep in mind.

Of course I agree we should not optimize prematurely. I'm not about to
rewrite my recursive generators just yet. But O(n^2) complexity is
something important to bear in mind. It doesn't necessary cause problems
in practice. But it might.
Aug 11 '05 #6
> You seem to be assuming that a yield statement and a function call are
equivalent. I'm not sure that's a valid assumption.
I don't know. I was hoping the compiler can optimize away the chain of
yields.
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
-------------------------------------------------


This test somehow water down the n^2 issue. The problem is in the depth of
recursion, in this case it is only log(n). It is probably more interesting
to test:

def gen(n):
if n:
yield n
for i in gen(n-1):
yield i
Aug 11 '05 #7
aurora wrote:
This test somehow water down the n^2 issue. The problem is in the depth
of recursion, in this case it is only log(n). It is probably more
interesting to test:

def gen(n):
if n:
yield n
for i in gen(n-1):
yield i


You should be able to do this yourself ;) but here's the results anyway:

-------------------- test.py --------------------
def gen(n):
if n:
yield n
for i in gen(n-1):
yield i

def gen_wrapper(n):
return list(gen(n))

def nongen(n, func):
if n:
func(n)
nongen(n-1, func)

def nongen_wrapper( n):
result = []
nongen(n, result.append)
return result
-------------------------------------------------

D:\steve>python -m timeit -s "import test" "test.gen_wrapp er(10)"
10000 loops, best of 3: 22.3 usec per loop

D:\steve>python -m timeit -s "import test" "test.nongen_wr apper(10)"
100000 loops, best of 3: 12 usec per loop

D:\steve>python -m timeit -s "import test" "test.gen_wrapp er(20)"
10000 loops, best of 3: 60.8 usec per loop

D:\steve>python -m timeit -s "import test" "test.nongen_wr apper(20)"
10000 loops, best of 3: 20.9 usec per loop

D:\steve>python -m timeit -s "import test" "test.gen_wrapp er(100)"
1000 loops, best of 3: 1.01 msec per loop

D:\steve>python -m timeit -s "import test" "test.nongen_wr apper(100)"
10000 loops, best of 3: 93.3 usec per loop

It does appear that you get O(N**2)-ish behavior, but the difference
isn't horribly noticeable at a depth of 10 or 20. How deep are your trees?

I also have to mention that, for this kind of problem, it's silly to use
any recursive solution, when there's a faster non-recursive solution:

-------------------- test.py --------------------
....
def nonrecur(n):
result = []
append = result.append
while n:
append(n)
n -= 1
return result
-------------------------------------------------

D:\steve>python -m timeit -s "import test" "test.nonrecur( 10)"
100000 loops, best of 3: 6.26 usec per loop

D:\steve>python -m timeit -s "import test" "test.nonrecur( 100)"
10000 loops, best of 3: 37.9 usec per loop

Sure, this only works on non-branching trees, but if that's what you're
worried about, use the solution designed for it. ;)

STeVe
Aug 11 '05 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

10
1934
by: MetalOne | last post by:
I am trying to write a generator function that yields the index position of each set bit in a mask. e.g. for x in bitIndexGenerator(0x16): #10110 print x --> 1 2 4 This is what I have, but it does not work. Changing yield to print, shows that the recursion works correctly.
8
2307
by: Paul Chiusano | last post by:
I've been playing around with generators and have run into a difficulty. Suppose I've defined a Node class like so: class Node: def __init__(self, data=None, left=None, right=None): self.children = self.children.append(left) self.children.append(right) self.data = data
19
2291
by: Carlos Ribeiro | last post by:
Hello all, Here I am using some deeply nested, tree-like data structures. In some situations I need to traverse the tree; the old-style way to do it is to write a recursive method on the node class, as in: def walk(self): """old-style recursive tree traversal""" child.do_something for child in childs:
10
5672
by: Steve Goldman | last post by:
Hi, I am trying to come up with a way to develop all n-length permutations of a given list of values. The short function below seems to work, but I can't help thinking there's a better way. Not being a computer scientist, I find recursive functions to be frightening and unnatural. I'd appreciate if anyone can tell me the pythonic idiom to accomplish this. Thanks for your help,
2
1292
by: Johannes Ahl mann | last post by:
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
6
4532
by: Talin | last post by:
I've been using generators to implement backtracking search for a while now. Unfortunately, my code is large and complex enough (doing unification on math expressions) that its hard to post a simple example. So I decided to look for a simpler problem that could be used to demonstrate the technique that I am talking about. I noticed that PEP 255 (Simple Generators) refers to an implementation of the "8 Queens" problem in the lib/test...
2
1730
by: James Stroud | last post by:
This was my answer to the thread "new in programing": def do_something(*args): print args def do_deeply(first, depth, lim, doit=True, *args): if depth < lim: do_deeply(first+1, depth+1, lim, False, *args) if first <= depth: do_deeply(first+1, depth, lim, True, *args + (first,))
8
1915
by: birchb | last post by:
While working on type expressions I am rather stuck for a way to express recursive types. A simple example of this is a singly-linked list of integers. In some languages you have compiler syntax which suspends evaluation so you can have recursive types. e.g. typedef Linked_List := int, Linked_List In LISP I would use a macro.
14
3481
by: Fabian Steiner | last post by:
Hello! I have got a Python "Device" Object which has got a attribute (list) called children which my contain several other "Device" objects. I implemented it this way in order to achieve a kind of parent/child relationship. Now I would like to get all children of a given "Device" object and thought that it would be the best way to use recursive function.
0
8767
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9428
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
9222
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8168
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6722
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
4537
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4799
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3246
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2702
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.