Speed comparison C vs Common Lisp

昨天看到有人轉噗一則 StackOverflow 上面的問題,內容是問他分別用 C,
python, erlang 與 haskell 寫了 Project Euler 的第十二題,但是
haskell 版本慢得不像話,該如何改進?

以下是苦主的原始 C 語言版:

    #a71d5d;">#include <stdio.h>
    #a71d5d;">#include <math.h>
    #a71d5d;">int #795da3;">factorCount (#a71d5d;">long n)
    {
        #a71d5d;">double square #a71d5d;">= #62a35c;">sqrt (n);
        #a71d5d;">int isquare #a71d5d;">= (#a71d5d;">int) square;
        #a71d5d;">int count #a71d5d;">= isquare #a71d5d;">== square #a71d5d;">? -#0086b3;">1 #a71d5d;">: #0086b3;">0;
        #a71d5d;">long candidate;
        #a71d5d;">for (candidate #a71d5d;">= #0086b3;">1; candidate #a71d5d;"><= isquare; candidate #a71d5d;">++)
            #a71d5d;">if (#0086b3;">0 #a71d5d;">== n #a71d5d;">% candidate) count #a71d5d;">+= #0086b3;">2;
        #a71d5d;">return count;
    }
    #a71d5d;">int #795da3;">main ()
    {
        #a71d5d;">long triangle #a71d5d;">= #0086b3;">1;
        #a71d5d;">int index #a71d5d;">= #0086b3;">1;
        #a71d5d;">while (factorCount (triangle) #a71d5d;">< #0086b3;">1001)
        {
            index #a71d5d;">++;
            triangle #a71d5d;">+= index;
        }
        #62a35c;">printf ("#0086b3;">%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 執行):

    (#a71d5d;">defun #795da3;">factor-count (n)
      (#a71d5d;">let* ((square (#62a35c;">sqrt n))
             (squaref (#62a35c;">floor square))
             (#62a35c;">count (#a71d5d;">if (#a71d5d;">eql squaref square) #a71d5d;">-#0086b3;">1 0)))
          (#a71d5d;">loop
             #a71d5d;">for cand #a71d5d;">from #0086b3;">1 #a71d5d;">to squaref
             #62a35c;">count (#a71d5d;">eql #0086b3;">0 (#a71d5d;">rem n cand)) into c
             #a71d5d;">finally (#a71d5d;">return (#a71d5d;">+ #62a35c;">count c c)))))
    (#a71d5d;">defun #795da3;">first-triangle-over (n)
        (#a71d5d;">loop
           #a71d5d;">for idx #a71d5d;">from #0086b3;">1
           #62a35c;">sum idx into triangle
           #62a35c;">until (#a71d5d;">>= (factor#a71d5d;">-#62a35c;">count triangle) n)
           #a71d5d;">finally (#a71d5d;">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 🙂

    (#62a35c;">declaim (inline factor#a71d5d;">-#62a35c;">count)) ;; <----
    (#a71d5d;">defun #795da3;">factor-count (n)
      (#a71d5d;">let* ((square (#62a35c;">sqrt n))
             (squaref (#62a35c;">floor square))
             (#62a35c;">count (#a71d5d;">if (#a71d5d;">eql squaref square) #a71d5d;">-#0086b3;">1 0)))
          (#a71d5d;">loop
             #a71d5d;">for cand #a71d5d;">from #0086b3;">1 #a71d5d;">to squaref
             #62a35c;">count (#a71d5d;">eql #0086b3;">0 (#a71d5d;">rem n cand)) into c
             #a71d5d;">finally (#a71d5d;">return (#a71d5d;">+ #62a35c;">count c c)))))
    (#a71d5d;">defun #795da3;">first-triangle-over (n)
        (#a71d5d;">loop
           #a71d5d;">for idx of#a71d5d;">-type fixnum #a71d5d;">from #0086b3;">1 ;; <----
           #62a35c;">sum idx into triangle of#a71d5d;">-type fixnum  ;; <----
           #62a35c;">until (#a71d5d;">>= (factor#a71d5d;">-#62a35c;">count triangle) n)
           #a71d5d;">finally (#a71d5d;">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 😉


已發佈

分類:

,

作者:

標籤: