Rustでたらいまわし

竹内関数

もはや説明も要らないほど有名な、日本の代表的なLisperである竹内郁雄さんが編み出した竹内関数。Rustで試したことがなかったので、やってみました。
まずはノーマルなたらいをまわします。

use std::time::Instant;

fn tarai(x: i32, y: i32, z: i32) -> i32 {
    if x <= y {
        y
    } else {
        tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
    }
}

fn main() {
    let start_tarai = Instant::now();

    println!("{}", tarai(10, 5, 0));

    let end_tarai = start_tarai.elapsed();

    let tarai_sec = end_tarai.as_secs() as f64 +
        end_tarai.subsec_nanos() as f64 / 1000_000_000.0;

    println!("tarai [benchmark]: {} secs", tarai_sec);
}

結果は以下のようになりました。

10
tarai [benchmark]: 0.001864613 secs

次にメモ化を使ったたらいをまわします。メモ化というのは、何度も計算することを避けるために、計算結果を記憶しておいて、過去に同じ引数で計算したことがあるものはその結果を使うという方法で、毎回計算するノーマルの場合と比べ、その分無駄がなくなるというやり方です。

use std::collections::HashMap;

type Memo = HashMap<(i32, i32, i32), i32>;

fn tarai_memo(x: i32, y: i32, z: i32, memo: &mut Memo) -> i32 {
    let key = (x, y, z);
    match memo.get(&key) {
        Some(&v) => v,
        None => {
            if x <= y {
                memo.insert(key, y);
                y
            } else {
                let v = tarai_memo(
                    tarai_memo(x - 1, y, z, memo),
                    tarai_memo(y - 1, z, x, memo),
                    tarai_memo(z - 1, x, y, memo),
                    memo
                    );
                memo.insert(key, v);
                v
            }
        }
    }
}

fn main() {
    let mut memo: Memo = HashMap::new();
    let start_tarai_memo = Instant::now();

    println!("{}", tarai_memo(10, 5, 0, &mut memo));

    let end_tarai_memo = start_tarai_memo.elapsed();

    let tarai_memo_sec = end_tarai_memo.as_secs() as f64 + 
        end_tarai_memo.subsec_nanos() as f64/ 1000_000_000.0;

    println!("tarai_memo [benchmark]: {} secs", tarai_memo_sec);
}

結果は以下のようになりました。

10
tarai_memo [benchmark]: 0.000739886 secs

だいぶ速くなりました。が、もうちょっとアレンジしてHashMapをBTreeMapに変更してやってみたところ、以下のような結果となりました。

use std::collections::BTreeMap;

type Memo = BTreeMap<(i32, i32, i32), i32>;

fn tarai_memo(x: i32, y: i32, z: i32, memo: &mut Memo) -> i32 {
    let key = (x, y, z);
    match memo.get(&key) {
        Some(&v) => v,
        None => {
            if x <= y {
                memo.insert(key, y);
                y
            } else {
                let v = tarai_memo(
                    tarai_memo(x - 1, y, z, memo),
                    tarai_memo(y - 1, z, x, memo),
                    tarai_memo(z - 1, x, y, memo),
                    memo
                    );
                memo.insert(key, v);
                v
            }
        }
    }
}

fn main() {
    let mut memo: Memo = BTreeMap::new();
    let start_tarai_memo = Instant::now();

    println!("{}", tarai_memo(10, 5, 0, &mut memo));

    let end_tarai_memo = start_tarai_memo.elapsed();

    let tarai_memo_sec = end_tarai_memo.as_secs() as f64 + 
        end_tarai_memo.subsec_nanos() as f64/ 1000_000_000.0;

    println!("tarai_memo [benchmark]: {} secs", tarai_memo_sec);
}

10
tarai_memo [benchmark]: 0.000500035 secs

BTreeMapのほうがやや速かったです。BTreeMapのキーの値はOrdを実装していなければなりません。この関数でキーとなる値は、i32のタプルです。i32はOrdを実装しており、すべてi32なので、このタプルもまたOrdを実装していることになります。したがって、今回はBTreeMapを使うことが可能です。
遅延評価版はなにやらややこしい感じになったので、やめました。うまくできるようになったらまた書くことにします。