久しぶりに技術っぽいブログを書く
おひさしぶりです。
ちょっとずついろんなことを学んでいる今日この頃です。
（たまにどうぶつの森してるけど…
→
島メロをサガフロンティア2のRomanにしたりしてる。(今は違う)
— ふぁん (@fan_tech_) 2020年4月6日
時々島に逃げてる。 pic.twitter.com/JxSX49monW
）
今日は勉強していて初耳だったメモ化についての備忘録です。
私のために書くので分かりづらいとは思いますが…
知らなかった人は「へ～！」
知ってた人は「そうそう」って思ってくれれば幸いです。
（そもそもの解釈が間違ってたらさーせん！）
フィボナッチ数列について
これは有名な数列だから、ご存じの方も多いと思います。
n番目のフィボナッチ数をFnであらわすと、Fnは再帰的に…
F0 = 0,
F1 = 1,Fn+2 = Fn +F(n+1) (n≧0) で定義される…
ってやつ。
実際の数字で言うと
0,1,1,2,3,5,8,13,21,34,55,89,144,233....って感じにふえてくやつだね。
0 と 1 があって
0 + 1 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
(以下略）
これを式にすると上記のものになるって感じだ。
それをプログラミングするとどうなる…？
私の安直な頭で最初に思い浮かんだのがコレ
function fibonacci(n) { if (n === 0) { return 0; } else if (n === 1) { return 1; } return fibonacci(n - 1) + fibonacci(n - 2); } const length = 40; for (let i = 0; i <= length; i++) { console.log(fibonacci(i)); }
一応出力はできるけど、const lengthを増やした時になんだか早くない。
なんでだ～？って思ったら
const lengthを増やすと爆発的に足し算する回数が増えてしまうみたいなんだって。
（こういう処理の増え方を指数オーダーと言うらしい…しらなかった…）
そこでアルゴリズムを使ってみるといい。
1度使った計算を保存し、後からをそれを読み取れればもしかして…
大幅に計算量が減るのでは……
そういう小技を「メモ化」というらしい。
なるほどなるほど。
それを実際のソースコードにするとこうなる。
const memo = new Map(); memo.set(0, 0); memo.set(1, 1); function fib(n) { if(memo.has(n)) { return memo.get(n); } const value = fib(n - 1) + fib(n - 2); memo.set(n, value); return value; } const length = 40; for (let i = 0; i <= length; i++) { console.log(fib(i));
なるほどなるほど、
memoの1番目には０、memoの2番目には１が入っていて
もし、nにすでにnが含まれていたらnを返し、
入ってなかったら計算済みのフィボナッチ数をmemoの中にぶち込むのか…？
（という雑な認識）
そして最後にvalueを返して出力…
なるほど…
たしかに足し算の回数が圧倒的に少ないように思える。
っていうか少ないじゃん。
これ考えた人すごく賢い、賢い…すごい…
ということでいろいろ勉強した1日でした。まる。
