A note on heapq module

[Neil Cerutti]

On 2007-01-18, bearophileHUGS at lycos.com <bearophileHUGS at lycos.com> wrote:
> Neil Cerutti:
>> One more idea, cribbed from the linked list thread elsewhere:
>> it might be nice if your Heap could optionally use an
>> underlying collections.deque instead of a list. I don't know
>> how excellent Python's deque is, but it's possible a deque
>> would provide a faster heap than a contiguous array. C++'s
>> std::deque is the default implementation of C++'s
>> std::priority_queue for that reason (unless I'm confused
>> again).
>
> If you have some minutes you can do few speed tests and show us
> the code and the timing results...

collections.deque is the loser.

Here's the output of the program from my last run:

list: 5.81679827554
deque: 6.40347742423
C heapq: 2.24028186815

Here's the program. You can customize it somewhat to attempt to
model a real program. It builds up a heap of random integers to
some size, performs random pushes and pops for a while, and then
pops the heap down until it's empty.

import random
import timeit

OPCOUNT = 5000
HEAP_SIZE = 100

# Create a random sequence of pushes and pops.
pushes = 0
ops = []
for i in xrange(OPCOUNT):
    x = random.randint(0, 1)
    if x == 0 or pushes < HEAP_SIZE:
        pushes += 1
        ops.append(0)
    else: 
        pushes -= 1
        ops.append(1)
# Pop off the rest
for i in xrange(pushes):
    ops.append(1)

def test(mod, cont):
    for op in ops:
        if op:
            mod.heappop(cont)
        else:
            mod.heappush(cont, random.randint(0, 150))

# heapqd is the pure Python heapq module without the C implementation.
t1 = timeit.Timer("test(heapqd, list())",
        "from __main__ import test; import heapqd")
t2 = timeit.Timer("test(heapqd, deque())", 
        "from __main__ import test; "\
        "from collections import deque; "\
        "import heapqd")
t3 = timeit.Timer("test(heapq, list())",
        "from __main__ import test; import heapq")
print "list:", t1.timeit(100)
print "deque:", t2.timeit(100)
print "C heapq:", t3.timeit(100)

-- 
Neil Cerutti
The Pastor would appreciate it if the ladies of the congregation would lend
him their electric girdles for the pancake breakfast next Sunday morning.
--Church Bulletin Blooper

-- 
Posted via a free Usenet account from http://www.teranews.com