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 11:15:02

Tim Blechmann wrote:
> Thomas Klimpel wrote:
> > I guess the problem here is that I found no way around using
> > "std::pair<value_type, value_type*>" as value_type for the heap,
> > because I need to know the position in the bulk of the point with
> > the smallest arrival time. But Dijkstra algorithm should be no
> > different, I have to know the vertex in the graph with the shortest path.
> 
> you mean std::pair<value_type, handle_type> in order to store the
> handle inside? this may be a hole in the API. at the moment it is
> possible to convert an iterator to a handle (s_handle_from_iterator),
> so possibly i should add an
> handle_type s_handle_from_reference(reference); to all mutable heaps
> ...

Oh, you probably assume too much ingenuity from my part. Perhaps it becomes clearer when I use typedefs:

typedef value_type* bulk_ptr_type;
typedef std::pair<value_type, bulk_ptr_type> heap_value_type;

If I store the index into the (arrival time) bulk instead of the pointer, it would read

typedef std::size_t bulk_index_type;
typedef std::pair<value_type, bulk_index_type> heap_value_type;

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

If I write his approach with typedefs, it would read for my case

typedef value_type* bulk_ptr_type;
typedef bulk_ptr_type heap_value_type;

The other difference is that he stores the returned "handle_type" in a Map, while I store it in a separate bulk (which I called m_tBackpointer) of the same size as the (arrival time) bulk. (A similar bulk is implicitly also present when using TStaticHeap, but it is a part of the heap itself.) So Andrew Sutton's approach to use the mutable interface is not too different from mine, but will probably lead to even worse performance (because a "map" lookup seems to be worse than a "bulk" lookup).

On the one hand, your proposed mutable interface seems to be quite "natural" for node based heaps. On the other hand, it looks like there is one more indirection than for a "straightforward" implementation of a "mutable" binary heap, where the heap "knows" the maximum number of different items that it has to manage.

> reproduced and fixed the issue with the fibonacci heap ...

Nice.

Regards,
Thomas