inohilog

/var/log/inohiro

フィボナッチ数の計算をメモ化を利用して高速化してみる

ネタ元

メモ化: 一度計算した値を覚えておいて、次に別の計算をしたときに、すでに計算していたらその値を返すよ、という単純な仕組みです。久しぶりに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

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の領域確保かな?
とりあえずメモ化ぱねぇと思った。