[boost] Priority Queues (was:config.h[pp])

From: Dietmar Kuehl (dietmar.kuehl_at_[hidden])
Date: 1999-07-15 20:11:51

Hi,
At 14:40 15.07.99 -0700, Reid Sweatman wrote:
>Anyway, on a totally different tack, had you considered combining a hash
>lookup with one of your DPQ classes?

You mean to avoid the need to keep a reference to the objects in the
priority queue if you want to change arbitrary elements? Well, no.
My own application are combinatorial algorithms like eg. Dijkstra's
algorithm for shortest path and the Preflow-Push for maximum flows.
There I can easily store the reference and eg. for Dijkstra's algorithm
you have a lot of decrease operations (well, depends on the density of
the graph and the edge weights...).

Maybe it would be reasonable to use a wrapper to the actual priority
queue which uses a hash for the references...? I'm not sure whether it
would safe anything if the hash bundled directly with the priority queue.
Well, thinking of it, for d-heaps it could be possible to avoid the
two level storage.

>In games, you quite often need a cache manager that accesses
>things much more frequently than it changes their priorities.  In a case
>like that, it's often much faster (with careful size tweaking after doing
>some profiling) to do the lookups via hash, and the priority changes via the
>tree.  Actually, you could speed things a bit more by hashing to find a node
>to change priorities on, and use the tree only when popping from the queue,
>thus substituting an amortized constant cost for a logarithmic one much of
>the time.

I can't follow you here... Can you give me an example of what kind of use
you are making of a priority queue? What has a cache manager to do with
priorities...? Hm, apparently I should have a look into game programming
some time.

>I'd also like to ask if you ever considered using splay trees?  Too much
>restructuring overhead?  I'm not sure, but it might actually have lower
>overhead, because while it tends to move more things around, it has slightly
>more efficient operations to do so.  Most other trees use a sort of bubble
>sort to restore the heap invariant.  I guess there might be a break point in
>N where one became more efficient than the other.  Anyway, I digress into
>rambling mode (I'm a ramblin' guy... <g>).

Yes, I considered splay trees and I'm still planning to implement a priority
queue on the basis of splay trees but over the last week I just tried to
get the stuff off my desk since I have other work to do. Currently I would
submit the complete library (including documentation :-) but I'm waiting
for the result of the poll: Probably I have to change a bunch of headers
and some files to use the extensions .hpp rather than .h as I'm currently
doing... Another thing which made me hesitate to use splay trees as the
basis of a priority queue was the idea of creating a proper tree abstraction
and use a general splay tree as priority queue. On the other hand, I think
the splay tree would be just a general splay tree anyway to which the
interface of priority queue is added.

>Oh, is the copy you e-mailed me still your latest, or have you posted a
>newer one somewhere.  At this point I'm pretty sure I'll either use your
>f_heap template as is, or write one based on it that's more focused on my
>particular application statistics.

I think I have a completely rewritten and improved version.... Also, I
have added a "lazy Fibonacci heap" which provides better performance in
certain situations. Well, I want to submit the stuff tomorrow and put it
up on the site of the company I'm working for.

>Hmmmn.  I guess there's one other thing that had occurred to me, too.  In
>the f_heap template you store the data in the nodes, but in the d_heap you
>use the tree for lookup into a container class, list.

Well, the problem is that d-heaps are fully balanced trees which are easily
maintained as an array with index calculations. However, if you move objects
around in an array, you can't hand out a reference to the user which is later
used to access the element again because it was possibly moved. Thus, I'm
using an array for the heap manipulations and an external container, the
list, to maintain an entry point for the reference handed out. This is not
necessary for Fibonacci heaps because these are node based anyway. Actually,
it would be close to impossible to represent a Fibonacci heap using an array
of object just moving them into appropriate locations: You need some kind
of pointer or index to maintain Fibonacci heaps.

I thought about implementing d-heap using a fully balanced binary tree and
some trickery to find the proper insertion position. However, I haven't come
around to implement this yet. However, I guess that that it would be slower
because there are more pointer manipulations to bubble a node aroundthan
there are now.

>It occurred to me
>(while trying to solve the cache manager problem I mentioned, and with a
>mental nudge from Andy Glew--thanks, Andy-- that you could also use the SGI
>STL hash_map class as the base container and combine hashing with d_heap's
>that way.  Of course, the tree restructuring would be a tad messier than for
>f_heaps.

I streamlined those for the current implementation: Basically, instead of
storing the children in a doubly linked list, I'm not storing them in an
array which results normally in less operations. Only if the the array
has to be resized (using a 'std::vector' I don't care manually about these)
this could be slower. At least, I measure a significant improvement (but
using only random data...).

>I guess the real objection you'd have would be that hash_map isn't
>part of the C++ standard.

SGI's hash map is publically available. I'm not opposed to using this at
all. What I'm opposed to is to support inferior compilers, that is systems
providing less not more functionality. However, I'm not clear at all what
you want to do with the hash map. Maybe you can describe the problem to
me (probably not on the list) and I can try to figure out a way how to
solve it.

>Anyway, I've
>taken too much of your time already (all too easy to do when you type 90
>wpm--I trained as a concert pianist <g>).

Now I understand why I couldn't follow you: Maybe you should type slower
next time because I have trouble reading that fast :-) However, although
I have no clue on how many characters I type per minute, it is sufficient
fast that my brain is the limiting facet, at least when coding. It would be
good to be able to type faster when doing prose...

dk

------------------------------------------------------------------------

eGroups.com home: http://www.egroups.com/group/boost
http://www.egroups.com - Simplifying group communications