Feedback request: priority queues in containers

[Louis Wasserman]

>
> I'm not sure about some of that. Imperative queues sometimes offer

O(1) decreaseKey and O(lg n) delete by storing pointers to elements in

a priority queue. The usual purely functional PQs can only offer O(n)

decreaseKey and O(n) delete. Purely functional PSQs can offer O(lg n)

decreaseKey and O(lg n) delete.


Minimum spanning tree is a common application for PQs that makes good

use of decreaseKey.

That example did occur to me, but I feel okay about following the examples
of Java and C++ STL, which offer priority queue implementations, but those
implementations don't support decreaseKey.

You might be able to convince me that we should offer PSQueues in addition
to PQueues, but I don't think they should be merged, for the following
reason.  Using the PSQueue package, which is essentially a copy of Ralf
Hinze's original implementation, yields the following benchmark for
heapsorting 25000 Ints:

Binomial:   0.000   3.240   2.180   4.000   8.001
PSQ:        8.001  13.241   2.882  12.001  24.002

I'm really not okay with that kind of performance loss for added
functionality that not everyone needs.

Louis Wasserman
wasserman.louis at gmail.com
http://profiles.google.com/wasserman.louis


On Tue, Mar 16, 2010 at 1:58 PM, Louis Wasserman
<wasserman.louis at gmail.com>wrote:

>
> Why not use Okasaki & Brodal's "Optimal Purely Functional Priority
>
> Queues"? They offer worst case:
>
>
> * O(1) union, findMin, and insert
>
> * O(lg n) deleteMin
>
> The primary reason that we don't use this implementation is, quoting from
> the paper you yourself linked to,
>
>> Our data structure is reasonably efficient in practice;
>> however, there are several competing data structures that, although
>> not asymptotically optimal, are somewhat faster than ours in practice.
>
> Hence, our work is primarily of theoretical interest.
>>
>
> The current implementation is considerably faster than Okasaki's
> implementation in practice, based on our benchmarks.  Furthermore, the
> asymptotics are really pretty good, and the constant factors appear to be
> relatively low.
>
> I wrote a pretty efficient skew binomial heap implementation -- the first
> step of Okasaki's approach -- and found it was already slower than the
> optimized binomial heap.  I'm not sure whether or not I uploaded that
> benchmark, though.  I'll do that at some point today, just to keep everyone
> happy.
>
> Louis Wasserman
> wasserman.louis at gmail.com
> http://profiles.google.com/wasserman.louis
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100316/59b3078e/attachment.html