Crate red_memo

red_memo is a simple, safe, single-threaded, pure rust library for memoization and dynamic programming.

Memoizer<K,V> is the main cache type. It can be initialized with an underlying std::collections::HashMap with new_hash(), or with an underlying std::collections::BTreeMap with new_ord().

Keys can be either ordered or hashed. The outer api is identical for both cases,

The Debug trait is required for keys and values in order to make error messages intelligible.

The Clone trait is required tor keys in order to fulfill the expectations a user has for a memoizing cache.

The Clone trait is required for values. If Memoizer were to return immutable references to cached values, as is typically done, then the cache would have to be immutably borrowd while new values were being calculated from old ones, and the cache would not be updated with the new values.

If a value type cannot be made to implement Clone, or if it would be excessively costly to make copies, consider using std::rc::Rc.

use red_memo::Memoizer;

fn fibonacci(mem: &mut Memoizer<usize, usize>, k: &usize) -> usize
{
    let k = *k;
    if k < 2 {
        k
    } else {
        mem.lookup(&(k - 1)) + mem.lookup(&(k - 2))
    }
}

fn main()
{
    let mut fib_cache = Memoizer::new_ord(fibonacci);
    // since usize implements Hash+Eq as well, this could instead be
    // let mut fib_cache = Memoizer::new_hash(fibonacci);
    println!("fibonacci(20) = {}", fib_cache.lookup(&20));
    assert_eq!(fib_cache.lookup(&40), 102334155);
}

Structs

Memoizer

Memoization cache for a recursive user function