On benchmarks, heaps, priority queues

Discussion in 'Python' started by aaronwmail-usenet@yahoo.com, Jan 26, 2005.

  1. Guest

    I've been wondering about benchmarks recently.

    What is a fair benchmark?

    How should benchmarks be vetted or judged?

    I decided to see what you folks thought, so for discussion I
    compared two priority queue implementations I
    published for Python in 1995 against the "heap" priority
    queue implementation added to the python distribution
    recently (python 2.3+).

    My implementations and the benchmark code are in

    http://xsdb.sourceforge.net/bench/pq3.py

    (benchmark code near the bottom of the file). The python
    standard implementation should be in your Lib/ directory.

    Below please find the numerical results of the benchmarks.
    They compare the implementations

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

    There are 2 benchmarks used.

    insertBench
    -- which does insertions followed by deletes.
    mixBench
    -- which does insertions and deletes mixed together.

    Here is my summary of the results:

    1) For sizes less than 10000 the insertion
    sort PQ0 is always better.

    2) For insertBench sized >10000 PQ0 is very
    bad and the other two are comparable with
    PQPython23 always a little faster.

    3) For mixBench both of my implementations are
    better than the Python23 implementation for
    all sizes tested, but PQ0 is far superior.

    Here is my analysis of the results:

    1) The python23 implementation is best when you
    expect to be doing mainly inserts with few deletions
    and the expected size is >10000 (otherwise use pq0).

    2) PQ0 is best if you expect to be doing many deletions
    interspersed with many inserts.

    3) PQueue is generally worse than the other two
    unless you want to use a non-standard comparison
    function (which the others don't support).

    My questions to you:

    Are my conclusions valid?

    What is a better way to perform and publish benchmarks?

    -- thanks, Aaron Watters

    ===
    JUVENILE COURT TO TRY SHOOTING SUSPECT
    -- a "real life headline" (that should work)

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

    BENCHMARKS FOR 1000

    insertBench
    __main__.PQPython23 on 1000 elapsed 0.039999961853 got 1000
    __main__.PQ0 on 1000 elapsed 0.00999999046326 got 1000
    __main__.PQueue on 1000 elapsed 0.0299999713898 got 1000

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

    BENCHMARKS FOR 10000

    insertBench
    __main__.PQPython23 on 10000 elapsed 0.261000156403 got 10000
    __main__.PQ0 on 10000 elapsed 0.209999799728 got 10000
    __main__.PQueue on 10000 elapsed 0.361000061035 got 10000

    mixBench
    __main__.PQPython23 on 10000 elapsed 0.0599999427795 got 5003
    __main__.PQ0 on 10000 elapsed 0.0500001907349 got 5003
    __main__.PQueue on 10000 elapsed 0.0699999332428 got 5003

    BENCHMARKS FOR 100000

    insertBench
    __main__.PQPython23 on 100000 elapsed 3.24500012398 got 100000
    __main__.PQ0 on 100000 elapsed 7.93099999428 got 100000
    __main__.PQueue on 100000 elapsed 4.82699990273 got 100000

    mixBench
    __main__.PQPython23 on 100000 elapsed 0.641000032425 got 50000
    __main__.PQ0 on 100000 elapsed 0.470999956131 got 50000
    __main__.PQueue on 100000 elapsed 0.651000022888 got 50000

    BENCHMARKS FOR 200000

    insertBench
    __main__.PQPython23 on 200000 elapsed 6.98000001907 got 200000
    __main__.PQ0 on 200000 elapsed 28.3209998608 got 200000
    __main__.PQueue on 200000 elapsed 10.4350001812 got 200000

    mixBench
    __main__.PQPython23 on 200000 elapsed 1.29099988937 got 100001
    __main__.PQ0 on 200000 elapsed 0.911999940872 got 100001
    __main__.PQueue on 200000 elapsed 1.33200001717 got 100001

    BENCHMARKS FOR 300000

    insertBench
    __main__.PQPython23 on 300000 elapsed 10.9159998894 got 300000
    __main__.PQ0 on 300000 elapsed 69.6300001144 got 300000
    __main__.PQueue on 300000 elapsed 19.3279998302 got 300000

    mixBench
    __main__.PQPython23 on 300000 elapsed 2.4430000782 got 150000
    __main__.PQ0 on 300000 elapsed 1.58299994469 got 150000
    __main__.PQueue on 300000 elapsed 2.14300012589 got 150000

    BENCHMARKS FOR 400000

    insertBench
    __main__.PQPython23 on 400000 elapsed 16.2630000114 got 400000
    __main__.PQ0 on 400000 elapsed 153.661000013 got 400000
    __main__.PQueue on 400000 elapsed 24.7860000134 got 400000

    mixBench
    __main__.PQPython23 on 400000 elapsed 2.91400003433 got 200000
    __main__.PQ0 on 400000 elapsed 1.8630001545 got 200000
    __main__.PQueue on 400000 elapsed 2.73399996758 got 200000

    BENCHMARKS FOR 500000

    insertBench
    __main__.PQPython23 on 500000 elapsed 20.1890001297 got 500000
    __main__.PQ0 on 500000 elapsed 246.383999825 got 500000
    __main__.PQueue on 500000 elapsed 30.1040000916 got 500000

    mixBench
    __main__.PQPython23 on 500000 elapsed 3.2650001049 got 250000
    __main__.PQ0 on 500000 elapsed 2.35299992561 got 250000
    __main__.PQueue on 500000 elapsed 3.32500004768 got 250000

    BENCHMARKS FOR 1000000

    insertBench
    __main__.PQPython23 on 1000000 elapsed 43.0320000648 got 1000000
    __main__.PQ0 on 1000000 elapsed 1376.39899993 got 1000000
    __main__.PQueue on 1000000 elapsed 67.2970001698 got 1000000

    mixBench
    __main__.PQPython23 on 1000000 elapsed 6.93000006676 got 500001
    __main__.PQ0 on 1000000 elapsed 4.8069999218 got 500001
    __main__.PQueue on 1000000 elapsed 6.82999992371 got 500001
    , Jan 26, 2005
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Der Andere
    Replies:
    6
    Views:
    623
    Dietmar Kuehl
    Jun 5, 2004
  2. Der Andere

    Still priority queues and STL ...

    Der Andere, Jun 4, 2004, in forum: C++
    Replies:
    1
    Views:
    380
    David Harmon
    Jun 4, 2004
  3. Delaney, Timothy C (Timothy)

    RE: On benchmarks, heaps, priority queues

    Delaney, Timothy C (Timothy), Jan 26, 2005, in forum: Python
    Replies:
    6
    Views:
    403
  4. Mason Kelsey
    Replies:
    7
    Views:
    378
    Josh Cheek
    Sep 21, 2009
  5. Mason Kelsey
    Replies:
    5
    Views:
    182
    John W Higgins
    Oct 2, 2009
Loading...

Share This Page