HackerNewsか何かで Fast Fibonacci algorithms を見つけて、Common Lispで書いてみた。
実行環境
- Windows 7 64bitAMD A10-6700T
- VMWare Player上 FreeBSD 10.1-RELEASE
- Clozure CL 1.10
- sbcl 1.2.9
ソースコード
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 をよりうまく書ければいいかな。