[Haskell-cafe] Performance of functional priority queues
Luke Palmer
lrpalmer at gmail.com
Mon Jun 15 03:54:32 EDT 2009
On Sun, Jun 14, 2009 at 9:18 PM, Richard O'Keefe <ok at cs.otago.ac.nz> wrote:
> There's a current thread in the Erlang mailing list about
> priority queues. I'm aware of, for example, the Brodal/Okasaki
> paper and the David King paper. I'm also aware of James Cook's
> priority queue package in Hackage, have my own copy of Okasaki's
> book, and have just spent an hour searching the web.
>
> One of the correspondents in that thread claims that it is
> provably impossible to have an efficient priority queue implementation
> without mutability.
If he so claims, maybe you can challenge him by asking for a proof?
Such a proof would probably only involve asymptotics, since it's very hard
to *prove* anything when actual raw speed is involved. If that's the case,
you can use Okasaki to back yourself up (or back him up; I am not familiar
with the results in this area).
I've seen in a few programming circles now that "provably" is used as a
weasel word. Provably, eh? Where's the proof?
Luke
> I think he's cuckoo. But I'd like to have some
> numbers to back me up.
>
> Can anyone point me to some actual benchmark results comparing
> priority queue performance *with* mutation and priority queue
> performance *without* mutation, in the same functional or
> mostly-functional language?
>
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090615/19a88207/attachment.html
More information about the Haskell-Cafe
mailing list