improving heapq efficiency

Question

So I find myself taking advantage of heapq for some calculations. However, for the problem I am working on, it runs slow because the heap gets pretty big.

I thought I had an option to speed it up. Rather than creating a giant heap, make it a heap of heaps. But, surprisingly to me, the "more efficient" code is significantly slower. There's a bit more overhead in that more efficient code, but I really thought it would win by a lot. Having stripped down the problem, I've got two functions that do the same net calculation. f1 is the "naive" (and faster) version. f2 is the "improved" (but slower) version. I do some random number generation in both, but I use the same seed, so it really is the same thing.

import random
import heapq
def f1():
    random.seed(1)
    Q=[0]
    while Q:
        value = heapq.heappop(Q)
        #print value
        if value<0.5:
            for counter in range(16):
                heapq.heappush(Q,value + 0.1 + (random.random()/1000))
    print value

def f2():
    random.seed(1)
    Q=[[0]]
    while Q:
        subQ = heapq.heappop(Q)
        value = heapq.heappop(subQ)
        #print value
        if subQ:
            heapq.heappush(Q,subQ)
        newQ = []
        if value<0.5:
            for counter in range(16):
                newQ.append(value + 0.1 + (random.random()/1000))
            heapq.heapify(newQ)
            heapq.heappush(Q,newQ)
    print value

Why does the heap of heaps (f2) run significantly slower? It should call heappush the same number of times, and heappop twice as many times. But the size of the heaps should be significantly smaller, so I expected it to run faster.

Answer 1

So I just wasn't pushing the code hard enough. Here's some modified code. When the subQ is made very large, the benefit I was after appears.

def f1(m,n):
    random.seed(1)
    Q=[0]
    for counter in range(m):
        value = heapq.heappop(Q)
        #print value
        for newcounter in range(n):
            heapq.heappush(Q,random.random())
    print value #should be the same for both methods, so this is just a test
    
def f2(m,n):
    random.seed(1)
    Q=[[0]]
    for counter in range(1000000):
        subQ = heapq.heappop(Q)
        value = heapq.heappop(subQ)
        #print value
        if subQ:
            heapq.heappush(Q,subQ)
        newQ = []
        for newcounter in range(n):
            newQ.append(random.random())
        heapq.heapify(newQ)
        heapq.heappush(Q,newQ)
    print value #should be the same for both methods, so this is just a test

When I profile f1(1000000,10) and f2(1000000,10) I get run times of 10.7 seconds and 14.8 seconds. The relevant details are:

f1:

ncalls tottime percall cumtime percall filename:lineno(function)

1000000 1.793 0.000 1.793 0.000 {_heapq.heappop}

10000000 3.856 0.000 3.856 0.000 {_heapq.heappush}

f2:

1000000 1.095 0.000 1.095 0.000 {_heapq.heapify}

2000000 2.628 0.000 2.628 0.000 {_heapq.heappop}

1999999 2.245 0.000 2.245 0.000 {_heapq.heappush}

10000000 1.114 0.000 1.114 0.000 {method 'append' of 'list' objects}

So net f2 loses out because of the extra heappop, as well as heapify and append. It does better on heappush.

But when I go and challenge it with a larger internal loop and run f1(1000,100000) and f2(1000,100000) we get

f1:

1000 0.015 0.000 0.015 0.000 {_heapq.heappop}

100000000 28.730 0.000 28.730 0.000 {_heapq.heappush}

f2:

1000 19.952 0.020 19.952 0.020 {_heapq.heapify}

2000 0.011 0.000 0.011 0.000 {_heapq.heappop}

1999 0.006 0.000 0.006 0.000 {_heapq.heappush}

100000000 6.977 0.000 6.977 0.000 {method 'append' of 'list' objects}

So we now do much better on heappush, and it's now enough that f2 runs faster (69 seconds versus 75 seconds).

So it turns out I just hadn't pushed my code sufficiently hard. I needed things to get large enough that many calls to heappush became slower than many calls to heapify.