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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe