Boost logo

Boost :

Subject: Re: [boost] [heap] A performance test and some questions
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-07 04:29:47


> > I have now read (and tried to understand) the similar question from
> > Andrew Sutton with respect to Dijkstra's SP:
> > <http://lists.boost.org/Archives/boost/2011/06/182381.php>
> >
> > (On a slightly unrelated note, I first also used his way to call
> > "update", but that totally killed the performance (and compare count) of
> > fibonacci_heap. I would suggest to remove this form of "update" at least
> > from fibonacci_heap, and require calling "increase" or "decrease" when
> > you have modified the priority "manually".)
>
> That's only a viable solution if you have some a priori knowledge
> about which "direction" the value has changed with respect to the
> comparison operator. If you have an expression like this:
>
> x' = x + y;
>
> where x is the previous key and x' the new key--a possible
> implementation of edge relaxation. You still have to compare x and x'
> to determine which direction the change was in. Minimally, you'd have
> to check y to determine if it was less than 0, assuming the types of
> x, x', and y are numeric.
>
> Removing the update() method makes the user work harder. Increase and
> decrease are nice when you know that you can optimize.

btw, the fibonacci heap also provides an update_lazy with slightly different
performance characteristics than update(), since it does not run a consolidation
phase ... it mainly gives a better throughput at the costs of a worse worst-case
performance ...

tim




Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk