Re: RE: [Caml-list] Priority queues, reloaded

Re: RE: [Caml-list] Priority queues, reloaded

[Radu Grigore]

On Sunday, July 10, 2011 6:55:57 PM UTC+1, Jon Harrop wrote:
> > In a real program, I'd probably go for binomial heaps if imperative is OK,
> FWIW, I found that Okasaki's binomial heaps are among the slowest.

Oops. I meant (imperative) *binary* heaps (the ones that stay in an array and don't need explicit pointers to parents/children to save memory---that's why I was mentioning space use).

It's not the first time I say binomial instead of binary ...

> Pairing
> heaps were the fastest overall, closely followed by leftist heaps in OCaml.
> If elements are inserted in order then the leftist heap is ~3x slower than a
> pairing heap in OCaml and ~5x slower in F#.

Good to know!

Another comparison appears in SGB, file miles_span.w, in the context of computing minimum spanning trees. It turns out that Fibonacci heaps are not only a theoretical curiosity!

RE: RE: [Caml-list] Priority queues, reloaded

[Jon Harrop]

Radu Grigore wrote:
> Another comparison appears in SGB, file miles_span.w, in the context of
> computing minimum spanning trees. It turns out that Fibonacci heaps are
not
> only a theoretical curiosity!

That's interesting. I was under the impression Fibonacci heaps had a really
bad constant prefactor.

If this is the right file:

  http://ftp.sunet.se/pub/text-processing/TeX/support/graphbase/miles_span.w

Then they say:

  "We will try out four basic algorithms that have received prominent
attention in the literature. Graham and Hell's Algorithm~1 is represented
by the |krusk| procedure, which uses Kruskal's algorithm after the
edges have been sorted by length with a radix sort. Their Algorithm~2
is represented by the |jar_pr| procedure, which incorporates a 
priority queue structure that we implement in two ways, either as
a simple binary heap or as a Fibonacci heap. And their Algorithm~3
is represented by the |cher_tar_kar| procedure, which implements a
method similar to Bor{\accent23u}vka's that was independently
discovered by Cheriton and Tarjan and later simplified by Karp and Tarjan. "

So they're only comparing binary and Fibonacci heaps (not skew, leftist,
pairing, binomial etc). Moreover, do you actually need a heap in the MST
algorithm? You cannot add the shortest edge first without traversing all
edges so you must consider all edges. I suppose a heap could win out over a
sort if the MST only requires a small proportion of all the edges, i.e.
finding the 1..k shortest edges, but I'm not sure how valuable that is in
practice.

Regardless, I'm sure the first step in optimizing such algorithms is to
sacrifice purity. :-)

Cheers,
Jon.