缓存/ memoization与对象生存期

Question

我的程序被构造为一系列函数调用，构建结果值 - 每个函数将返回值返回（移动）给它的调用者。这是一个简化版本：

struct Value {}

struct ValueBuilder {}

impl ValueBuilder {

    pub fn do_things_with_value(&mut self, v : &Value) {
        // expensive computations
    }

    pub fn make_value(&self) -> Value {
        Value {}
    }

    pub fn f(&mut self) -> Value {
        let v = self.make_value();
        self.do_things_with_value(&v);
        v
    }

    pub fn g(&mut self) -> Value {
        let v = self.f();
        self.do_things_with_value(&v);
        v
    }
}

play.rust-lang version

想象一下，除了f和g之外，还有更多类似于f和g的函数。您可以看到do_things_with_value被调用两次具有相同的值。我想缓存/ memoize这个调用，以便在下面的例子中“昂贵的计算”只执行一次。这是我（显然不正确）的尝试：

#[derive(PartialEq)]
struct Value {}

struct ValueBuilder<'a> {
    seen_values: Vec<&'a Value>,
}

impl<'a> ValueBuilder<'a> {
    pub fn do_things_with_value(&mut self, v: &'a Value) {
        if self.seen_values.iter().any(|x| **x == *v) {
            return;
        }
        self.seen_values.push(v)
        // expensive computations
    }

    pub fn make_value(&self) -> Value {
        Value {}
    }

    pub fn f(&mut self) -> Value {
        let v = self.make_value();
        self.do_things_with_value(&v); // error: `v` does not live long enough
        v
    }

    pub fn g(&mut self) -> Value {
        let v = self.f();
        self.do_things_with_value(&v);
        v
    }
}

play.rust-lang version

我理解为什么编译器正在这样做 - 虽然在这种情况下，在两次调用do_things_with_value之间没有丢弃v，但是不能保证它不会被丢弃，并且取消引用它会使程序崩溃。

有什么更好的方法来构建这个程序？我们假设：

• 克隆和储存Values是昂贵的，我们买不起seen_values保留我们见过的所有东西的副本
• 我们也无法重构代码/ Value对象来携带额外的数据（即bool指示我们是否使用此值进行了昂贵的计算）。它需要依靠使用PartialEq比较值

Answer 1

如果您需要在程序中的不同点保持相同的值，则最容易复制或克隆它。

但是，如果克隆不是一个选项，因为它太昂贵将值包装在Rc中。这是一个引用计数的智能指针，它允许共享其内容的所有权。克隆时相对便宜而不重复包含的值。

请注意，简单地将Rc<Value>存储在seen_values中将使所有值保持活动，至少与值构建器一样长。您可以通过存储Weak引用来避免这种情况。

use std::rc::{Rc, Weak};

#[derive(PartialEq)]
struct Value {}

struct ValueBuilder {
    seen_values: Vec<Weak<Value>>,
}

impl ValueBuilder {
    pub fn do_things_with_value(&mut self, v: &Rc<Value>) {
        if self
            .seen_values
            .iter()
            .any(|x| x.upgrade().as_ref() == Some(v))
        {
            return;
        }
        self.seen_values.push(Rc::downgrade(v))
        // expensive computations
    }

    pub fn make_value(&self) -> Rc<Value> {
        Rc::new(Value {})
    }

    pub fn f(&mut self) -> Rc<Value> {
        let v = self.make_value();
        self.do_things_with_value(&v);
        v
    }

    pub fn g(&mut self) -> Rc<Value> {
        let v = self.f();
        self.do_things_with_value(&v);
        v
    }
}

当Rc<Value>被函数链使用时，do_things()将记住值并跳过计算。如果某个值变为未使用（所有引用都被删除）并且稍后再次创建，则do_things()将重复计算。