> I wrote a pretty efficient skew binomial heap implementation -- the first
> step of Okasaki's approach -- and found it was already slower than the
> optimized binomial heap. I'm not sure whether or not I uploaded that
> benchmark, though. I'll do that at some point today, just to keep everyone
> happy.
The skew binomial heaps you implemented should only be asymptotically
faster than the usual binomial heaps on one special case: comparing a
binomial heap in a state that would case an \Omega(lg n) time cascade
on insert to the worst-case O(1) insert of binomial heaps.
I think it would also be worth comparing binomial heap merge against
Brodal-Okasaki heap merge.
Finally, if speed is the ultimate goal, I suspect the clever nested
type approach to guaranteeing binomial tree shape slows things down a
bit. For reference, the type in the latest patch is:
data BinomForest rk a = Nil
| Skip !(BinomForest (Succ rk) a)
| Cons {-# UNPACK #-} !(BinomTree rk a)
!(BinomForest (Succ rk) a)
data BinomTree rk a = BinomTree a (rk a)
data Succ rk a = Succ {-# UNPACK #-} !(BinomTree rk a) (rk a)
data Zero a = Zero
I suspect the following might be faster:
data BinomForest2 a = Empty
| NonEmpty a [BinomTree2 a]
data BinomTree2 a = BinomTree2 a [BinomTree2 a]
This eliminates the "Skip" constructor, which contributes only to the
nested type guarantee.
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
