Fibonacci number - コードの恵み

以前、AST変換でバイトコードを直接生成して計算する方法で Pure Java より速いことが話題に上がっていた。*1

Groovy1.8 ではバイトコードにまでする意味がなくなるのではと指摘されていたようにプリミティブ型の演算が速くなっていたのでその結果から見ていく。*2

Pure Groovy
165580141
Computed in 1864ms
Bytecode Groovy
165580141
Computed in 735ms

Groovy のサイトには載っていないのだがヘルプを見るとコマンドラインオプションが増えていてプリミティブ型の演算を off にすることもできる。
disableopt オプションは int か all しかまだないので今は同じ意味である。

groovy --disableopt int fib.groovy

以前の Wrapper ならどのくらいか比較してみる。
先ほどの結果と比較するとプリミティブとWrapperは約 7 倍の違いがある。

Pure Groovy
165580141
Computed in 14071ms
Bytecode Groovy
165580141
Computed in 737ms

メソッドをオーバーロードしてプリミティブ型と Wrapper 型が切り替わっていることを確認する。*3
ただし、long は実際には Long で扱われていて直前で unbox されているようなのでは速くはならなかった。

int i = 1

def printInt(int i) {
  println "int"
}

def printInt(Integer i) {
  println "Integer"
}

printInt(i)


long l = 1L

def printLong(long l) {
  println "long"
}

def printLong(Long l) {
  println "Long"
}

printLong(l)

アルゴリズムによる最適化

参考

Scheme, Ruby, Haskell で記述されているが分類すると 3つ

メモ化
動的計画法
逐次平方変換 *4

3番目の方法が理解できていないのだがとりあえず Groovy で実装して実行してみる。
memoize の再帰が1行で記述できないのが少し残念。*5

def fib_m
fib_m = { int n ->
  n <= 1 ? 1 : fib_m(n-2) + fib_m(n-1)
}.memoize()

def fib_d = { int n ->
  def rec = { int i ->
    if (i == 1) {
      [1, 1]
    } else {
      def (x1, x0) = call(i-1)
      [x1 + x0, x1]
    }
  }
  rec(n)[0]
}

def fib_v = { int n ->
  def rec = { int a, int b, int p, int q, int count ->
    count     == 0 ? b :
    count % 2 == 0 ? call(a, b, p*p+q*q, 2*p*q+q*q, count.intdiv(2)) :
                     call(b*q+a*q+a*p, b*p+a*q, p, q, count -1)
  }.call(1, 1, 0, 1, n)
}

long sd
println "fib_m"
sd = System.currentTimeMillis()
println fib_m(40)
println "Computed in ${(System.currentTimeMillis()-sd)}ms"

println "fib_d"
sd = System.currentTimeMillis()
println fib_d(40)
println "Computed in ${(System.currentTimeMillis()-sd)}ms"

println "fib_v"
sd = System.currentTimeMillis()
println fib_v(40)
println "Computed in ${(System.currentTimeMillis()-sd)}ms"

int を Integer に変えてもあまり変化のないレベルになる。

fib_m
165580141
Computed in 21ms
fib_d
165580141
Computed in 11ms
fib_v
165580141
Computed in 2ms

2011-04-16 追記

数学ガールを読み返してみたが逐次平方変換とは値が違ったので新たに書いてみる。
逐次平方変換も考え方は似ているが行列の値の意味がことなるようだ。

SICP 問題 1.19 （逐次平方変換を利用したFibonacci数を求める末尾再帰処理） - awacio.log から引用

a : １つ前の項の数値（と同時に解答でもある）
b : ２つ前の項の数値
p : 変換係数その１
q : 変換係数その２
i : あと何回計算するべきか。

行列は順番さえ入れ替えなければどこから計算してもよいので以下のエントリを参考に文字列の連結部分を行列の積に変更した。

404 Blog Not Found:アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 *6

def fib_r = { int n ->
  def mul = { int a, int b, int c, int d ->
            { int e, int f, int g, int h ->
    [a*e+b*g, a*f+b*h, c*e+d*g, c*f+d*h]
  } }
  def r = [1,0,0,1] // 初期値は単位行列
  def t = [1,1,1,0] // 数学ガール 乱択アルゴリズム p.271
  while (n > 0) {
    if (n & 1) r = mul(r)(t)
    n >>>= 1
    t = mul(t)(t)
  }
  r[0]
}
println "fib_r"
sd = System.currentTimeMillis()
println fib_r(40)
println "Computed in ${(System.currentTimeMillis()-sd)}ms"

fib_r
165580141
Computed in 3ms

フィボナッチ数列の一般項

コメントで id:akihiro4chawon 氏に指摘していただいて冪乗を検索していたときにその話題があったことを思い出した。

アルゴリズム百選 - フィボナッチ数列にO()を学ぶ - www.textfile.org

小飼弾氏と結城浩氏がブログでやり取りしていて川合史朗氏もコメント欄で参加されている。
フィボナッチ数列の一般項の場合オーダーは O(1) か O(n) かという話みたいだ。
まとまらないので書いたが消した。とりあえず結果だけ。

fib_b
165580141
Computed in 9ms

私は O(log n) より時間がかかるが注目しているループではないので O(1) と思うのだが 40 番目では測定結果は O(n) の動的計画法に近かった。*7

*1:groovyjarjarasm.asm は org.objectweb.asm にパッケージが変わった

*2:1.8.0-rc-4 で試した

*3:Wrapper でも 1.7 とは違い int i = null はエラーになる

*4:数学ガールにでてきた行列?

*5:プロパティにすればできるが

*6:ブログ名+冪乗で Hit しなかった

*7:BigDecimal の演算だから？