[erlang-questions] Mnesia sorting/limiting
Thu Jun 11 01:18:56 CEST 2009
On 10 Jun 2009, at 8:30 pm, Ola Andersson A wrote:
> I was surprised to discover that there is no priority queue
> implementation in OTP.
You will find an implementation of skew heaps in
It was on the first page of results from a Google search for
(priority queues Erlang).
According to that thread as stored at Nabble, the use of gb_trees
for priority queues was proposed by Ulf Wiger.
There is a paper "Optimal Purely Functional Priority Queues" by
Brodal and Okasaki at
which it might be interesting to translate into Erlang; that
paper uses ML, which is strict like Erlang, not lazy like Haskell.
However, I'd draw your attention to a sentence in that paper:
"Our data structure is reasonably ecient in practice;
however, there are several competing data structures that, although
not asymptotically optimal, are somewhat faster than ours in practice."
We had a visitor here for a month or two a couple of years ago who
was interested in priority queue algorithms. He was evalluating a
recent theoretically improved algorithm, and was quite pleased that
his implementation of it was _by actual measurement_ faster than
several other moderately recent contenders. I said "why aren't
you including the old heap-in-an-array data structure in your
benchmarks? I think you really OUGHT to include the old heap-in-
an-array data structure in your benchmarks!" So he did. And it
was about 10 times faster than the _theoretically_ better ones.
If all you need is new(), empty(), insert(), find_min(), and
remove_min(), something like skew heaps or perfectly balanced
heaps will probably be hard to beat. If you need fancier things
like O(1) meld(), then you will need something like the
Brodal/Okasaki data structure.
More information about the erlang-questions