"ocaml_beginners"::[] min-heap algorithm

On Mon, 27 Nov 2006, drehman27 wrote:

> Thank you Brian and Remi.
>; I will be constructing min-heaps with an average size of 700 float
>; numbers. The operations I will be doing most are inserting an element
> and removing the min. I wonder if binomial heaps or fibonacci heaps
>; should be considered in this case.

Actually, in this case I'd strongly recommend leftist heaps (the code I
sent). The thing to remember is to watch those constant factors.
log2(700) < 10, so you're generally not going to go more than 9-10 levels
deep, and each level is relatively cheap. It's about as cheap as any
applicative data structure is going to be.

One of the things to know about imperitive (mutable) data structures in
Ocaml is that the Ocaml GC doesn't want objects in the major heap to have
references to the minor heap. This means that if you write a pointer to
an object in the minor heap into an object in the major heap, a minor
collection occurs. This can get very spendy, especially if objects that
normally wouldn't survive to get promoted to the major heap do because a
minor collection was kicked off too early- at which point collecting them
becomes more expensive. So for reasonably small data sets (and, from my
experience, 700 elements generally qualifies as "reasonably small";), O(log
N) cost purely applicative structures are often faster than O(1)
imperitive structures.

Note that you can do a purely applicative binomial heap (I have)- it just
winds up about as complicated as the leftist heap.

Brian

Messages in this topic (5) Reply (via web post) | Start a new topic

.

--- In ocaml_beginners%40yahoogroups.com">ocaml_beginnersyahoogroups.com, Brian Hurt <bhurt...> wrote:
&gt;
>
>
> On Mon, 27 Nov 2006, drehman27 wrote:
&gt;
> > Thank you Brian and Remi.
>; > I will be constructing min-heaps with an average size of 700 float
>; > numbers. The operations I will be doing most are inserting an element
&gt; > and removing the min. I wonder if binomial heaps or fibonacci heaps
>; > should be considered in this case.
>;
> Actually, in this case I'd strongly recommend leftist heaps (the code I
> sent). The thing to remember is to watch those constant factors.
> log2(700) < 10, so you're generally not going to go more than 9-10
levels
> deep, and each level is relatively cheap. It's about as cheap as any
> applicative data structure is going to be.
>
> One of the things to know about imperitive (mutable) data structures in
> Ocaml is that the Ocaml GC doesn't want objects in the major heap to
have
> references to the minor heap. This means that if you write a
pointer to
> an object in the minor heap into an object in the major heap, a minor
> collection occurs.

I am not following you here. I am not familiar with the workings of a
GC. Would you care to explain with an example please?

This can get very spendy, especially if objects that
> normally wouldn't survive to get promoted to the major heap do
because a
> minor collection was kicked off too early- at which point collecting
them
> becomes more expensive. So for reasonably small data sets (and,
from my
> experience, 700 elements generally qualifies as "reasonably small";),
O(log
> N) cost purely applicative structures are often faster than O(1)
> imperitive structures.
>

I will have to create thousands of heaps of size 700 sequentially, but
I will only need one at a time (because I will write them to disk and
the GC can reclaim space from each dumped heap).
Even in this situation do you still recommend purely applicative
structures?

Messages in this topic (6) Reply (via web post) | Start a new topic

.