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

Subject: Re: [boost] [heap] A performance test and some questions
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2011-06-06 12:24:11

> 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.

Indeed, I have to check this, if I want to use the interface where I can change the priority "manually". The issue here is that fibonacci_heap itself can no longer do this check, since the previous value is already gone when "update" is called. And it seems that this missing piece of information totally ruins the performance of fibonacci_heap. So if you want the convenience of "update" and don't care about performance, just use std::pair<priority_type, Vertex*> as value_type for the heap, and use the "normal" update function. This is still an order of magnitude faster than the performance that results from modifying the priority "manually" and just calling "update".

> Removing the update() method makes the user work harder. Increase and
> decrease are nice when you know that you can optimize.

It's not that I want to optimize something here, I want to avoid a totally unnecessary pessimization. Because the normal user won't be aware of the consequences of this tiny bit of missing information for the performance of fibonacci_heap.

Regards,
Thomas