6 releases

0.3.2 Mar 8, 2020
0.3.1 Mar 8, 2020
0.2.0 Feb 9, 2020
0.1.1 Feb 1, 2020

#17 in #i64

Download history 94/week @ 2024-03-16 150/week @ 2024-03-23 144/week @ 2024-03-30 197/week @ 2024-04-06 143/week @ 2024-04-13 113/week @ 2024-04-20 128/week @ 2024-04-27 153/week @ 2024-05-04 125/week @ 2024-05-11 128/week @ 2024-05-18 89/week @ 2024-05-25 136/week @ 2024-06-01 67/week @ 2024-06-08 98/week @ 2024-06-15 112/week @ 2024-06-22 40/week @ 2024-06-29

341 downloads per month
Used in competitive-hpp

BSD-3-Clause

22KB
469 lines

memoise crate-name at crates.io crate-name at docs.rs

Simple memoization library for rust

Documentation

Find it on docs.rs.

Usage

Add this to your Cargo.toml:

[dependencies]
memoise = "0.3"

And then, just add memoise attribute to functions you want to memoise:

use memoise::memoise;

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

And you can call it normally:

fn main() {
    println!("{}", fib(45));
}

And run it:

$ cargo build --release
$ time cargo run --release -q
1134903170

real    0m0.039s
user    0m0.000s
sys     0m0.016s

If comment out memoise attribute, it will not be memoised.

// #[memoise(n <= 100)]
fn fib(n: i64) -> i64 {
    if n == 0 || n == 1 {
        return n;
    }
    fib(n - 1) + fib(n - 2)
}
$ cargo build --release
$ time cargo run --release -q
1134903170

real    0m5.019s
user    0m4.984s
sys     0m0.016s

When no bounds for keys given, the cache table Vec will be allocated dynamically.

use memoise::memoise;

// the cache table for `n` is dynamically allocated
#[memoise(n)]
fn fib(n: i64) -> i64 {
    if n == 0 || n == 1 {
        return n;
    }
    fib(n - 1) + fib(n - 2)
}

_reset function frees allocated Vec.

fib(42); // This allocates cache table for `0..n+1`
fib_reset();

memoise_map memoises a function by using BTreeMap. It is suitable for keys are sparse.

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

_reset function also releases all allocated memory.

For more information, you can find a document on docs.rs.

Dependencies

~1.5MB
~34K SLoC