|
Boost : |
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk