Common Lispでフィボナッチ関数を書いてみたら、泥沼にハマった。

2016-05-21 07:07:03

HackerNewsか何かで Fast Fibonacci algorithms を見つけて、Common Lispで書いてみた。

実行環境

ソースコード

Slowly DP。F(k-1), F(k)がわかってたら、F(k+1)もわかる。

(defun fibonacci (n)
  (labels ((f (n a b)
	     (if (or (= n 1) (= n 2))
		 b
		 (f (1- n) b (+ a b)))))
    (f n 1 1)))

次は、Fast Double。ashは算術シフトする関数。

(defun fast-fibonacci (n)
  (cond ((or (= n 1) (= n 2)) 1)
	((evenp n) 
	 (let* ((p (ash n -1))
		(a (fast-fibonacci p))
		(b (fast-fibonacci (1+ p))))
	   (- (ash (* a b) 1) (* a a))))
	((oddp n)
	 (let* ((p (ash (1- n) -1))
		(a (fast-fibonacci p))
		(b (fast-fibonacci (1+ p))))
	   (+ (* a a) (* b b))))))

テスト

上のようにテスト関数を作って、性能を確認してみると、 時間もメモリもFast Doubleが上。

(defun test-fibonacci ()
  (loop for fn in (list #'fibonacci #'fast-fibonacci)
       do (time (funcall fn 500000))))

Clozure CL 1.10

(FUNCALL FN 500000)
took 24,491,428 microseconds (24.491428 seconds) to run.
      3,649,664 microseconds ( 3.649664 seconds, 14.90%) of which was spent in GC.
During that period, and with 2 available CPU cores,
      4,314,482 microseconds ( 4.314482 seconds) were spent in user mode
     20,222,251 microseconds (20.222252 seconds) were spent in system mode
 10,857,496,112 bytes of memory allocated.
 1,647 minor page faults, 0 major page faults, 0 swaps.
(FUNCALL FN 500000)
took 90,302 microseconds (0.090302 seconds) to run.
        473 microseconds (0.000473 seconds, 0.52%) of which was spent in GC.
During that period, and with 2 available CPU cores,
     75,278 microseconds (0.075278 seconds) were spent in user mode
     14,792 microseconds (0.014792 seconds) were spent in system mode
 2,661,776 bytes of memory allocated.

sbcl 1.2.9

Evaluation took:
  8.821 seconds of real time
  8.815573 seconds of total run time (8.220311 user, 0.595262 system)
  [ Run times consist of 1.199 seconds GC time, and 7.617 seconds non-GC time. ]
  99.94% CPU
  22,010,553,980 processor cycles
  10,853,635,904 bytes consed
  
Evaluation took:
  0.184 seconds of real time
  0.184765 seconds of total run time (0.184765 user, 0.000000 system)
  [ Run times consist of 0.010 seconds GC time, and 0.175 seconds non-GC time. ]
  100.54% CPU
  459,482,400 processor cycles
  83,402,992 bytes consed

別のテスト

(defun test2-fibonacci (n)
  (time (dotimes (p 1000) (loop for i from 1 to n do (fibonacci i))))
  (time (dotimes (p 1000) (loop for i from 1 to n do (fast-fibonacci i)))))

150あたりまでだと、Slowly DPのほうが実行時間が速い。 180以降はFast Doubleのが速い。なんでだろう。

sbcl 1.2.9

test2-fibonacciを実行してみた。すると、断然slowly DPのが早かった。

CL-USER> (test2-fibonacci 150)
Evaluation took:
  0.197 seconds of real time
  0.196579 seconds of total run time (0.196500 user, 0.000079 system)
  [ Run times consist of 0.007 seconds GC time, and 0.190 seconds non-GC time. ]
  100.00% CPU
  492,008,563 processor cycles
  58,540,800 bytes consed
  
Evaluation took:
  2.735 seconds of real time
  2.733805 seconds of total run time (2.710233 user, 0.023572 system)
  [ Run times consist of 0.206 seconds GC time, and 2.528 seconds non-GC time. ]
  99.96% CPU
  6,823,969,586 processor cycles
  1,829,255,296 bytes consed

最後に

sbclなら、fibonacciが断然速いとしか言えない。

テストの書き方はこれでいいのかとか、 fast-fibonacci をよりうまく書ければいいかな。