Crate memoise

An attribute macro to memoise a function.

Usage

You can just add attribute memoise to normal functions that you want to memoise against arguments. For example:

use memoise::memoise;

#[memoise(n <= 100)]
fn fib(n: i64) -> i64 {
    if n == 0 || n == 1 {
        return n;
    }
    fib(n - 1) + fib(n - 2)
}

You need to specify upper-bound of arguments statically. Bounds can be specified by < or <= and must be integer literal. Calling memoised function by arguments that out of bounds cause panic.

You can specify multiple keys for memoise.

use memoise::memoise;

#[memoise(n <= 100, m <= 50)]
fn comb(n: usize, m: usize) -> usize {
    if m == 0 {
        return 1;
    }
    if n == 0 {
        return 0;
    }
    comb(n - 1, m - 1) + comb(n - 1, m)
}

To reuse memoised functions depend on non-key arguments, you can reset memoise tables by calling automatic defined function named <function-name>_reset. On above code, the function comb_reset is defined, so you can call that function to reset the table.

let a = comb(10, 5); // calculation
comb_reset();        // reset the memoization table
let a = comb(10, 5); // calculation executed again

You can also specify lower-bounds of keys.

use memoise::memoise;

#[memoise(-100 <= n <= 100)]
fn foo(n: i64) -> i64 {
    todo!()
}

If lower-bounds are not specified, concider ‘0 <= _’ is specified implicitly.

And you can specify keys as expressions instead of just variable names.

use memoise::memoise;

#[memoise(n * 100 + m <= 100)]
fn bar(n: i64, m: i64) -> i64 {
    todo!()
}

Without bounds, cache table will be allocated dynamically.

use memoise::memoise;

#[memoise(n, k)]
fn comb(n: usize, k: usize) -> usize {
    if k == 0 {
        return 1;
    }
    if n == 0 {
        return 0;
    }
    comb(n - 1, k - 1) + comb(n - 1, k)
}

memoise_map memoises a function with BTreeMap.

use memoise::memoise_map;

#[memoise_map(n, k)]
fn comb(n: usize, k: usize) -> usize {
    if k == 0 {
        return 1;
    }
    if n == 0 {
        return 0;
    }
    comb(n - 1, k - 1) + comb(n - 1, k)
}

Attribute Macros

memoise

Memoise function by using Vec

memoise_map

Memoise function by using BTreeMap