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

[Thorkil Naur]

Hello Melissa,

On Tuesday 24 July 2007 19:09, Melissa O'Neill wrote:
> 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, 

Do you have detailed measurements that you wish to share? I would be most 
interested, I assure you.

> although its another   
> case where most readers would find a detailed explanation of the code  
> instructive.)

I'll do my very best to provide such an explanation within, say, the next 
couple of weeks.

> 
> > 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 

Thanks a lot and the best regards
Thorkil