memoires 🧠

在 Rust 中实现 Memoization 的最困难方式...

使用方法

让我们想象你有一个实现斐波那契序列的函数

fn fib(n: usize) -> usize {
    if n == 0 {
        0
    } else if n == 1 {
        1
    } else {
        fib(n - 1) + fib(n - 2)
    }
}


fn main() {
    // long as f*ck
    for i in 1..60 {
        println!("{}", fib(i))
    }
}

它将变为

use memoires::Memoire;

// The two generics of Memoire<usize, usize> must be change to the types
// your function will return.
//
// If you have a f(String) -> String, you gonna write Memoire<String, String>.
//
// IMPORTANT: 
//  - the input type must implement the Clone, Eq and Hash traits
//  - the output type must implement the Clone trait
//
fn fib<I, O>(n: usize, m: &mut Memoire<usize, usize>) -> usize {
    if n == 0 {
        0
    } else if n == 1 {
        1
    } else {
        m.run(n - 1) + m.run(n - 2) // Replace the function name with m.run
    }
}

fn main() {
    let mut fib_mem = Memoire::new(fib::<isize, isize>);

    for i in 1..60 {
        println!("{}", fib_mem.run(i))
    }
}