Feedback request: priority queues in containers
jbapple+haskell-lib at gmail.com
Wed Mar 17 04:27:23 EDT 2010
> I encourage you to test it
> out for yourself, but I think you'll find similar results. =D
I don't spend a lot of time thinking about non-asymptotic
optimizations, so I may have made an error or ten, but I found vastly
different results for heap sort.
I tested heap sorting mostly following the description of your example:
1. Generate 25,000 random Ints
3. Start timer
4. Insert Ints into PQ
5. Remove one at a time until there are none left
6. Print the last one removed
7. Stop timer
I compiled with GHC 6.10.1 and -O2.
I tested four implementations of binomial PQs:
A: Brodal-Okasaki binomial PQs, modified for O(1) findMin (the first
implementation in the paper I linked, transcribed by me by hand). This
file contains no strictness or unpacking annotations or optimizations.
B: Wasserman PQs, using your unpacking but writing the functions
myself (just so I could make a small file that I could be sure I
mostly understood). This is clearly different from D, your proposal,
but I think it uses the same algorithms (not functions) and the same
data structures (down to unpacking and strictness).
C: Simple binomial queues without the O(1) findMin modification, as
written by you in the last attachment on 3909. This implementation
uses some unpacking and strictness annotations, and uses a different
deleteMin algorithm than Brodal & Okasaki use. You called this
implementation "sparse" to distinguish it from your nested types
D: Wasserman PQs, using your latest proposed patch from ticket 3909.
Binomial priority queue timings (in milliseconds, averaged over 20 runs)
A: Simple Brodal-Okasaki list implementation:
B: Wasserman nested type implementation, simple functions:
C: Wasserman's 'Quick' list implementation:
D: Wasserman's proposed nested type implementation:
D is still the fastest. However, A is a good bit faster than B. Is it
possible that C would show a similar advantage over D if it were
optimized as carefully as D?
Also, why do my benchmarks show only slight differences between the
implementations when yours show massive ones?
It is possible I am making a noob benchmarking error. Attached is a
zip file that should contain everything necessary to replicate my
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 12253 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/libraries/attachments/20100317/3b3e328b/HeapSortTest.zip
More information about the Libraries