Sieve of Eratosthenes 的 Haskell/Scheme 实现

win_hate

有点明白了

按我对第二段代码的理解，设当前素数为 p，你把后面的数分成前后两段。只用 p 来筛后段，而前段让 p 之前的素数来筛。

但是你分段的时候，是通过计算平方来判断的，这与直接拿 p 来模相比，效率不会有明显改进。而且，用 p 来模可以去掉一些合数，计算平方并不能去掉合数，仅仅是把淘汰的工作留给 p 之前的素数了。基于这些分析，第二段代码性能可能不如第一段。

MMMIX

原帖由 win_hate 于 2008-9-24 20:47 发表

按我对第二段代码的理解，设当前素数为 p，你把后面的数分成前后两段。只用 p 来筛后段，而前段让 p 之前的素数来筛。

没错，前半段是由 p 之前的素数来筛的。

但是你分段的时候，是通过计算平方来判断的，这与直接拿 p 来模相比，效率不会有明显改进。而且，用 p 来模可以去掉一些合数，计算平方并不能去掉合数，仅仅是把淘汰的工作留给 p 之前的素数了。基于这些分析，第二段代码性能可能不如第一段。

分段之后，一些取模运算可以变为比较，运算量应该会小些。

我观察到的变慢的情况主要是大量内存操作引起的，实际上，profile 数据显示，80% 甚至更多的时间都是在做垃圾回收(GC).

真正优化后的版本应该是:

1. 
   
2. sieve :: [Integer] -> [Integer]
   
3. sieve (x:xs) = x : sieve xs'
   
4.              where
   
5.                 xs' = filter isPrime xs
   
6.                 isPrime y
   
7.                     | y < x*x           = True
   
8.                     | y `mod` x /= 0    = True
   
9.                     | otherwise         = False
   
10. 
    
11. primes = 2 : sieve [3,5..]
    

复制代码

这是执行结果(编译时使用 -O2 优化选项)

lee@debian:~/tmp/sieve$ time ./sieve0 10000    －－ 未加平方优化的版本
104743

real        0m26.741s
user        0m26.698s
sys        0m0.024s
lee@debian:~/tmp/sieve$ time ./sieve3 10000    －－ 上述加了平方优化的版本
104743

real        0m19.842s
user        0m19.733s
sys        0m0.020s

[ 本帖最后由 MMMIX 于 2008-9-24 21:48 编辑 ]

win_hate

我说的平方优化和你的还不大一样，学着用 Haskell 写了一个(逻辑上跟我前面的 scheme 是一致的)。

1. 
   
2. isprime :: Integer->[Integer]->Bool
   
3. isprime n (x:xs) | x*x > n = True
   
4.                  | n `mod` x == 0 = False
   
5.                  | otherwise = isprime n xs
   
6.                               
   
7. 
   
8. primes = 2: filter (\x->isprime x primes) [3..]
   

复制代码

[ 本帖最后由 win_hate 于 2008-9-24 22:46 编辑 ]

flw

在我机器上 win_hate 这个版本比前面 MMMIX 那个在计算 10000 时快两个数量级。

1. flw@debian:~/study$ ghc --make -O2 3mix_2.hs
   
2. flw@debian:~/study$ time ./3mix_2 10000
   
3. 104743
   
4. 
   
5. real    0m4.027s
   
6. user    0m3.728s
   
7. sys     0m0.052s
   
8. flw@debian:~/study$ ghc --make -O2 win_hate.hs
   
9. flw@debian:~/study$ time ./win_hate 10000
   
10. 104743
    
11. 
    
12. real    0m0.103s
    
13. user    0m0.092s
    
14. sys     0m0.008s
    
15. flw@debian:~/study$

复制代码

[ 本帖最后由 flw 于 2008-9-25 09:20 编辑 ]

MMMIX

原帖由 win_hate 于 2008-9-24 22:44 发表
我说的平方优化和你的还不大一样，学着用 Haskell 写了一个(逻辑上跟我前面的 scheme 是一致的)。

明白了，这个确实可以提前过滤掉许多数字。

MMMIX

原帖由 flw 于 2008-9-25 09:18 发表
在我机器上 win_hate 这个版本比前面 MMMIX 那个在计算 10000 时快两个数量级。

嗯，我那个实现在数字增大的时候性能会急剧下降，占用的内存太多了。

MMMIX

原帖由 win_hate 于 2008-9-24 22:44 发表
我说的平方优化和你的还不大一样，学着用 Haskell 写了一个(逻辑上跟我前面的 scheme 是一致的)。

帮你润饰下

1. 
   
2. isPrime :: Integer -> [Integer] -> Bool
   
3. isPrime p (x:xs)
   
4.     | x*x > p           = True
   
5.     | p `mod` x == 0    = False
   
6.     | otherwise         = isPrime p xs
   
7. 
   
8. primes = 2 : [ p | p <- [3,5..], isPrime p primes ]
   

复制代码

win_hate

恩， list comprehension 的确是很漂亮的表达方式。

MMMIX

HackageDB 上前不久上传了一个叫做 primes 的 package, 下面是其描述：

primes: Efficient, purely functional generation of prime numbers
This Haskell library provides an efficient lazy wheel sieve for prime generation inspired by Lazy wheel sieves and spirals of primes by Colin Runciman and The Genuine Sieve of Eratosthenes by Melissa O'Neil.

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/primes