フィボナッチ数列は、fib(n) = fib(n-1) + fib(n-2) の漸化式で表現される数列です。
プログラミングにおいて再帰の例でよく参照されます。
Rust で記述すると次のようになります。
// fib.rs
fn fib(n: u64) -> u64 {
match n {
0 => 0,
1 => 1,
_ => fib(n - 1) + fib(n - 2),
}
}
fn main() {
println!("{}", fib(46));
}
しかし、この実装はとても効率が悪く、n の数を増やすと実行時間がどんどん増えていきます。
以下は実機で計測した例ですが、n が 40 を超えるあたりで急激に実行時間が増えていることがわかります。
| n | 実行時間 [sec] |
|---|---|
| 0 | 0.00 |
| 10 | 0.00 |
| 20 | 0.00 |
| 30 | 0.00 |
| 40 | 0.99 |
| 41 | 1.60 |
| 42 | 2.62 |
| 43 | 4.28 |
| 44 | 6.96 |
| 45 | 11.01 |
| 46 | 18.02 |
この記事では、メモ化によって計算を高速化する方法を紹介します。
フィボナッチ数列のメモ化
実装サンプル
早速ですが実装サンプルです。
use std::collections::HashMap;
struct FibCached(HashMap<u64, u64>);
impl FibCached {
fn new() -> Self {
FibCached(HashMap::new())
}
fn get(&mut self, n: u64) -> u64 {
if let Some(&m) = self.0.get(&n) {
m
} else {
let m = match n {
0 => 0,
1 => 1,
_ => self.get(n - 1) + self.get(n - 2),
};
self.0.insert(n, m);
m
}
}
}
fn main() {
println!("{}", FibCached::new().get(46));
}
メモ化の手段として、一度計算した値を HashMap にキャッシュさせるようにします。
これによって、過去に計算済みの fib(n) についてはキャッシュを返すだけとして、計算量を削減します。
ただし、HashMap を保持するために構造体を準備する必要があり、実装はやや冗長になっています。FibCached の get メソッドが、フィボナッチ関数の本体になります。
実行結果
以下は実行結果です。
$ rustc fib_cached.rs && /usr/bin/time -f %E ./fib_cached
1836311903
0:00.00オリジナルでは計算に18秒かかっていたものが、一瞬で計算できるようになりました。
コメント