無限ストリームを使って素数を求める処理に、「素数は必ず６の倍数の隣にある」という事実を使って、処理速度を改善してみます。なお、無限ストリームを使った解法は処理速度が遅いので、最速を求める人にはおすすめしません。
無限ストリームを実現するための基本的な手続き群から。無限ストリームをそのまま実装してしまうとコンピュータが応答無しになってしまうので、delay を使って遅延評価するようにします。評価するには force を使います。
(define nil '())
(define (square x) (* x x))
(define (divisible? x y) (= (remainder x y) 0))
; streams
(define the-empty-stream nil)
(define (stream-null? stream)
(null? stream))
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))
(define (cons-stream a b)
(cons a b))
(define (stream-filter pred stream)
(cond ((stream-null? stream) the-empty-stream)
((pred (stream-car stream))
(cons-stream (stream-car stream)
(delay (stream-filter pred (stream-cdr stream)))))
(else (stream-filter pred (stream-cdr stream)))))
(define (stream-ref s n)
(if (= n 0)
(stream-car s)
(stream-ref (stream-cdr s) (- n 1))))
(define (stream-map proc . argstreams)
(if (stream-null? (car argstreams))
the-empty-stream
(cons-stream
(apply proc (map stream-car argstreams))
(delay
(apply stream-map
(cons proc (map stream-cdr argstreams)))))))次は素数の無限ストリームの実装です。
integers-starting-from 手続きは n から始まる整数の無限ストリームを生成します。この手続きを使って primes を定義できます。
; infinite streams
(define (integers-starting-from n)
(cons-stream n (delay (integers-starting-from (+ n 1)))))
(define primes
(cons-stream
2
(delay (stream-filter prime? (integers-starting-from 3)))))
(define (prime? n)
(define (iter ps)
(cond ((> (square (stream-car ps)) n) #t)
((divisible? n (stream-car ps)) #f)
(else (iter (stream-cdr ps)))))
(if (> n 1) (iter primes) #f))
(define (make-primes limit)
(define (rec s)
(if (> (stream-car s) limit)
nil
(cons (stream-car s) (rec (stream-cdr s)))))
(rec primes))無限ストリームは、そのすべての要素を予め用意しているわけではなく、必要な時に必要な分だけを用意します。無限ストリームを使う手続きからすると、あたかも全ての要素が用意されているかのように振る舞います。
改良前の処理速度を測っておきます。
gosh> (time (make-primes 2000000)) ;(time (make-primes 2000000)) ; real 11.061 ; user 8.844 ; sys 1.781 (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 ....)
200万までの素数を求めるのに約 11 秒かかっています。
プログラムを改良する前に、「素数は必ず６の倍数の隣にある」のか確かめておきます。6 は 2 * 3 です。整数を 6 で割ったときの余りは 0, 1, 2, 3, 4, 5 の 6 パターンあります。
余り 0 ... 6 で割り切れるので素数ではない。 余り 1 ... 素数になる可能性がある。 余り 2 ... 2 で割り切れるので素数ではない。 余り 3 ... 3 で割り切れるので素数ではない。 余り 4 ... 2 で割り切れるので素数ではない。 余り 5 ... 素数になる可能性がある。
となります。
6n + 0 ... 6の倍数 6n + 1 ... 素数かも知れない 6n + 2 ... 2(3n + 1) ... 2の倍数 6n + 3 ... 3(2n + 1) ... 3の倍数 6n + 4 ... 2(3n + 2) ... 2の倍数 6n + 5 ... 素数かも知れない
と言い換えても良いです。同じ事を言っています。
つまり 6 の倍数の両隣、6n - 1 と 6n + 1 は素数になる可能性があります。注意点として、素数になる可能性があるだけで、必ず素数になるとは限りません。また、2 と 3 は該当しません。
改良して行きます。6n - 1 と 6n + 1 の無限ストリームを作る手続きを追加します。
かなり手抜きですが、n の初期値は必ず 6 にしてくださいｗ
(define (numbers-that-may-be-prime-numbers-starting-from n)
(cons-stream (- n 1)
(delay (cons-stream (+ n 1)
(delay (numbers-that-may-be-prime-numbers-starting-from (+ n 6)))))))primes は先程追加した numbers-that-may-be-prime-numbers-starting-from 手続きを使うように修正します。2 と 3 は例外扱いしますので、これも組み込みます。
(define primes
(cons-stream
2
(delay (cons-stream
3
(delay (stream-filter prime? (numbers-that-may-be-prime-numbers-starting-from 6)))))))以上です。処理時間を計測してみます。
gosh> (time (make-primes 2000000)) ;(time (make-primes 2000000)) ; real 6.496 ; user 5.781 ; sys 0.390 (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 ....)
200万までの素数を求めるのに約 6.5 秒かかっています。改良前よりは処理速度は短縮しているのがわかります。
ただし、無限ストリームを使用した素数を求める手続きの処理時間 O(n) ではないので注意です。400 万まで求める場合、処理時間は 2 倍にはならず、もっと時間がかかります。n が大きくなると処理時間も増加のしかたは大きくなっていきます。O(n^2) まではいかないですがかなり遅いです。
さらに、処理時間を正確に計測する場合は、処理系を一度終了するなどして、無限ストリームを捨てる必要があります。無限ストリームが一旦生成されると force した部分は再計算しないためです*1。
*1:これは無限ストリームを使う利点の一つです。
