昨天看到有人轉噗一則 StackOverflow 上面的問題，內容是問他分別用 C,
python, erlang 與 haskell 寫了 Project Euler 的第十二題，但是
haskell 版本慢得不像話，該如何改進？
以下是苦主的原始 C 語言版：
#include <stdio.h>
#include <math.h>
int factorCount (long n)
{
double square = sqrt (n);
int isquare = (int) square;
int count = isquare == square ? -1 : 0;
long candidate;
for (candidate = 1; candidate <= isquare; candidate ++)
if (0 == n % candidate) count += 2;
return count;
}
int main ()
{
long triangle = 1;
int index = 1;
while (factorCount (triangle) < 1001)
{
index ++;
triangle += index;
}
printf ("%ld\n", triangle);
}
我的執行時間約為 5.48s
% gcc -lm -o euler12.bin euler12.c
% time ./euler12.bin
842161320
./euler12.bin 5.48s user 0.00s system 99% cpu 5.484 total
手癢想看看據說可以編譯出不錯的機器碼的 Common Lisp 速度怎麼樣，於是第
一個版本如下 (用 sbcl 執行)：
(defun factor-count (n)
(let* ((square (sqrt n))
(squaref (floor square))
(count (if (eql squaref square) -1 0)))
(loop
for cand from 1 to squaref
count (eql 0 (rem n cand)) into c
finally (return (+ count c c)))))
(defun first-triangle-over (n)
(loop
for idx from 1
sum idx into triangle
until (>= (factor-count triangle) n)
finally (return triangle)))
;; (time (first-triangle-over 1000))
;; Evaluation took:
;; 11.192 seconds of real time
;; 11.184699 seconds of total run time (11.184699 user, 0.000000 system)
;; 99.94% CPU
;; 30,135,882,489 processor cycles
;; 32,912 bytes consed
;;
;; 842161320
還不錯，11.192s，這個版本採用原文中給 haskell 的建議，使用 rem 而不是 mod，可以
加快一點速度。再給一點關於型別的提示，然後把第一個 function inline，第
二版可以跑出和 C 版本差不多的成績 5.563s 🙂
(declaim (inline factor-count)) ;; <----
(defun factor-count (n)
(let* ((square (sqrt n))
(squaref (floor square))
(count (if (eql squaref square) -1 0)))
(loop
for cand from 1 to squaref
count (eql 0 (rem n cand)) into c
finally (return (+ count c c)))))
(defun first-triangle-over (n)
(loop
for idx of-type fixnum from 1 ;; <----
sum idx into triangle of-type fixnum ;; <----
until (>= (factor-count triangle) n)
finally (return triangle)))
;; (time (first-triangle-over 1000))
;; Evaluation took:
;; 5.563 seconds of real time
;; 5.556347 seconds of total run time (5.556347 user, 0.000000 system)
;; 99.87% CPU
;; 14,970,270,903 processor cycles
;; 32,768 bytes consed
;;
;; 842161320
純粹湊個熱鬧而已，有興趣的人可以試試看把 loop 改成和原文其他語言一樣使
用遞迴來實做，大部分 Lisp 都有做 TCO，速度應該差不多…
結論：Common Lisp is awesome 😉
