< 返回版块

0x5F3759DF 发表于 2020-09-04 01:29

Tags:dynamic programming, dp, cache, memoization

cached

缓存结构型,简化函数记忆化

cached 提供几种不同缓存结构型的实现和一个易用的用作定义记忆化函数的宏,可为动态规划算法的实现带来很大的便利

使用#[cached]/cached!宏定义的记忆化函数具有线程安全的特性,并自带封装在互斥锁中的后备函数缓存。函数缓存在函数执行期间是非锁定状态,因此,具有相同参数的长期运行函数的初始(在空缓存上)并发调用将被完整执行,并且每次完成时都会覆盖已记忆值。这与Python的functools.lru_cache行为相同

#[cached] & cached!宏定义记忆化函数

基本使用案例:

use cached::proc_macro::cached;

/// 定义一个叫`fib`的函数,此函数使用一个名为`FIB`的缓存
/// 默认情况下,缓存的名称与函数相同,但用全大写字母命名
/// 下一行代码与#[cached(name = "FIB", unbound)]效果相同
#[cached]
fn fib(n: u64) -> u64 {
    if n == 0 || n == 1 { return n }
    fib(n-1) + fib(n-2)
}
use std::thread::sleep;
use std::time::Duration;
use cached::proc_macro::cached;

/// 使用一个大小为100的lru(最近最少使用)缓存和一个类型为 `(String, String)` 的缓存键
#[cached(size=100)]
fn keyed(a: String, b: String) -> usize {
    let size = a.len() + b.len();
    sleep(Duration::new(size as u64, 0));
    size
}
use std::thread::sleep;
use std::time::Duration;
use cached::proc_macro::cached;
use cached::SizedCache;

/// 将`显式缓存类型`与`自定义创建块`和`自定义缓存键生成块`一起使用
#[cached(
    type = "SizedCache<String, usize>",
    create = "{ SizedCache::with_size(100) }",
    convert = r#"{ format!("{}{}", a, b) }"#
)]
fn keyed(a: &str, b: &str) -> usize {
    let size = a.len() + b.len();
    sleep(Duration::new(size as u64, 0));
    size
}

使用#[cached]/cached!定义的函数将使用函数的参数作为键来缓存其结果(在使用cached_key!时则是一个特定的表达式)。当用 cached! 定义的函数被调用时,在运行函数逻辑之前,首先会检查函数的缓存中是否存在已计算(并且仍然有效)的结果。

出于在全局缓存中存储参数和返回值的需要:

  • 函数返回类型必须被拥有并实现Clone
  • 函数参数必须被拥有并且实现 Hash + Eq + Clone 或者使用 cached_key! 宏来将参数转换为一个被拥有的 Hash + Eq + Clone 类型
  • 在插入和检索过程中,参数和返回值将被克隆
  • 请勿使用#[cached]/cached! 函数来产生 side-effectual 的结果!
  • 因为cached!会被扩展为once_cell 初始化和函数定义,所以#[cached]/cached! 函数不能直接存在于impl块下
  • #[cached]/cached! 函数不能接受类型为 Self 的参数

注意: 任何实现cached :: Cached的自定义缓存都可以与cached宏一起使用,以代替内置函数。

cached!cached_key! 用法与选项:

有多种选择,具体取决于您想要的显示方式。 有关完整的语法细分,请参见以下代码:

1.) 使用简写将使用无限制的缓存。

#[macro_use] extern crate cached;

/// 定义一个名为`fib`的函数并使用一个名为`FIB`的缓存
cached!{
    FIB;
    fn fib(n: u64) -> u64 = {
        if n == 0 || n == 1 { return n }
        fib(n-1) + fib(n-2)
    }
}

2.) 使用完整语法需要指定完整的缓存类型并提供要使用的缓存实例。 请注意,缓存的键类型是函数参数类型的元组。如果您希望对键进行精细控制,可以使用 cached_key! 宏。以下用例使用 SizedCache (LRU):

#[macro_use] extern crate cached;

use std::thread::sleep;
use std::time::Duration;
use cached::SizedCache;

/// 定义一个使用名为`COMPUTE`、大小限制为50的LRU缓存的名为`compute`的函数
/// `cached!`宏将隐式地将函数参数组合成一个元组,以用作缓存键

cached!{
    COMPUTE: SizedCache<(u64, u64), u64> = SizedCache::with_size(50);
    fn compute(a: u64, b: u64) -> u64 = {
        sleep(Duration::new(2, 0));
        return a * b;
    }
}

3.) cached_key宏的功能相同,但是允许将缓存键定义为表达式。

