Skip to content

Instantly share code, notes, and snippets.

@mizukmb
Last active September 23, 2019 05:52
Show Gist options
  • Save mizukmb/5bf3e69f10c94af1a508f8ffa6cdf7f7 to your computer and use it in GitHub Desktop.
Save mizukmb/5bf3e69f10c94af1a508f8ffa6cdf7f7 to your computer and use it in GitHub Desktop.
// $ cargo +nightly --version # you need to use rustc nightly version
// cargo 1.39.0-nightly (3596cb86b 2019-09-19)
// $ cargo +nightly bench --features unstable
// Compiling ackermann-calc v0.1.0 (/home/mizukmb/src/ackermann-calc)
// Finished release [optimized] target(s) in 1.12s
// Running target/release/deps/ackermann_calc-83e1a1843dd244b1
//
// running 9 tests
// test tests::a0 ... ignored
// test tests::a1 ... ignored
// test tests::a2 ... ignored
// test tests::a3 ... ignored
// test tests::a4 ... ignored
// test tests::conv_from_u32_biguint ... ignored
// test bench::biguint_bench ... bench: 43,511,770 ns/iter (+/- 1,410,295)
// test bench::memo_bench ... bench: 1,492,002 ns/iter (+/- 144,372)
// test bench::naive_bench ... bench: 839,195 ns/iter (+/- 48,702)
//
// test result: ok. 0 passed; 0 failed; 6 ignored; 3 measured; 0 filtered out
#![feature(test)]
extern crate test;
use std::thread;
use num_bigint::BigUint;
use std::collections::HashMap;
fn biguint_ackermann(m: u32, n: u32) -> BigUint {
fn work(m: BigUint, n: BigUint) -> BigUint {
if m == b(0) {
n + b(1)
} else if n == b(0) {
work(m.clone() - b(1), b(1))
} else {
work(m.clone() - b(1), work(m.clone(), n - b(1)))
}
}
work(b(m), b(n))
}
fn naive_ackermann(m: i32, n: i32) -> i32 {
fn work(m: i32, n: i32) -> i32 {
if m == 0 {
n + 1
} else if n == 0 {
work(m - 1, 1)
} else {
work(m - 1, work(m, n - 1))
}
}
fn run_in_thread(m: i32, n: i32) -> i32 {
let builder = thread::Builder::new()
.name("large_stack_thread".into())
.stack_size(32 * 1024 * 1024); // 32MiB
let handler = builder.spawn(move || work(m, n)).unwrap();
handler.join().unwrap()
}
run_in_thread(m, n)
}
// What's ackermann function?
// A(m,n) =
// n+1 if m = 0
// A(m-1,1) if m > 0 and n = 0
// A(m-1,A(m,n-1)) if m > 0 and n > 0
fn ackermann(m: u32, n: u32) -> BigUint {
fn work(m: BigUint, n: BigUint, memo: &mut HashMap<(BigUint, BigUint), BigUint>) -> BigUint {
if let Some(v) = memo.get(&(m.clone(), n.clone())) {
(*v).clone()
} else {
if m == b(0) {
let res = n.clone() + b(1);
memo.insert((m, n), res.clone());
res
} else if n == b(0) {
let res = work(m.clone() - b(1), b(1), memo);
memo.insert((m, n), res.clone());
res
} else {
let res = work(m.clone() - b(1), work(m.clone(), n.clone() - b(1), memo), memo);
memo.insert((m, n), res.clone());
res
}
}
}
fn run_in_thread(m: u32, n: u32) -> BigUint {
let builder = thread::Builder::new()
.name("large_stack_thread".into())
.stack_size(32 * 1024 * 1024); // 32MiB
let handler = builder.spawn(move || {
let mut memo = HashMap::new();
work(b(m), b(n), &mut memo)
}).unwrap();
handler.join().unwrap()
}
run_in_thread(m, n)
}
fn b(v: u32) -> BigUint {
BigUint::from(v)
}
fn main() {
println!("{}", ackermann(1, 0));
}
#[cfg(test)]
mod tests {
use super::*;
use std::convert::TryInto;
#[test]
fn a0() {
assert_eq!(ackermann(0, 0), b(1));
assert_eq!(ackermann(0, 1), b(2));
}
#[test]
fn a1() {
assert_eq!(ackermann(1, 0), b(2));
assert_eq!(ackermann(1, 1), b(3));
assert_eq!(ackermann(1, 2), b(4));
}
#[test]
fn a2() {
assert_eq!(ackermann(2, 0), b(3));
assert_eq!(ackermann(2, 1), b(5));
for i in 0..10 {
assert_eq!(ackermann(2, i), b(2 * i + 3));
}
}
#[test]
fn a3() {
for i in 0..10 {
let ui: u32 = i.try_into().unwrap();
assert_eq!(ackermann(3, i), b(2_u32.pow(ui + 3) - 3));
}
}
#[test]
fn a4() {
assert_eq!(ackermann(4, 1), b(65533));
}
#[test]
fn conv_from_u32_biguint() {
assert_eq!(b(5), BigUint::new(vec![5]));
}
}
#[cfg(all(feature = "unstable", test))]
mod bench {
use super::*;
use self::test::Bencher;
#[bench]
fn naive_bench(b: &mut Bencher) {
b.iter(|| naive_ackermann(3, 7))
}
#[bench]
fn biguint_bench(b: &mut Bencher) {
b.iter(|| biguint_ackermann(3, 7))
}
#[bench]
fn memo_bench(b: &mut Bencher) {
b.iter(|| ackermann(3, 7))
}
}
@mizukmb
Copy link
Author

mizukmb commented Sep 23, 2019

アッカーマン関数の計算過程を表示する (その↑) / DDRの足運び最適化問題を解く ( https://booth.pm/ja/items/1575590 ) の 3.2.5 ベンチマークを取ってみる を実際に実行するための手順

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment