Hatena::Groupcadr

kozima の日記

2009-01-02

エラトステネスの篩

| 21:33

有名なエラトステネスの篩を CL で作ったことがないことに気がついたので、作りました。loop の練習っぽいコード。

(defun sieve (n)
  (let ((bs (make-array n :element-type 'bit)))
    (loop for i from 2 below n
      if (zerop (aref bs i)) collect i
      and do (loop for j from i below n by i do
               (setf (aref bs j) 1)))))

せっかくなので素朴なやり方で列挙するものと速度を比較してみる。

(defun naive-primes (n)
  (loop with d = #(2 4)
    for i = 0 then (- 1 i)
    and p = 5 then (+ p (svref d i))
    while (>= n p)
    if (loop for q in ps until (< p (* q q)) never (zerop (mod p q)))
    collect p into ps
    finally (return (list* 2 3 ps))))

(defun test (n)
  (format t "~%n = ~A..." n)
  (time (naive-primes n))
  (time (sieve n))
  (terpri))

(loop for i from 3 to 6 do (test (expt 10 i)))

結果。ちゃんと線形時間になってます。ナイーブなほうは O(n\sqrt n) ぐらいなんでしょうか。

n = 1000...
Real time: 0.015625 sec.
Run time: 0.015625 sec.
Space: 1344 Bytes
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 1480 Bytes

n = 10000...
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 9832 Bytes
Real time: 0.015625 sec.
Run time: 0.015625 sec.
Space: 11092 Bytes

n = 100000...
Real time: 0.265625 sec.
Run time: 0.265625 sec.
Space: 76736 Bytes
Real time: 0.125 sec.
Run time: 0.125 sec.
Space: 89244 Bytes

n = 1000000...
Real time: 5.328125 sec.
Run time: 5.328125 sec.
Space: 627984 Bytes
GC: 1, GC time: 0.015625 sec.
Real time: 1.125 sec.
Run time: 1.125 sec.
Space: 831104 Bytes
GC: 2, GC time: 0.03125 sec.

エラトステネスの篩って、高校生のときに聞いて何が嬉しいのかさっぱりわからなかった記憶があります。効率よさそうにはとても見えなかったんですよね。