[Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was:
Genuine Eratosthenes sieve)
oneill at cs.hmc.edu
Tue Jul 24 13:09:25 EDT 2007
> After some pondering, the List a data structure for merging is
> 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
> 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
> 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
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
> the approach here adds 5*5=25 to the heap only after considering
> the 9th prime 23.
Yep, that's what mine does too.
More information about the Haskell-Cafe