プログラミング言語Rustを一通り読んだのでまずFibonacci数列書いてみたメモです。
Table Of Contents
準備
Fibonacci以外にも色々やっていく予定なので、Rustの勉強用リポジトリを作ります。
$ cargo new exercise --bin
$ cd exercise
モジュール
mainにﾄﾞﾊﾞﾄﾞﾊﾞ書いても良いのですがRustにはモジュールがあるので使ってみます。
$ cd src
$ touch lib.rs
$ touch fibonacci.rs
lib.rsにモジュールについての情報を書き込みます。
pub mod fibonacci;
fibonacci.rsを書いていきます。外部から呼ぶ関数にはpubをつけて宣言します。
pub fn fib_match(n: i32) -> i32 {
match n {
0 => 0,
1 => 1,
_ => fib_match(n-2) + fib_match(n-1),
}
}
main.rsから呼び出すときは
extern crate exercise;
use exercise::fibonacci;
fn main() {
assert_eq!(8, fibonacci::fib_match(5));
}
のようにします。
テスト
fibonacci.rs内に続けてテストを書いていく方向でいきます。
// pub fn fib_match() ... の下
#[cfg(test)]
mod tests_fibonacci {
use super::*;
#[test]
fn test_fib_match() {
assert_eq!(89, fib_match(10));
}
}
$ cargo test
Running target/debug/exercise-aedb186b5607382a
running 1 test
test fibonacci::tests_fibonacci::test_fib_match ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured
Running target/debug/exercise-d96eb056e1d4faff
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured
Doc-tests exercise
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured
ベンチマークテスト
Fibonacci数列計算の時間を図りたさがあるのでベンチマークテストを使ってみます。
注意して欲しいのはRust 1.9時点ではベンチマークテストはnightly buildでしか使えないということです。
nightlyの入手方法は以下にあります。
$ curl -s https://static.rust-lang.org/rustup.sh | sh -s -- --channel=nightly
これでベンチマークテストができます。
テストはfibonacci.rsに書いていくことにしたのでベンチマークテストを追加します。その前に、testアトリビュートとtestクレートをlib.rsに追加します。
#![feature(test)]
extern crate test;
pub mod fibonacci;
fibonacci.rsにベンチマークテストを書きます。
#[cfg(test)]
mod tests_fibonacci {
use super::*;
use test::Bencher;
#[test]
fn test_fib_match() {
assert_eq!(89, fib_match(10));
}
#[bench]
fn bench_fib_match(b: &mut Bencher) {
b.iter(|| fib_match(30));
}
}
$ cargo bench
Compiling exercise v0.1.0 (file:///home/vagrant/works/exercise)
Running target/release/exercise-aedb186b5607382a
running 2 tests
test fibonacci::tests_fibonacci::test_fib_match ... ignored
test fibonacci::tests_fibonacci::bench_fib_match ... bench: 1,207 ns/iter (+/- 768)
test result: ok. 0 passed; 0 failed; 1 ignored; 1 measured
Running target/release/exercise-d96eb056e1d4faff
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured
これは便利。
Fibonacci数列
パターンマッチを使った方法(O(2^n))はもう書いたのでそれ以外の方法でも書いてみます。
関数呼び出し1回
O(n)
Rustは関数内に関数を定義できます。
pub fn fib_one(n: i32) -> i32 {
fn func(a: i32, b: i32, c: i32) -> i32 {
if c < 2 { return a; }
func(a+b, a, c-1)
}
func(1, 0, n)
}
クロージャを使って再帰を書けたほう便利そうですが
クロージャを使った再帰はできないみたいです。
動的計画法
O(n)
pub fn fib_dp_simple(n: i32) -> i32 {
let mut f1 = 0;
let mut f2 = 1;
let mut tmp = 0;
for _ in 0..n-1 {
tmp = f1 + f2;
f1 = f2;
f2 = tmp;
}
tmp
}
配列を使って計算結果をメモ
一度計算した結果を配列にメモする方法。
プログラミングコンテストチャレンジブック [第2版]にあるC++のコード
int memo[MAX_N + 1];
int fib(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n];
return memo[n] = fib(n-1) + fib(n-2);
}
これを素直に実装しようとすると、memoはstatic mut [i32; MAX_N]型の配列になると思うのですが、static mut型の値を変更するにはunsafeを使わざるを得ないのでアンチパターンな気がします。
という意見をもらったので実装してみました。
const MAX_N: usize = 1000;
struct FibMemo {
memo: [i32; MAX_N],
}
impl FibMemo {
fn new() -> Self {
FibMemo { memo: [0; MAX_N] }
}
fn calc(&mut self, n: i32) -> i32 {
if n < 2 { return n; }
if self.memo[n as usize] != 0 { return self.memo[n as usize]; }
self.memo[n as usize] = self.calc(n-2) + self.calc(n-1);
self.memo[n as usize]
}
}
pub fn fib_memo(n: i32) -> i32 {
let mut f = FibMemo::new();
f.calc(n)
}
ベンチマークテストしてみるとあまり速度が出ておらず、もっと良い実装ありそうですが正解がわかってません。
繰り返し二乗法
O(log(n))
プログラミングコンテストチャレンジブック [第2版]にのってる方法です。
フィボナッチ数列の行列表現を利用した手法です。
fn mul(a: &[i32; 4], b: &[i32; 4]) -> [i32; 4] {
let mut c = [0; 4];
for i in 0..2 {
for k in 0..2 {
for j in 0..2 {
c[i*2+j] = c[i*2+j] + a[i*2+k] * b[k*2+j];
}
}
}
c
}
fn pow(mut a: [i32; 4], mut n: i32) -> [i32; 4] {
let mut b = [1, 0, 0, 1];
while n > 0 {
if n & 1 != 0 {
b = mul(&b, &a);
}
a = mul(&a, &a);
n >>= 1;
}
b
}
pub fn fib_repeat(n: i32) -> i32 {
// a[0] = A[0][0]
// a[1] = A[0][1]
// a[2] = A[1][0]
// a[3] = A[1][1]
let mut a = [1, 1, 1, 0];
a = pow(a, n);
a[2]
}
リファレンスやExampleを見るとビット演算やシフト演算もサポートされていました。
上のコードでは二次元配列ではなく一次元配列で処理してます。
一般項
O(1)
pub fn fib_formulas(n: i32) -> i32 {
( ( ( ( 1f64 + 5f64.sqrt() ) / 2f64 ).powi(n) - ( ( 1f64 - 5f64.sqrt() ) / 2f64 ).powi(n) ) / 5f64.sqrt() ).round() as i32
}
Rustはf64などのプリミティブ型にimplで数値計算系のメソッドが定義されているので、こういった処理を直感的に書けて便利感を感じました。
速度比較
matchの方法は遅すぎるのでのせてません。1000番目の計算時間です。
test fibonacci::bench_fib_one ... bench: 317 ns/iter (+/- 55)
test fibonacci::bench_fib_dp_simple ... bench: 321 ns/iter (+/- 59)
test fibonacci::bench_fib_memo ... bench: 8,525 ns/iter (+/- 1,039)
test fibonacci::bench_fib_repeat ... bench: 24 ns/iter (+/- 5)
test fibonacci::bench_fib_formulas ... bench: 0 ns/iter (+/- 0)
関数呼び出し1回と動的計画法はO(n)で同程度の時間、メモを使用した方法は結構時間かかっています。繰り返し二乗法はO(log(n))なので速いです。
一般項はO(1)なのでどんなnでも定数時間しかかからないので比較しても意味なさげです。
こういうアルゴリズム別に計算時間の比較とかしたいときにベンチマークテスト便利!便利!ってなりました。
まとめ
色々学びがありました。
テスト関係が標準であるのはいいことですね。ベンチマークテストも簡単に使えて便利でした。
Rustはコンパイラ先生がかなり厳しくつらいので、まだ慣れが必要感がすごいです。がんばるぞい。
ソースコードは以下にあります。自分のやる気次第ですが他のこともやってみたい予定です。
Show comments