[Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was:
Genuine Eratosthenes sieve)
naur at post11.tele.dk
Tue Jul 24 19:42:23 EDT 2007
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
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,
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
Thanks a lot and the best regards
More information about the Haskell-Cafe