Sieve of Eratosthenes 的 Haskell/Scheme 实现

Question

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

Haskell 实现如下:

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

复制代码

加了平方优化后的版本

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''
8. primes = 2 : sieve [3,5..]

复制代码

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

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

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
8. primes = 2 : [ p | p <- [3,5..], isPrime p primes ]

复制代码

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

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

Answer 1

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

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

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

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

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

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

Answer 2

我不是很明白你的意思。

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

drs01.png (30.2 KB, 下载次数: 28)

下载附件

2008-09-21 17:48 上传

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

drs02.png (33.41 KB, 下载次数: 26)

下载附件

2008-09-21 17:44 上传

可能我模块那里没写对？

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

Answer 3

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

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

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

Answer 4

谢谢！

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

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))

复制代码

Answer 5

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

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

Answer 6

原帖由 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 编辑 ]

Answer 7

一个带平方优化的版本

2. (define odd
3.   (letrec ((f (lambda (n)
4.              (cons n (f (+ n 2))))))
5.     (f 3)))
7. (define primes
8.   (cons 2 (filter primes? odd)))
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))

复制代码

Answer 8

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

2. #lang lazy
4. (define (integers n)
5.   (cons n (integers (+ n 2))))
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))))

复制代码

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

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

Answer 9

lazy scheme

2. (define (integers n)
3.   (cons n (integers (+ n 1))))
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