Bearing in mind that I haven't looked at this in several years...
Why did you switch from queuelike to pqueue?
Because I liked the API better?
Could you put the code up somewhere manageable (repo)?
I had it up on darcs, but since that's not there any more, I don't have any more source history than you do.
Is it possible to make pqueue a full pSqueue implementation? Not without rewriting the API and data structure...or, equivalently, just starting from scratch.
Louis Wasserman
wasserman.louis@gmail.com
http://profiles.google.com/wasserman.louis
On Thu, Mar 28, 2013 at 10:20 PM, Niklas Hambüchen
(This is a slightly detailed email. If you are the maintainer of one of the packages benchmarked here, you might want to read it though.)
Today I was looking for a Priority Queue that also allows a delete operation (some call this a "Priority Search Queue").
I found
http://stackoverflow.com/questions/6976559/comparison-of-priority-queue-impl... and after looking at the 10 queue alternatives, I got to the following conclusions:
* Only 3 of them allow to delete entries (are p*s*queues) * Most of them are outdated or at least unmaintained for the last 3-5 years * There was an effort to get a priority queue into containers (see the stackoverflow link), but it was not agreed on * Those efforts were driven by Louis Wasserman, who wrote one of the 3 psqueues (queuelike), but now only maintains a non-ps-queue (pqueue) that seems to be the most popular priority queue implementation
PSQueue implementations -----------------------
The three packages that are psqueues are:
- PSQueue (http://hackage.haskell.org/package/PSQueue-1.1) * original implementation from paper of Ralf Hinze * last upload 2008 * no test suite (but small commented out QC properties), no benchmarks * no code repository
- fingertree-psqueue (http://hackage.haskell.org/package/fingertree-psqueue-0.3) * last upload 2011 * no tests, no benchmarks * no code repository
- queuelike (http://hackage.haskell.org/package/queuelike-1.0.9) * last upload 2009 * no tests, no benchmarks * no code repository
Benchmarks ----------
Unfortunately, none of them had tests, code in repositories or any indication about their real-world performance, so I made some criterion benchmarks. You can find them here:
https://github.com/nh2/psqueue-benchmarks Graphs:
http://htmlpreview.github.com/?https://raw.github.com/nh2/psqueue-benchmarks...
Benchmark results -----------------
* PSQueue throws a stack space overflow if you try to put in 100000 Ints
* PSQueue suffers from some significant worst case in terms of queue creation, sometimes creating a queue from random numbers just takes 5 times longer (1st graph). This only happens sometimes (despite Criterion)
* queuelike creation is instant - it seems to work around my benchmark somehow
* converting a queuelike queue to a list surprisingly takes 10 times longer than with the other packages
* in terms of average performance, the three are quite close to each other (apart from the point above). queuelike seems fastest, fingertree-psqueue is second and PSQueue slowest, with a difference of +30% to the next one
My questions to the maintainers -------------------------------
@Scott: Do you have an idea why PSQueue stack overflows?
@Louis: Why did you switch from queuelike to pqueue? Could you put the code up somewhere manageable (repo)? Is it possible to make pqueue a full pSqueue implementation?
Niklas