Comments on Doug Hellmann: PyMOTW: heapq

Thanks for the tip - I didn't know about that.So I...

2008-05-18T20:11:00.000-04:00

Thanks for the tip - I didn't know about that.

So I looked into their source code and found out that the heapq module stores everything in the opposite order from what I do (root node is smallest element - not the largest one). So when I did nlargest, it simply sorted the whole list!

nsmallest, which was "equivalent" to what I was doing, works.

I also replaced my function with a nonrecursive one - no difference. So at the end: With psyco my version is much faster than heapq, but without it is much slower...

I'm sure a non-recursive key function would have a...

2008-05-17T16:26:00.000-04:00

I'm sure a non-recursive key function would have an impact.

As far as where the heapq source is, try this:

$ python
>>> import heapq
>>> print heapq.__file__

Actually, in a sense, I compared psyco on both. ps...

2008-05-17T16:23:00.000-04:00

Actually, in a sense, I compared psyco on both. psyco had little impact on the heapq function.

I used the algorithms given in the Cormen Intro to Algorithms book.

I suspect the reason I got a good speedup with psyco is that a key function I wrote is recursive. I'll try writing a nonrecursive one and see what difference that makes.

But in a more general sense, I would think trying to find the top 10 numbers among 10 million of them using heaps should be significantly faster than using sort. In Python, using heapq, it really wasn't much faster (perhaps a speedup of 2 at most) - which made me wonder if there's some inefficiency in the heapq code.

Do you know where on my system (Linux) I can find the source for heapq? I honestly don't have a clue.

Beetle B., the standard library documentation does...

2008-05-17T16:00:00.000-04:00

Beetle B., the standard library documentation doesn't talk a lot about performance of heappush vs. heapify, but I wouldn't be surprised to find heapify more efficient.

I'm also not surprised to find the code optimzied with psyco runs faster than native Python. That's the point, right? :-)

Thanks for highlighting the module. 1. I haven't l...

2008-05-17T14:17:00.000-04:00

Thanks for highlighting the module.

1. I haven't looked at the source code, but usually heappush is slower (O(n*logn) vs O(n) for heapify). It'd be worth experimenting, but I suspect that for large enough n, it would be faster to read the elements into a list, and heapify it rather than heappush one by one.

2. Regarding nlargest(), here's a relevant blog post. The gist of it is that if you want to get the top n elements, you can either sort the whole list and read them off, or construct a heap and keep popping the largest elements. The assertion is that the latter approach is faster (as you need not sort the whole list, and creating a heap is O(n)).

So I decided to try it out. I created a random list of 1 million integers. I then wrote my own (very simple) heap functions - I did not know at the time of the heapq module - and timed it.

Then I found out about the heapq module and used nlargest(). I was quite surprised to see that my routine was 2-3 times faster (if I used psyco) than the heapq function.

I can send the code over if you want to compare...

Thanks, István! By the way, the code to print the...

2008-05-11T16:26:00.000-04:00

Thanks, István! By the way, the code to print the heap is included in the example source tarball, even though I don't show it here in this post.

What a great tutorial! Showing how the tree change...

2008-05-11T16:20:00.000-04:00

What a great tutorial! Showing how the tree changes after pushing values onto the heap are fantastic.

I'm putting "LazyWeb" on notice ... from now on there is no excuse for not understanding how heaps work ;-)