#[macro_use] extern crate cached;

use std::thread::sleep;
use std::time::Duration;
use cached::SizedCache;

/// 定义一个名为`length`的函数并使用一个名为`LENGTH`的LRU作为其缓存
/// `Key = ` 表达式用作显式定义将被用作缓存键使用的值
/// 在这里,借用的参数将转换为被拥有的字符串,该字符串可以存储在全局函数缓存中

cached_key!{
    LENGTH: SizedCache<String, usize> = SizedCache::with_size(50);
    Key = { format!("{}{}", a, b) };
    fn length(a: &str, b: &str) -> usize = {
        let size = a.len() + b.len();
        sleep(Duration::new(size as u64, 0));
        size
    }
}

4.) cached_resultcached_key_result 宏的作用对应于 cachedcached_key 相类似,但是带有缓存的函数需要返回Result(或诸如 io::Result的类型别名)。如果函数返回Ok(val),那么val会被缓存,但报错会不同。注意只有成功时的返回类型需要实现Clone, 错误时的返回类型则不需要。当使用cached_resultcached_key_result时,缓存的类型不能被派生,必须要明确指定。

#[macro_use] extern crate cached;

use cached::UnboundCache;

/// 缓存函数成功时的返回
/// 使用`cached_key_result`与使用`cached_key`时一样添加一个键函数
cached_result!{
   MULT: UnboundCache<(u64, u64), u64> = UnboundCache::new(); // 类型必须被指定
   fn mult(a: u64, b: u64) -> Result<u64, ()> = {
        if a == 0 || b == 0 {
            return Err(());
        } else {
            return Ok(a * b);
        }
   }
}

语法

常用的宏语法如下:

cached_key!{
    CACHE_NAME: CacheType = CacheInstance;
    Key = KeyExpression;
    fn func_name(arg1: arg_type, arg2: arg_type) -> return_type = {
        return_type
    }
}

其中:

  • CACHE_NAME 是用来存放指向缓存的static ref的特定名称
  • CacheType 是缓存的完整类型
  • CacheInstance 是一个可以产生 CacheType 实例的表达式,用作缓存存储,用;结尾
  • 当使用cached_key!宏的时候,"Key" 这一行必须被明确定义。该行必须以文字标记Key =开头,后跟一个计算为键的表达式,以;结尾。
  • fn func_name(arg1: arg_type) -> return_type 与普通的函数签名形式相同,唯一的不同是,当函数没有返回值时,必须明确声明 (比如 fn func_name(arg: arg_type) -> ())
  • = 之后的表达式是分配给func_name的函数体。注意,函数体可以对已被缓存的自己进行递归调用 (func_name)。

细粒度控制可使用 cached_control!

cached_control!宏允许提供插入到记忆化函数的关键区域中的表达式。尽管cachedcached_result变体可以应付大多数情况,但需要自定义宏的功能时会很有用。

#[macro_use] extern crate cached;

use cached::UnboundCache;

/// 以下的用例使用插入式表达式实现与`cached_result!`功能类似的宏

cached_control!{
    CACHE: UnboundCache<String, String> = UnboundCache::new();

    // 使用一个被拥有的参数副本`input`作为缓存键
    Key = { input.to_owned() };

    // 如果被缓存的值存在, 会被绑定到`cached_val`并且
    // 包含被缓存的主体的`Result`将会被返回
    // 这时,函数会直接返回,主体不会被执行
    
    PostGet(cached_val) = { return Ok(cached_val.clone()) };

    // 函数主体执行的结果会被绑定到`body_result`
    // 这种情况下,函数主体会返回一个`Result`
    // 我们会对`Result`进行匹配,如果函数出现错位,会提前返回一个`Err`
    // 其他情况下,我们会将函数的结果缓存起来
    PostExec(body_result) = {
        match body_result {
            Ok(v) => v,
            Err(e) => return Err(e),
        }
    };

    // 当向缓存插入值的时候
    // 我们将被插入值绑定到`set_value`并得到一个可插入缓存的副本

    Set(set_value) = { set_value.clone() };

    // 在返回之前打印出即将被返回的值
    Return(return_value) = {
        println!("{}", return_value);
        Ok(return_value)
    };

    fn can_fail(input: &str) -> Result<String, String> = {
        let len = input.len();
        if len < 3 { Ok(format!("{}-{}", input, len)) }
        else { Err("too big".to_string()) }
    }
}

许可证: MIT

评论区

写评论
chenwei767 2020-09-04 12:12

不错.

1 共 1 条评论, 1 页