On benchmarks, heaps, priority queues

[aaronwmail-usenet at yahoo.com]

me> PQPython23 - the Lib implementation
me> PQ0 - my insertion sort based variant
me> PQueue - my "heap" based variant
me> (like PQPython23, but different).

Tim D:
> First of all, you should be running these benchmarks using Python
2.4.
> heapq is considerably faster there ... (Raymond Hettinger rewrote it
all
> in C).
> http://www.python.org/2.4/highlights.html
> Tim Delaney

WHOOPS. Okay after getting past my initial embarassment I tried this,
and it turns out it doesn't make much of a difference.  In particular
PQ0 is still always better if you intersperse many deletes with inserts
or in all cases of size <10000.  Of course other machines will probably
have different characteristics (and yes my py24 contains the _heapq
extension module).

The nasty behavior of PQ0 for insertBench at >100000
I think has to do with large list reallocation.

Hmmm.  This makes me wonder if my bplustree implementation(s) are
faster
than the bsddb modules too...

-- Aaron Watters
===
SOMETHING WENT WRONG IN AIRLINE CRASH, EXPERT SAYS
-- a "real life headline" (that'll be $50,000, please)


ENCLOSURE: Python 2.4 run of
http://xsdb.sourceforge.net/bench/pq3.py on my machine.
=======================

BENCHMARKS FOR 1000

insertBench
__main__.PQPython23 on 1000 elapsed 0.0199999809265 got 1000
__main__.PQ0 on 1000 elapsed 0.00999999046326 got 1000
__main__.PQueue on 1000 elapsed 0.0300002098083 got 1000

mixBench
__main__.PQPython23 on 1000 elapsed 0.0 got 502
__main__.PQ0 on 1000 elapsed 0.00999999046326 got 502
__main__.PQueue on 1000 elapsed 0.0 got 502

BENCHMARKS FOR 10000

insertBench
__main__.PQPython23 on 10000 elapsed 0.260999917984 got 10000
__main__.PQ0 on 10000 elapsed 0.210000038147 got 10000
__main__.PQueue on 10000 elapsed 0.359999895096 got 10000

mixBench
__main__.PQPython23 on 10000 elapsed 0.0700001716614 got 5003
__main__.PQ0 on 10000 elapsed 0.050999879837 got 5003
__main__.PQueue on 10000 elapsed 0.0699999332428 got 5003

BENCHMARKS FOR 100000

insertBench
__main__.PQPython23 on 100000 elapsed 3.26499986649 got 100000
__main__.PQ0 on 100000 elapsed 7.88100004196 got 100000
__main__.PQueue on 100000 elapsed 4.81699991226 got 100000

mixBench
__main__.PQPython23 on 100000 elapsed 0.65099978447 got 50000
__main__.PQ0 on 100000 elapsed 0.461000204086 got 50000
__main__.PQueue on 100000 elapsed 0.661000013351 got 50000

BENCHMARKS FOR 200000

insertBench
__main__.PQPython23 on 200000 elapsed 6.99000000954 got 200000
__main__.PQ0 on 200000 elapsed 28.5010001659 got 200000
__main__.PQueue on 200000 elapsed 10.3849999905 got 200000

mixBench
__main__.PQPython23 on 200000 elapsed 1.29099988937 got 100001
__main__.PQ0 on 200000 elapsed 0.922000169754 got 100001
__main__.PQueue on 200000 elapsed 1.34200000763 got 100001

BENCHMARKS FOR 300000

insertBench
__main__.PQPython23 on 300000 elapsed 11.6970000267 got 300000
__main__.PQ0 on 300000 elapsed 70.3009998798 got 300000
__main__.PQueue on 300000 elapsed 16.8840000629 got 300000

mixBench
__main__.PQPython23 on 300000 elapsed 1.93300008774 got 150000
__main__.PQ0 on 300000 elapsed 1.39199995995 got 150000
__main__.PQueue on 300000 elapsed 1.96300005913 got 150000

BENCHMARKS FOR 400000

insertBench
__main__.PQPython23 on 400000 elapsed 15.5419998169 got 400000
__main__.PQ0 on 400000 elapsed 127.253000021 got 400000
__main__.PQueue on 400000 elapsed 23.0629999638 got 400000

mixBench
__main__.PQPython23 on 400000 elapsed 2.64399981499 got 200000
__main__.PQ0 on 400000 elapsed 1.95300006866 got 200000
__main__.PQueue on 400000 elapsed 2.73399996758 got 200000

BENCHMARKS FOR 500000

insertBench
__main__.PQPython23 on 500000 elapsed 20.8800001144 got 500000
__main__.PQ0 on 500000 elapsed 246.954999924 got 500000
__main__.PQueue on 500000 elapsed 35.9609999657 got 500000

mixBench
__main__.PQPython23 on 500000 elapsed 3.55599999428 got 250000
__main__.PQ0 on 500000 elapsed 2.48300004005 got 250000
__main__.PQueue on 500000 elapsed 3.48500013351 got 250000

BENCHMARKS FOR 1000000

insertBench
__main__.PQPython23 on 1000000 elapsed 44.6940000057 got 1000000
__main__.PQ0 on 1000000 elapsed 1400.5940001 got 1000000
__main__.PQueue on 1000000 elapsed 70.6619999409 got 1000000

mixBench
__main__.PQPython23 on 1000000 elapsed 6.63000011444 got 500001
__main__.PQ0 on 1000000 elapsed 4.73600006104 got 500001
__main__.PQueue on 1000000 elapsed 6.82999992371 got 500001