読者です 読者をやめる 読者になる 読者になる

uokadaの見逃し三振は嫌いです

ここで述べられていることは私の個人的な意見に基づくものであり、私が所属する組織には一切の関係はありません。

コラッツの問題のベンチマーク

コラッツの問題

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

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ミリ秒前後でで処理できる様子。

まとめ

Language 実行時間(msec)
scala 130~150 msec
python 3500 msec

単純なリストの作成処理を比較した場合、pythonの20倍の速度でscalaが実行できました。 実行環境などの要因でこの数字はブレますのであくまで参考に。

参考

Scalaベンチマーク メモ(Hishidama's Scala Benchmark Memo)

Gomokuの形態素解析部をScalaで実装してみた - sileの日記