2007/7/15, Hugh Perkins <[EMAIL PROTECTED]>:
There's really a tendency in this newsgroup to point people to huge
documents, when a small copy and paste would make the answer so much more
accessible ;-)
I was pointing you on a document of quite honest size in my opinion,
and not really hard to read...
But well if you want a piece of code, here it is :
--
merge xs@(x:xt) ys@(y:yt) = case compare x y of
LT -> x : (merge xt ys)
EQ -> x : (merge xt yt)
GT -> y : (merge xs yt)
diff xs@(x:xt) ys@(y:yt) = case compare x y of
LT -> x : (diff xt ys)
EQ -> diff xt yt
GT -> diff xs yt
primes, nonprimes :: [Int]
primes = [2,3,5] ++ (diff [7,9..] nonprimes)
nonprimes = foldr1 f . map g $ tail primes
where f (x:xt) ys = x : (merge xt ys)
g p = [ n*p | n <- [p,p+2..]]
--
The HaskellWiki repertory it under "primes" and it's at least 170
times faster than the extra-naive sieve you used in your comparison on
my computer... (I have some doubts on the accuracy of the benchmark
and System.Time at this level of precision, especially on Windows)
An implementation with DiffArray (not even DiffUArray since there's no
instance for Bool ? Is there a bitvector implementation somewhere to
make up for this ?) and exactly your algorithm is already more than 20
times faster than the naive sieve.
Note that this kind of benchmark is pretty pointless anyway since
you're not really using C# in your program : you're using a subset of
C# that's almost immediately translatable in the corresponding C code,
and indeed the JIT compiler must compile to the same code as the
equivalent C code, so it's no surprise at all that the performances
are similar !
Due to the nature of Haskell, it's not so easy to do the same thing
(write a C program in Haskell as you wrote a C program in C#), so the
conclusion is obviously to Haskell disadvantage.
--
Jedaï
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
