コラッツの問題のベンチマーク - uokadaの見逃し三振は嫌いです

1〜1000までの整数についてコラッツの問題を解くコードを pythonとscalaで書いてみてそれぞれのベンチマークをとってみた。

scalaバージョン

import scala.testing.Benchmark

object BenchCollatz extends Benchmark {

  override def prefix = "Collatz"

  def collatz(num: Int): List[Int] = {
    num match {
      case 1                   => List(1)
      case num if num % 2 == 0 => num :: collatz(num / 2)
      case num if num % 2 == 1 => num :: collatz(num * 3 + 1)
    }
  }

  def run() = {
    1 to 1000 map (collatz)
  }
}

pythonバージョン

#!/usr/bin/env python2.7
# -*-coding:utf-8 -*-
from timeit import Timer

s = '''
def collatz(n):
    ls = [n]
    while not n == 1:
        if n % 2 == 0:
            n = n / 2
        elif n % 2 == 1:
            n = n * 3 + 1
        ls.append(n)
    return ls

for i in xrange(1, 1000 + 1):
    collatz(i)
'''
if __name__ == '__main__':
    t = Timer(stmt=s)
    # ミリ秒で表示するために1000で乗算
    print map(lambda x: x * 1000.0, t.repeat(repeat=10, number=100))

コードが揃ったところで測定してみます。まず、scalaコードの測定

# scala 2.9.1で測定
% scala -version
Scala code runner version 2.9.1.final -- Copyright 2002-2011, LAMP/EPFL

# コンパイル
% scalac src/BenchCollatz.scala 

# コラッツの問題を100回繰り返す処理を10回繰り返すベンチマーク
# % scala BenchCollatz <繰り返す回数> <1回の試行でrun()を呼び出す回数>

% scala BenchCollatz 10 100
Collatz	308	154	131	144	133	133	132	132	128	129
# 単位はミリ秒 100回実行して130~150ミリ秒で処理できる様子

scalaだと100回実行して130~150ミリ秒で処理できる様子

次は、python

% python2.7 BenchCollatz.py
[3453.1171321868896, 3438.311815261841, 3749.725103378296, 
3545.8619594573975, 3768.6450481414795, 3628.9780139923096, 
3509.5250606536865, 3587.18204498291, 3496.6540336608887, 3595.9320068359375]

pythonだと100回実行して3500ミリ秒前後でで処理できる様子。