Sieve of Eratosthenes 的 Haskell/Scheme 实现

MMMIX

Sieve of Eratosthenes 算法描述见 http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Haskell 实现如下:

1. 
   
2. sieve :: [Integer] -> [Integer]
   
3. sieve (x:xs) = x : sieve xs'
   
4.              where xs' = filter (\y -> y `mod` x /= 0) xs
   
5. 
   
6. primes = 2 : sieve [3,5..]
   

复制代码

加了平方优化后的版本

1. 
   
2. sieve :: [Integer] -> [Integer]
   
3. sieve (x:xs) = x : sieve (xs' ++ xs''')
   
4.              where
   
5.                 (xs', xs'') = break (>= x*x) xs
   
6.                 xs''' = filter (\y -> y `mod` x /= 0) xs''
   
7. 
   
8. primes = 2 : sieve [3,5..]
   

复制代码

实际上，第二个版本有严重的性能问题(break 会导致大量的内存操作)以至于还没有第一个快。

真正优化的版本(by win_hate):

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 ]
   

复制代码

BTW，这个还可以再稍加优化。

[ 本帖最后由 MMMIX 于 2009-5-20 14:15 编辑 ]

win_hate

lazy scheme

1. 
   
2. (define (integers n)
   
3.   (cons n (integers (+ n 1))))
   
4. 
   
5. (define (sieve seq)
   
6.   (let ((p (car seq)))
   
7.   (cons p (sieve
   
8.            (filter (lambda (x) (not (= 0 (modulo x p)))) (cdr seq))))))
   
9.            
   
10. (define primes (sieve (integers 2)))
    

复制代码

> (list-ref primes 50)
233

MMMIX

我觉着 integers 的定义可以优化下
PLT Scheme 实现(需要在 DrScheme 中将语言设为 Module)

1. 
   
2. #lang lazy
   
3. 
   
4. (define (integers n)
   
5.   (cons n (integers (+ n 2))))
   
6. 
   
7. (define (sieve seq)
   
8.   (let ((p (car seq)))
   
9.   (cons p (sieve
   
10.            (filter (lambda (x) (not (= 0 (modulo x p)))) (cdr seq))))))
    
11.            
    
12. (define primes (cons 2
    
13.                      (sieve (integers 3))))
    

复制代码

1. 
   
2. > (list-ref primes 50)
   
3. 233
   

复制代码

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

win_hate

一个带平方优化的版本

1. 
   
2. (define odd
   
3.   (letrec ((f (lambda (n)
   
4.              (cons n (f (+ n 2))))))
   
5.     (f 3)))
   
6. 
   
7. (define primes
   
8.   (cons 2 (filter primes? odd)))
   
9. 
   
10. (define (primes? n)
    
11.   (define (f ps)
    
12.     (let ((p (car ps)))
    
13.       (cond ((> (* p p) n) #t)
    
14.             ((= (modulo n p) 0) #f)
    
15.             (else (f (cdr ps))))))
    
16.   (f primes))
    

复制代码

win_hate

原帖由 MMMIX 于 2008-9-21 01:59 发表
我觉着 integers 的定义可以优化下
PLT Scheme 实现

#lang lazy

(define (integers n)
  (cons n (integers (+ n 2))))

(define (sieve seq)
  (let ((p (car seq)))
  (cons p (sieve
         ...

说得对，用奇数列相当于在选材上先 filter 了一次。

那个 #lang lazy 在 mzscheme 中好用吗？我这里试了不行。

[ 本帖最后由 win_hate 于 2008-9-21 10:34 编辑 ]

MMMIX

原帖由 win_hate 于 2008-9-21 10:17 发表
那个 #lang lazy 在 mzscheme 中好用吗？我这里试了不行。

mzscheme 不清楚(应该也行)，我向来都是直接用 DrScheme 的
在 DrScheme 中应该把语言设为 Module，然后通过 #lang 选择具体要用的语言，这也是推荐的作法。

win_hate

谢谢！


用模块之后可以了，但对整个体系还是很模糊。要找个时间把 PLT 的文档好好看一看才行。

1. 
   
2. (module nth (lib "lazy.ss" "lazy")
   
3.   
   
4.   (define odd
   
5.     (letrec ((f (lambda (n)
   
6.                   (cons n (f (+ n 2))))))
   
7.       (f 3)))
   
8.   
   
9.   (define primes
   
10.     (cons 2 (filter primes? odd)))
    
11.   
    
12.   (define (primes? n)
    
13.     (define (f ps)
    
14.       (let ((p (car ps)))
    
15.         (cond ((> (* p p) n) #t)
    
16.               ((= (modulo n p) 0) #f)
    
17.               (else (f (cdr ps))))))
    
18.     (f primes))
    
19.   
    
20.   (define (nth-prime n)
    
21.     (! (list-ref primes n)))
    
22.   
    
23.   (provide nth-prime))
    

复制代码

MMMIX

原帖由 win_hate 于 2008-9-21 11:21 发表
谢谢！


用模块之后可以了，但对整个体系还是很模糊。要找个时间把 PLT 的文档好好看一看才行。

其实用 #lang 也是可以的，不过直接用 (list-ref primes 50) 是没有输出的，但是可以用 (display (list-ref primes 50)) 显示结果。

win_hate

我不是很明白你的意思。

如果直接选 lazy scheme，是可以运行的。我回的第一贴用的就是这个环境

如果把语言选为 module，则得到一条错误。

可能我模块那里没写对？

[ 本帖最后由 win_hate 于 2008-9-21 17:49 编辑 ]

MMMIX

原帖由 win_hate 于 2008-9-21 17:44 发表


如果把语言选为 module，则得到一条错误。

估计是版本的问题，我看你用的还是 3.72, 我测试时用的是 4.1

collects/lazy/lang/reader.ss 这个文件在我这是有的，内容很简单：

1. 
   
2. (module reader syntax/module-reader
   
3.   lazy)
   

复制代码

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