[Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)

[Melissa O'Neill]

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.