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 -- http://mail.python.org/mailman/listinfo/python-list
