フィボナッチ数の計算をメモ化を利用して高速化してみる
ネタ元
メモ化: 一度計算した値を覚えておいて、次に別の計算をしたときに、すでに計算していたらその値を返すよ、という単純な仕組みです。久しぶりにC#で書いた（uintだとまだまだ小さいので、BigInteger（.NET 4.0以降, System.Numerics名前空間））を利用した。まずはメモ化しないfibメソッド。
private static BigInteger fib( BigInteger n ) { if( n <= 1 ) { return n; } else { return fib( n - 2 ) + fib( n - 1 ); } }
次にメモ化するCalcクラスのfibメソッド(クラス名おかしいよなあ。。。）。変数memoはDictionary
public BigInteger fib( BigInteger n ) { if( n <= 1 ) { return n; } else { if( memo.ContainsKey( n ) ) { return memo[n]; } else { BigInteger result = fib( n - 2 ) + fib( n - 1 ); memo.Add( n, result ); // output(); return result; } } }
uint じゃ小さいからもっとでかくしよう。 => BigInteger にしてみた。遅い。
fib(100）とかfib(300)とかfib(1000)とか
もはや合っているのかわからない。。
[100], 354224848179261915075, 0 msec
[300], 222232244629420445529739893461909967206666939096499764990979600, 0 msec
[1000], 43466557686937456435688527675040625802564660517371780402481729089536555 41794905189040387984007925516929592259308032263477520968962323987332247116164299 6440906533187938298969649928516003704476137795166849228875, 0 msec
- ここ（The first 300 Fibonacci numbers, factored）によれば、fib(100)とfib(300）の値は合ってそう
fib(0)からfib(40) とか
結果は列挙すると長いので、「続きを読む」にします。
uint 版
上がメモ化を用いないで計算したfib(0)からfib(40)。下がメモ化を用いたもの。
[0], 0, 0 msec [1], 1, 0 msec [2], 1, 0 msec [3], 2, 0 msec [4], 3, 0 msec [5], 5, 0 msec [6], 8, 0 msec [7], 13, 0 msec [8], 21, 0 msec [9], 34, 0 msec [10], 55, 0 msec [11], 89, 0 msec [12], 144, 0 msec [13], 233, 0 msec [14], 377, 0 msec [15], 610, 0 msec [16], 987, 0 msec [17], 1597, 0 msec [18], 2584, 0 msec [19], 4181, 0 msec [20], 6765, 0 msec [21], 10946, 0 msec [22], 17711, 15 msec [23], 28657, 0 msec [24], 46368, 0 msec [25], 75025, 16 msec [26], 121393, 15 msec [27], 196418, 16 msec [28], 317811, 31 msec [29], 514229, 63 msec [30], 832040, 93 msec [31], 1346269, 125 msec [32], 2178309, 203 msec [33], 3524578, 327 msec [34], 5702887, 531 msec [35], 9227465, 842 msec [36], 14930352, 1357 msec [37], 24157817, 2200 msec [38], 39088169, 3557 msec [39], 63245986, 5709 msec [40], 102334155, 9251 msec ==================================== [0], 0, 0 msec [1], 1, 0 msec [2], 1, 16 msec [3], 2, 0 msec [4], 3, 0 msec [5], 5, 0 msec [6], 8, 0 msec [7], 13, 0 msec [8], 21, 0 msec [9], 34, 0 msec [10], 55, 0 msec [11], 89, 0 msec [12], 144, 0 msec [13], 233, 0 msec [14], 377, 0 msec [15], 610, 0 msec [16], 987, 0 msec [17], 1597, 0 msec [18], 2584, 0 msec [19], 4181, 0 msec [20], 6765, 0 msec [21], 10946, 0 msec [22], 17711, 0 msec [23], 28657, 0 msec [24], 46368, 0 msec [25], 75025, 0 msec [26], 121393, 0 msec [27], 196418, 0 msec [28], 317811, 0 msec [29], 514229, 0 msec [30], 832040, 0 msec [31], 1346269, 0 msec [32], 2178309, 0 msec [33], 3524578, 0 msec [34], 5702887, 0 msec [35], 9227465, 0 msec [36], 14930352, 0 msec [37], 24157817, 0 msec [38], 39088169, 0 msec [39], 63245986, 0 msec [40], 102334155, 0 msec
BigInteger 版
[0], 0, 0 msec [1], 1, 0 msec [2], 1, 0 msec [3], 2, 0 msec [4], 3, 0 msec [5], 5, 0 msec [6], 8, 0 msec [7], 13, 0 msec [8], 21, 0 msec [9], 34, 0 msec [10], 55, 0 msec [11], 89, 0 msec [12], 144, 0 msec [13], 233, 0 msec [14], 377, 0 msec [15], 610, 0 msec [16], 987, 0 msec [17], 1597, 0 msec [18], 2584, 0 msec [19], 4181, 16 msec [20], 6765, 0 msec [21], 10946, 16 msec [22], 17711, 0 msec [23], 28657, 16 msec [24], 46368, 47 msec [25], 75025, 46 msec [26], 121393, 110 msec [27], 196418, 140 msec [28], 317811, 234 msec [29], 514229, 374 msec [30], 832040, 593 msec [31], 1346269, 967 msec [32], 2178309, 1545 msec [33], 3524578, 2527 msec [34], 5702887, 4072 msec [35], 9227465, 6583 msec [36], 14930352, 10639 msec [37], 24157817, 17254 msec [38], 39088169, 28002 msec [39], 63245986, 45287 msec [40], 102334155, 73305 msec ==================================== [0], 0, 0 msec [1], 1, 0 msec [2], 1, 16 msec [3], 2, 0 msec [4], 3, 0 msec [5], 5, 0 msec [6], 8, 0 msec [7], 13, 0 msec [8], 21, 0 msec [9], 34, 0 msec [10], 55, 0 msec [11], 89, 0 msec [12], 144, 0 msec [13], 233, 0 msec [14], 377, 0 msec [15], 610, 0 msec [16], 987, 0 msec [17], 1597, 0 msec [18], 2584, 0 msec [19], 4181, 0 msec [20], 6765, 0 msec [21], 10946, 0 msec [22], 17711, 0 msec [23], 28657, 0 msec [24], 46368, 0 msec [25], 75025, 0 msec [26], 121393, 0 msec [27], 196418, 0 msec [28], 317811, 0 msec [29], 514229, 0 msec [30], 832040, 0 msec [31], 1346269, 0 msec [32], 2178309, 0 msec [33], 3524578, 0 msec [34], 5702887, 0 msec [35], 9227465, 0 msec [36], 14930352, 0 msec [37], 24157817, 0 msec [38], 39088169, 0 msec [39], 63245986, 0 msec [40], 102334155, 0 msec
時間の計測は、超単純にこーいうかんじなので、どれくらいの精度があるのかわかりませんが。。。
var start1 = System.Environment.TickCount;
var result1 = fib( i );
var end1 = System.Environment.TickCount;
output( i, result1, end1 - start1 ); // output は Console.WriteLine を呼んでる
たまにメモ化しているほうで「15,6msec」かかる時があるんだけど、これは何でだろう。memoの領域確保かな？
とりあえずメモ化ぱねぇと思った。
