On 2007-01-18, [EMAIL PROTECTED] <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list