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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Thanks a lot and the best regards Thorkil