如何编写可以读取和写入缓存的生锈函数？

问题描述 投票：0回答：3

Original Problem Statement

我正在尝试编写一个可以从缓存中读取和写入的函数，但是我遇到了一个问题，编译器说我不能同时使用缓存而且不可靠地借用缓存。

我已经阅读了https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html，https://naftuli.wtf/2019/03/20/rust-the-hard-parts/和随机堆栈溢出/ Reddit帖子，但我看不出如何应用他们对此代码所说的内容。

use std::collections::HashMap;

struct CacheForMoves {
    set_of_moves: Vec<usize>,
    cache: HashMap<usize, Vec<Vec<usize>>>,
}

impl CacheForMoves {
    fn new(set_of_moves: Vec<usize>) -> CacheForMoves {
        CacheForMoves {
            set_of_moves: set_of_moves,
            cache: HashMap::new(),
        }
    }

    fn get_for_n(&self, n: usize) -> Option<&Vec<Vec<usize>>> {
        self.cache.get(&n)
    }

    fn insert_for_n(&mut self, n: usize, value: Vec<Vec<usize>>) {
        self.cache.insert(n, value);
    }
}

fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
    return match cache.get_for_n(n) {
        Some(result) => result,
        None => stairs(cache, n - 1),
    };
}

fn main() {
    let mut cache = CacheForMoves::new(vec![1, 2]);
    cache.insert_for_n(1, vec![]);
    let result = stairs(&mut cache, 4);
    println!("Found {} possible solutions: ", result.len());
    for solution in result {
        println!("{:?}", solution);
    }
}

这会产生以下编译错误：

error[E0502]: cannot borrow `*cache` as mutable because it is also borrowed as immutable
  --> stairs2.rs:28:18
   |
26 |     return match cache.get_for_n(n) {
   |                  ----- immutable borrow occurs here
27 |         Some(result) => result,
28 |         None => stairs(cache, n - 1)
   |                        ^^^^^ mutable borrow occurs here
29 |     }
30 | }
   | - immutable borrow ends here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0502`.

我不明白为什么它认为我不可避免地在第26行借用cache。我的理解是main创建了一个CacheForMove的实例并拥有该值。它可变地将价值借给stairs函数，所以现在stairs已经可变地借用了这个值。我希望能够在这个可变借用的参考上调用get_for_n和insert_for_n。

Answers that I don't understand yet

这是How can I mutate other elements of a HashMap when using the entry pattern?的副本吗？

在这个SO问题中，OP希望对缓存中的一个密钥进行更新取决于缓存中不同密钥的值。我最终想做到这一点，但在我达到这一点之前我遇到了一个问题。我不是在查看缓存中的其他条目来计算“this”条目。该问题的答案表明，他们需要从缓存中分离出来，从而插入到缓存中，如下所示：

fn compute(cache: &mut HashMap<u32, u32>, input: u32) -> u32 {
    if let Some(entry) = cache.get(&input) {
        return *entry;
    }

    let res = if input > 2 {
        // Trivial placeholder for an expensive computation.
        compute(cache, input - 1) + compute(cache, input - 2)
    } else {
        0
    };
    cache.insert(input, res);
    res
}

但是，我相信我的代码已经从插入中分离出来了，但我仍然遇到编译错误。

即使我调整上面的示例来匹配我的API：

fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
    if let Some(entry) = cache.get_for_n(n) {
        return entry;
    }
    let res = stairs(cache, n - 1);
    cache.insert_for_n(n, res.clone());
    res
}

我仍然得到同样的错误：

error[E0502]: cannot borrow `*cache` as mutable because it is also borrowed as immutable
  --> src/main.rs:29:15
   |
25 | fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
   |                  - let's call the lifetime of this reference `'1`
26 |     if let Some(entry) = cache.get_for_n(n) {
   |                          ----- immutable borrow occurs here
27 |         return entry;
   |                ----- returning this value requires that `*cache` is borrowed for `'1`
28 |     }
29 |     let res = stairs(cache, n - 1);
   |               ^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

