Subject: Re: [boost] [heap] A performance test and some questions
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2011-06-06 12:02:07
> I have now read (and tried to understand) the similar question from Andrew Sutton with respect to Dijkstra's SP:
> (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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk