[boost] Re: Dietmar Kuehl

From: Brian Parker (brianjparker_at_[hidden])
Date: 2002-05-25 00:21:44

Hi Dietmar,

You may be interested to know that I have used your priority queues (esp.
the Fibonacci heap) extensively on several huge data sets and I hope that
they are eventually fully adopted into Boost as they are essential data
structures.

(See Parker, B. Magarey, J. "Three-dimensional Video Segmentation Using a
Variational Method". IEEE International Conference on Image Processing 2001
(ICIP 2001) for a description of the main algorithm I am using it in).

I have previously posted some bug fixes and minor interface changes to the
Fibonacci heap in the files section- see
"priority_queues_new_interface.zip".

The changes I made to the interface include some of the changes being
discussed here, including an allocator interface, and a constant time meld
operation (the allocator interface in fact optionally allows two allocators
to be specified- one for the fixed-sized nodes and another for the non-fixed
size allocations).

In my experience, in a (near) real-time video application using a hinted
fixed-size allocator (such as the one in the file "bjp_utilities*.zip" in
the files section) gave a significant speedup of around 20-30% and
significantly reduced the memory requirements (In the near future, I will
compare the speed of the Boost fast_pool_allocator with my hinted fixed size
allocators and post the results here).

Based on the requirements of my algorithm, I also made some changes to the
iterators so that they can be fully dereferenced (I also changed the name of
your "pointer" to "trivial_iterator" as per the SGI concept documentation,
but a better name may be found) , and I adjusted the template arguments so
the Fibonacci heap can be used to both order individual elements or elements
with associated data.

There are several other small interface changes documented in the html file.

Unfortunately, I found  that the other priority queues crashed on very large
data sets with repeated elements, and I have yet to fully debug them.

Anyway, I hope that anyone working further on your classes will find my
posted code changes of some use (BTW, the posted version was compiled using
Intel C++ 5- I have since built the code with both GCC and Intel C++ 6 which
required, IIRC, some minor changes, so I will upload the latest version in
the next few days).

Cheers,
Brian Parker
(brianjparker_at_[hidden])