Re: [boost] [heap] A performance test and some questions

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