CLでSRFI-27 — #:g1

Posted 2012-01-08 23:30:00 GMT

CLでSRFI、今回は、SRFI-27の「Sources of Random Bits」です。
SRFI-27は、CLでいうと、cl:randomを中心とした乱数関係のものを提供するライブラリです。

動作

(srfi-27:random-integer 100)
;=>  92

(srfi-27:random-real)
;=>  0.7949600206575553d0

(defun random-permutation (n)
  (flet ((random-source-make-permutations (s)
           (let ((rand (srfi-27:random-source-make-integers s)))
             (lambda (n)
               (let ((x (srfi-43:make-vector n 0)))
                 (do ((i 0 (+ i 1)))
                     ((= i n))
                   (srfi-43:vector-set! x i i) )
                 (do ((k n (- k 1)))
                     ((= k 1) x)
                   (let* ((i (- k 1))
                          (j (funcall rand k))
                          (xi (srfi-43:vector-ref x i))
                          (xj (srfi-43:vector-ref x j)) )
                     (srfi-43:vector-set! x i xj)
                     (srfi-43:vector-set! x j xi) )))))))
    (funcall (random-source-make-permutations srfi-27:default-random-source)
             n )))

(random-permutation 20) ;=> #(13 9 12 0 4 18 5 8 19 2 10 6 7 17 14 15 11 16 3 1)

移植について

参照実装には、Schemeだけのものと、高速化のためにCで書いたものと組み合わせるものがありますが、単純にSchemeだけのものを移植してみました。 動作のテストですが、参照実装に付いてくるテストは通りましたが、DIEHARDテストという、ファイルに書き出すタイプが出力する内容がどうも説明と違います。Gaucheで同じ内容のテストを動作させると、CLに移植したものと同じ内容のファイルを出力するので、とりあえずこれで良いかなということにしました。
速度は、cl:randomと比べると、20倍程度遅いですが、チューニングもしていないので最適化を詰めていけば、cl:random位のスピードにできるのかもしれません。
;;; 速度比較

;; srfi-27
(dotimes (i 10000000)
  (srfi-27:random-real))
;⇒ NIL
----------
Evaluation took:
  1.839 seconds of real time
  1.840115 seconds of total run time (1.840115 user, 0.000000 system)
  [ Run times consist of 0.060 seconds GC time, and 1.781 seconds non-GC time. ]
  100.05% CPU
  4,402,953,630 processor cycles
  480,031,120 bytes consed

Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz

(dotimes (i 10000000) (random 1.0d0)) ;⇒ NIL ---------- Evaluation took: 0.446 seconds of real time 0.448028 seconds of total run time (0.448028 user, 0.000000 system) 100.45% CPU 1,066,179,303 processor cycles 0 bytes consed

Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz

(dotimes (i 10000000) (srfi-27:random-integer 1000)) ;⇒ NIL ---------- Evaluation took: 2.172 seconds of real time 2.168136 seconds of total run time (2.168136 user, 0.000000 system) 99.82% CPU 5,201,124,219 processor cycles 37,648 bytes consed

Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz

(dotimes (i 10000000) (random 1000)) ;⇒ NIL ---------- Evaluation took: 0.383 seconds of real time 0.384024 seconds of total run time (0.384024 user, 0.000000 system) 100.26% CPU 915,014,997 processor cycles 0 bytes consed

Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz


comments powered by Disqus