apfelmus wrote:
After some pondering, the List a data structure for merging is
really
ingenious! :) Here's a try to explain how it works:
Thanks apfelmus! A detailed explanation of this code is really
helpful for anyone trying to understand what is going on. The VIP/
Crowd analogy is also very nice.
I think that this approach has the potential to outperform O'Neill's
(old?) code because it doesn't incorporates another prime number to
the
sieve mechanism until it really has to. I mean the following: in the
1st, 2nd, 3rd, 4th, ... step,
O'Neill's code adds the multiples
2*2, 3*3, 5*5, 7*7, ...
to the priority queue and uses them to sieve for potential prime
numbers
from then on.
Yeah, that's (only) what the code in my paper does -- it's good
enough for explicative purposes, but all recent versions have used a
slightly augmented priority queue. It's a priority queue coupled
with a "feeder list" that provides entries to add to the queue (in
increasing order). They are only admitted to the heap data structure
only once when the root of the heap "gets there".
The two most important bits are:
type HybridQ k v = (PriorityQ k v, [(k,v)])
-- postRemoveHQ is called when the min element of the heap
has changed
postRemoveHQ :: Ord k => HybridQ k v -> HybridQ k v
postRemoveHQ mq@(pq, []) = mq
postRemoveHQ mq@(pq, (qk,qv) : qs)
| qk < minKeyPQ pq = (insertPQ qk qv pq, qs)
| otherwise = mq
(See ONeillPrimes.hs in http://www.cs.hmc.edu/~oneill/code/haskell-
primes.zip for the complete code. I've also added Thorkil Naur's
code from March, which is also a good performer, although its another
case where most readers would find a detailed explanation of the code
instructive.)
the approach here adds 5*5=25 to the heap only after considering
the 9th prime 23.
Yep, that's what mine does too.
Best Regards,
Melissa.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