error[E0499]: cannot borrow `*cache` as mutable more than once at a time
  --> src/main.rs:30:5
   |
25 | fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
   |                  - let's call the lifetime of this reference `'1`
...
29 |     let res = stairs(cache, n - 1);
   |                      ----- first mutable borrow occurs here
30 |     cache.insert_for_n(n, res.clone());
   |     ^^^^^ second mutable borrow occurs here
31 |     res
   |     --- returning this value requires that `*cache` is borrowed for `'1`

error: aborting due to 2 previous errors

Some errors occurred: E0499, E0502.
For more information about an error, try `rustc --explain E0499`.

这是What is the idiomatic way to implement caching on a function that is not a struct method?的副本吗？

在那个问题中，OP表示他们不愿意使用struct，并且提供的答案使用了unsafe，mutex，lazy_static!，RefCell等的一些组合。

我有相反的问题。我非常愿意使用struct（事实上，我在我原来的问题陈述中使用了一个），但是使用unsafe，mutex，lazy_static!等对我来说听起来更危险或更复杂。

该问题的OP暗示如果我们可以使用结构，那么解决方案将是显而易见的。我想学习那个明显的解决方案。

你是不可变借用它 - 运行get_for_n方法，当返回值超出范围时（即在匹配结束时），它从self借用并释放此借用。您不希望楼梯功能对缓存执行的操作使匹配的值无效。

stairs函数不会使用匹配的值。在原始问题陈述中显示的实现中：

fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
    return match cache.get_for_n(n) {
        Some(result) => result,
        None => stairs(cache, n - 1),
    };
}

我不可避免地借用cache来获取缓存值。如果有值可用，我将其返回（不再递归调用stairs）。如果没有值，我希望None可以复制（即我可以在我的堆栈上拥有自己的None副本;我不再需要在cache中引用任何数据）。在这一点上，我希望能够安全地可变地借用cache来调用stairs(cache, n-1)，因为没有其他借用（可变或不可变）来缓存。

要真正推动这一点回家，请考虑楼梯功能的这种替代实现：

fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
    {
        let maybe_result = cache.get_for_n(n);
        if maybe_result.is_some() {
            return maybe_result.unwrap();
        }
    }
    return stairs(cache, n - 1);
}

在这里，我使用了一对花括号来限制不可变借用的范围。我执行一个不可变的借用来填充maybe_result，并检查它是否是Some。如果是，我打开内部值并返回它。如果没有，我结束我的范围，因此所有借用都超出了范围，现在无效。没有借款了。

然后，我尝试可变地借用cache以递归方式调用stairs。这应该是此时唯一的借用，所以我希望借用成功，但编译器告诉我：

error[E0502]: cannot borrow `*cache` as mutable because it is also borrowed as immutable
  --> src/main.rs:32:12
   |
25 | fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
   |                  - let's call the lifetime of this reference `'1`
26 |     {
27 |         let maybe_result = cache.get_for_n(n);
   |                            ----- immutable borrow occurs here
28 |         if maybe_result.is_some() {
29 |             return maybe_result.unwrap();
   |                    --------------------- returning this value requires that `*cache` is borrowed for `'1`
