Sieve of Eratosthenes 的 Haskell/Scheme 實(shí)現(xiàn)

MMMIX

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

Haskell 實(shí)現(xiàn)如下:

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..]
   

復(fù)制代碼

加了平方優(yōu)化后的版本

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..]
   

復(fù)制代碼

實(shí)際上，第二個(gè)版本有嚴(yán)重的性能問(wèn)題(break 會(huì)導(dǎo)致大量的內(nèi)存操作)以至于還沒有第一個(gè)快。

真正優(yōu)化的版本(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 ]
   

復(fù)制代碼

BTW，這個(gè)還可以再稍加優(yōu)化。

[ 本帖最后由 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)))
    

復(fù)制代碼

> (list-ref primes 50)
233

MMMIX

我覺著 integers 的定義可以優(yōu)化下
PLT Scheme 實(shí)現(xiàn)(需要在 DrScheme 中將語(yǔ)言設(shè)為 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))))
    

復(fù)制代碼

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

復(fù)制代碼

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

win_hate

一個(gè)帶平方優(yōu)化的版本

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

復(fù)制代碼

win_hate

原帖由 MMMIX 于 2008-9-21 01:59 發(fā)表
我覺著 integers 的定義可以優(yōu)化下
PLT Scheme 實(shí)現(xiàn)

#lang lazy

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

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

說(shuō)得對(duì)，用奇數(shù)列相當(dāng)于在選材上先 filter 了一次。

那個(gè) #lang lazy 在 mzscheme 中好用嗎？我這里試了不行。

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

MMMIX

原帖由 win_hate 于 2008-9-21 10:17 發(fā)表
那個(gè) #lang lazy 在 mzscheme 中好用嗎？我這里試了不行。

mzscheme 不清楚(應(yīng)該也行)，我向來(lái)都是直接用 DrScheme 的
在 DrScheme 中應(yīng)該把語(yǔ)言設(shè)為 Module，然后通過(guò) #lang 選擇具體要用的語(yǔ)言，這也是推薦的作法。

win_hate

謝謝！


用模塊之后可以了，但對(duì)整個(gè)體系還是很模糊。要找個(gè)時(shí)間把 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))
    

復(fù)制代碼

MMMIX

原帖由 win_hate 于 2008-9-21 11:21 發(fā)表
謝謝！


用模塊之后可以了，但對(duì)整個(gè)體系還是很模糊。要找個(gè)時(shí)間把 PLT 的文檔好好看一看才行。

其實(shí)用 #lang 也是可以的，不過(guò)直接用 (list-ref primes 50) 是沒有輸出的，但是可以用 (display (list-ref primes 50)) 顯示結(jié)果。

win_hate

我不是很明白你的意思。

如果直接選 lazy scheme，是可以運(yùn)行的。我回的第一貼用的就是這個(gè)環(huán)境

如果把語(yǔ)言選為 module，則得到一條錯(cuò)誤。

可能我模塊那里沒寫對(duì)？

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

MMMIX

原帖由 win_hate 于 2008-9-21 17:44 發(fā)表


如果把語(yǔ)言選為 module，則得到一條錯(cuò)誤。

估計(jì)是版本的問(wèn)題，我看你用的還是 3.72, 我測(cè)試時(shí)用的是 4.1

collects/lazy/lang/reader.ss 這個(gè)文件在我這是有的，內(nèi)容很簡(jiǎn)單：

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

復(fù)制代碼

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