[OCaml][Common Lisp][Ruby][SICP]両替の組み合わせを数えるプログラムの実行速度

SICPにあった、両替の組み合わせを数えるプログラムを、Common Lisp、OCaml、Rubyで書いて、実行速度を比べてみた。

各言語のコード

Common Lisp

(defun change-count (amount)
  (change-count-aux amount 5))

(defun change-count-aux (amount kind)
  (cond
    ((= amount 0) 1)
    ((< amount 0) 0)
    ((= kind 0) 0)
    (t (+ (change-count-aux amount (1- kind))
      (change-count-aux (- amount (first-denomination kind)) kind)))))

(defvar *money* #(1 5 10 25 50))

(defun first-denomination (kind-of-coins)
  (elt *money* (1- kind-of-coins)))

OCaml

open Core.Std

let money = List.to_array [1; 5; 10; 25; 50]

let change_count amount =
  let first_denomination kind = money.(kind - 1) in
  let rec count amount kind =
    match (amount, kind) with
    | (0, _) -> 1
    | (amount', _) when amount' < 0 -> 0
    | (_, 0) -> 0
    | (_, _) -> (count amount (kind - 1))
                + (count (amount - (first_denomination kind)) kind)
  in
  count amount (Array.length money)
   
let () =
  print_endline "*start";
  flush stdout;
  printf "Change count 1000=%d\n" (change_count 1000)

Ruby

#!/usr/bin/env ruby

Money = [1,5,10,25,50]

def first_denomination(kind)
  Money[kind - 1]
end

def count(amount, kind)
  if amount == 0
    1
  elsif amount < 0
    0
  elsif kind == 0
    0
  else
    count(amount, kind - 1) + count((amount - first_denomination(kind)), kind)
  end
end

def change_count(amount)
  count(amount, 5)
end

print "*start\n"
printf("Change count 1000=%d\n", change_count(1000))

実行時間の比較

10ドルを1,5,10,25,50セントで両替する場合の組み合わせ数を求める時間を測定した。

Common Lispは Clozure CL 1.9を使用し、REPL上でtimeマクロで測定した。
OCaml は 4.01を使用。ocamlbuildでnative指定でコンパイルし、timeコマンドで測定した。
Rubyは2.0.0-p353を使用。timeコマンドで測定した。

環境はWindow8のVirtualBox上のDebian Wheezy。
CPUは Intel Core-i5 4200U 1.6GHz。
VirtualBoxには2CPUを割り当て。

Common Lisp

CL-USER> (time (change-count 1000))
(CHANGE-COUNT 1000)
took 4,475 milliseconds (4.475 seconds) to run.
During that period, and with 2 available CPU cores,
     4,752 milliseconds (4.752 seconds) were spent in user mode
         0 milliseconds (0.000 seconds) were spent in system mode
801451

OCaml

satoshi@debian:~/workspace/sicp/ch1$ time ./Ch1.native
*start
Change count 1000=801451
./Ch1.native  2.54s user 0.01s system 99% cpu 2.553 total

Ruby

satoshi@debian:~/workspace/sicp/ch1$ time ruby ch1.rb
*start
Change count 1000=801451
ruby ch1.rb  42.54s user 0.06s system 99% cpu 42.630 total

結果

Common Lisp(CCL1.9): 4.752sec
OCaml4.01: 2.54sec
Ruby: 42.54sec

何の根拠もなく、Common Lispの方がOCamlより速いのだろうと思っていたが、結果は逆で、OCamlの方が1.8倍ほど速かった。
圧倒的にRubyは遅かった。VM上でコードを実行するので、もう少し速いと思っていた。Ruby2.1だともう少し速いのかな?

その他

この規模のプログラムでは、各言語での読み易さには、あまり違いがない。OCamlのmatch 〜 with構文は、少し読み易いかなという程度。
Common LispやRubyと異なり、厳格な型チェックをするOCamlのコンパイルが通った後の、プログラム実行時の安心感は格別だ。