...
32 |     return stairs(cache, n - 1);
   |            ^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0502`.
rust borrow-checker borrowing
3个回答
0
投票

明确检查None并在不可变借用之前返回：

fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
    if cache.get_for_n(n).is_none() {
        return stairs(cache, n - 1);
    } else {
        cache.get_for_n(n).unwrap()
    }
}

但是我不喜欢两次调用get_for_n()函数

Rust playground link

0
投票

我想我已经搞清楚了，所以记录我的答案以防其他人遇到同样的问题。这编译并运行：

use std::collections::HashMap;

struct CacheForMoves {
    set_of_moves: Vec<usize>,
    cache: HashMap<usize, Vec<Vec<usize>>>
}

impl CacheForMoves {
    fn new(set_of_moves: Vec<usize>) -> CacheForMoves {
        CacheForMoves {
            set_of_moves: set_of_moves,
            cache: HashMap::new()
        }
    }

    fn get_for_n(&self, n: usize) -> Option<&Vec<Vec<usize>>> {
        self.cache.get(&n)
    }

    fn insert_for_n(&mut self, n: usize, value: Vec<Vec<usize>>) {
        self.cache.insert(n, value);
    }
}

fn stairs(cache: &mut CacheForMoves, n: usize) -> Vec<Vec<usize>> {
    return match cache.get_for_n(n) {
        Some(result) => result.clone(),
        None => stairs(cache, n - 1)
    }
}

fn main() {
    let mut cache = CacheForMoves::new(vec![1, 2]);
    cache.insert_for_n(1, vec![]);
    let result = stairs(&mut cache, 4);
    println!("Found {} possible solutions: ", result.len());
    for solution in result {
        println!("{:?}", solution);
    }
}

有两个主要变化：

  1. stairs不再返回&Vec<Vec<usize>>而是返回Vec<Vec<usize>>
  2. 在Some(result)的情况下，我们返回result.clone()而不是result。

2是1的结果，所以让我们关注为什么1是必要的以及它解决问题的原因。 HashMap拥有Vec<Vec<usize>>，因此当最初的实现返回&Vec<Vec<usize>>时，它返回对HashMap拥有的内存位置的引用。如果有人要改变HashMap，比如删除一个条目，因为HashMap拥有Vec<Vec<usize>>，HashMap会得出结论，释放Vec<Vec<usize>>使用的记忆是安全的，我最终会有一个悬空参考。

我只能保证&Vec<Vec<usize>>只要我能保证只要HashMap引用存在就不会改变&Vec<Vec<usize>>，并且因为我将&Vec<Vec<usize>>引用返回给我的调用者，这实际上意味着我需要保证HashMap是永远不可变的（因为我不知道调用者可能会做什么）。

0
投票

将它包装在Rc中是一种可能的解决方案。

Rc是一个“引用计数”指针，使您可以对同一个值进行多次“借用”。当您调用“克隆”方法时，计数将增加。当值被破坏时，计数将减少。最后，如果引用计数达到0，则指针及其“指向”值将被销毁。您可能希望在并发环境中使用Arc（它基本上是一个原子引用计数“指针）或者如果您正在制作一个板条箱，因为它提供了更大的灵活性.Arc将执行与Rc相同的工作，除了计数将是原子地完成。

这样，您的所有权问题将得到解决，而无需复制整个Vec，只需使用另一个指向同一“值”的指针即可。

我也用Option::unwrap_or_else取代了，这是一种更为惯用的解包Option :: Some（T）的方法，或者在Option :: None的情况下懒惰地计算默认值。

use std::collections::HashMap;
use std::rc::Rc;

struct CacheForMoves {
    set_of_moves: Vec<usize>,
    cache: HashMap<usize, Vec<Vec<usize>>>,
}

impl CacheForMoves {
    fn new(set_of_moves: Vec<usize>) -> CacheForMoves {
        CacheForMoves {
            set_of_moves,
            cache: HashMap::new(),
        }
    }

    fn get_for_n(&self, n: usize) -> Option<&Vec<Vec<usize>>> {
        self.cache.get(&n)
    }

    fn insert_for_n(&mut self, n: usize, value: Vec<Vec<usize>>) {
        self.cache.insert(n, value);
    }
}

fn stairs(cache: &Rc<CacheForMoves>, n: usize) -> &Vec<Vec<usize>> {
    cache.get_for_n(n).unwrap_or_else(|| stairs(cache, n - 1))
}

fn main() {
    let mut cache = Rc::new(CacheForMoves::new(vec![1, 2]));
    Rc::get_mut(&mut cache).unwrap().insert_for_n(1, vec![]);
    let result = stairs(&cache, 4);
    println!("Found {} possible solutions: ", result.len());
    for solution in result {
        println!("{:?}", solution);
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.