fact いろいろ

階乗を求めるコードをいろいろなバージョンで。特に意味はない。

(use srfi-1)

(define (fact-1 n)
  (letrec ((fact-sub (lambda (n result)
                       (if (> n 1)
                           (fact-sub (- n 1) (* n result))
                           result))))
    (fact-sub n 1)))

(define (fact-2 n)
  (apply * (iota n 1)))

(define (fact-3 n)
  (letrec ((fact-cps 
            (lambda (x cont)
              (if (<= x 1)
                  (cont 1)
                  (fact-cps (- x 1) 
                            (lambda (y)
                              (cont (* x y))))))))
    (fact-cps n values)))

(define (fact-4 n)
  (if (<= n 1)
      1
      (* n (fact-4 (- n 1)))))


(define (fact-5 n)
  (let ((r 1))
    (do ((i 1 (+ i 1)))
        ((> i n) r)
      (set! r (* i r)))))

(define (fact-6 n)
  (do ((i 1 (+ i 1))
       (r 1 (* r i)))
      ((> i n) r)))

(define (main args)
  (let ((n 8000))
    (time (fact-1 n))
    (time (fact-2 n))
    (time (fact-3 n))
    (time (fact-4 n))
    (time (fact-5 n))
    (time (fact-6 n))))

結果。

;(time (fact-1 n))
; real   0.290
; user   0.290
; sys    0.000
;(time (fact-2 n))
; real   1.372
; user   1.370
; sys    0.000
;(time (fact-3 n))
; real   0.308
; user   0.310
; sys    0.000
;(time (fact-4 n))
; real   0.286
; user   0.290
; sys    0.000
;(time (fact-5 n))
; real   0.255
; user   0.260
; sys    0.000
;(time (fact-6 n))
; real   0.259
; user   0.260
; sys    0.000