Skip to content

Instantly share code, notes, and snippets.

@jyn514
Created September 25, 2019 21:52
Show Gist options
  • Save jyn514/637ab76be9c870173a81e0ddacbd372f to your computer and use it in GitHub Desktop.
Save jyn514/637ab76be9c870173a81e0ddacbd372f to your computer and use it in GitHub Desktop.
Fibonacci using a thread_local cache
use std::cell::RefCell;
use std::io::{stdin, stdout, Write};
fn main() {
loop {
print!("Enter a positive integer: ");
stdout().flush().expect("could not flush buffer");
let mut input = String::new();
let read = stdin().read_line(&mut input).expect("failed to read line");
// EOF
if read == 0 || input.trim() == "quit" {
break;
}
let num: usize = match input.trim().parse() {
Ok(num) => num,
Err(e) => {
println!("error parsing integer: {}", e);
continue;
}
};
println!("fibonacci of {} is {}", num, fib(num));
}
}
fn fib(n: usize) -> u64 {
thread_local! {
static CACHE: RefCell<Vec<u64>> = RefCell::new(vec![1, 1]);
}
CACHE.with(|cache| {
let mut cache = cache.borrow_mut();
cache.reserve(n);
if cache.len() <= n {
let result = match n {
0 => 1,
1 => 1,
_ => fib(n - 1) + fib(n - 2),
};
cache.push(result);
}
cache[n]
})
}
#[cfg(test)]
mod test {
use super::fib;
#[test]
fn initial_values() {
assert_eq!(fib(0), 1);
assert_eq!(fib(1), 1);
assert_eq!(fib(2), 2);
}
#[test]
fn medium_values() {
assert_eq!(fib(3), 3);
assert_eq!(fib(5), 8);
assert_eq!(fib(6), 13);
assert_eq!(fib(10), 55);
assert_eq!(fib(12), 144);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment