6 ms·
It bugs me a bit that the example code is brute force trial division instead of a true prime sieve. Sure, it highlights lazyness but the algorithm is less effic
by ufo 12y ago
It bugs me a bit that the example code is brute force trial division instead of a true prime sieve. Sure, it highlights lazyness but the algorithm is less efficient.
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
- deleted 12y ago[deleted]
- bignaj 12y agoIf you ever wanted to know what a typical Haskell programmer sounds like, ^^this is it to a T.
- judk 12y agoNo, typical Haskell programmers avoid talking about performance issues, because those highlight how awkward it is to write high- performance code.
- ibotty 12y agothat's just nonsense. there are many people very concerned about performance. i guess you are right that some do not care about constant factors, but i am very sure most do care about algorithmic complexity. and thinking about it, that's the approach you should use for anything where every last bit of performance is not utterly needed.
- codygman 12y agoI'm a Haskell programmer and I care about performance. So do many others, which is why you continue to see things like Conduit and more recently Haxl.
- throwaway_yy2Di 12y agoWell it's the haskell.org landing page, of course they're showing off the type of code that Haskell is good at. In your link, the purely functional version (15 lines around a priority queue) is more complicated than a naive version with a mutable array, so why would they advertise it?
- tel 12y agoI personally think the priority queue one is somewhat simpler than a fixed array algorithm. It also produces an infinite list of primes (or generator) instead of the primes up to a particular number. This is especially important in Haskell. I'd love to see it as it shows off some great data structures available in the libraries (like priority queues) but it's getting longish. The mutable array version is basically the same as imperative code everywhere sieveUA :: Int -> UArray Int Bool sieveUA top = runSTUArray $ do let m = (top-1) `div` 2 r = floor . sqrt $ fromIntegral top + 1 sieve <- newArray (1,m) True forM_ [1..r `div` 2] $ \i -> do isPrime <- readArray sieve i when isPrime $ do forM_ [2*i*(i+1), 2*i*(i+2)+1..m] $ \j -> do writeArray sieve j False return sieve It's a bit noisy syntactically and doesn't show off as much interesting stuff.
- ufo 12y agoMy pet peeve is mainly the function name. It says the algorithm is a prime sieve when it isn't and it spreads a common misconception :)