多维向量借用

Question

我正在尝试实现一个编码练习，但是我遇到了一个关于多维向量和借用的墙。

代码可以在这个操场中访问，但我将在这里添加一个代码片段，以供参考：

type Matrix = Rc<RefCell<Vec<Vec<String>>>>;

/// sequence -> target string
/// dictionary -> array of 'words' that can be used to construct the 'sequence'
/// returns -> 2d array of all the possible combinations to create the 'sequence' from the 'dictionary'
pub fn all_construct<'a>(sequence: &'a str, dictionary: &'a [&str]) -> Matrix {
    let memo: Rc<RefCell<HashMap<&str, Matrix>>> = Rc::new(RefCell::new(HashMap::new()));
    all_construct_memo(sequence, dictionary, Rc::clone(&memo))
}

fn all_construct_memo<'a>(
    sequence: &'a str,
    dictionary: &'a [&str],
    memo: Rc<RefCell<HashMap<&'a str, Matrix>>>,
) -> Matrix {
    if memo.borrow().contains_key(sequence) {
        return Rc::clone(&memo.borrow()[sequence]);
    }

    if sequence.is_empty() {
        return Rc::new(RefCell::new(Vec::new()));
    }

    let ways = Rc::new(RefCell::new(Vec::new()));
    for word in dictionary {
        if let Some(new_sequence) = sequence.strip_prefix(word) {
            let inner_ways = all_construct_memo(new_sequence, dictionary, Rc::clone(&memo));

            for mut entry in inner_ways.borrow_mut().into_iter() { // error here
                entry.push(word.to_string());
                ways.borrow_mut().push(entry);
            }
        }
    }

    memo.borrow_mut().insert(sequence, Rc::clone(&ways));
    Rc::clone(&ways)
}

代码不编译。

问题：

1. 这感觉太复杂了。有更简单的方法吗？ 1.1对于Matrix类型，我试着用Vec<Vec<String>>勉强过活，但这并没有让我走得太远。--如何正确地编码2d向量，允许不使用额外的板条箱而进行可更改和共享？ 1.2。有更好的方式传递备忘录对象吗？
2. 不完全理解这里的编译器错误。你能帮我吗？

error[E0507]: cannot move out of dereference of `RefMut<'_, Vec<Vec<String>>>`
  --> src/lib.rs:31:30
   |
31 |             for mut entry in inner_ways.borrow_mut().into_iter() { // error here
   |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ move occurs because value has type `Vec<Vec<String>>`, which does not implement the `Copy` trait

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

谢谢!

Answer 1

2d vecs工作正常，对于像您这样的锯齿状数组，您的实现是正确的。您的问题源于对Rc和RefCell不必要的使用。因为您调用的方式，一个单一的，可变的引用将工作。

考虑以下修改后的示例：

type Vec2<T> = Vec<Vec<T>>;

fn all_constructs<'a>(sequence: &'a str, segments: &[&'a str]) -> Vec2<&'a str> {
    let mut cache = HashMap::new();
    all_constructs_memo(sequence, segments, &mut cache)
}

fn all_constructs_memo<'a>(
    sequence: &'a str,
    segments: &[&'a str],
    cache: &mut HashMap<&'a str, Vec2<&'a str>>
) -> Vec2<&'a str> {
    // If we have the answer cached, return the cache
    if let Some(constructs) = cache.get(sequence) {
        return constructs.to_vec();
    }
    // We don't have it cached, so figure it out
    let mut constructs = Vec::new();
    for segment in segments {
        if *segment == sequence {
            constructs.push(vec![*segment]);
        } else if let Some(sub_sequence) = sequence.strip_suffix(segment) {
            let mut sub_constructs = all_constructs_memo(sub_sequence, segments, cache);
            sub_constructs.iter_mut().for_each(|c| c.push(segment));
            constructs.append(&mut sub_constructs);
        }
    }
    cache.insert(sequence, constructs.clone());
    return constructs;
}

它是相同的，摘录了四个差异：

1.)我删除了所有的Rc和RefCell。只有一个Hashmap引用

2.)我没有使用all_constructs_memo("", ...) -> Vec::new()，而是在迭代器if *segment == sequence中添加了一个分支，以便以这种方式测试单个段匹配。

3.)我写的是Vec2而不是Matrix

(4) strip_suffix而不是strip_prefix，仅仅因为在vecs的末尾添加比添加到前端更有效。

这里有一个操场链接，其中包含对非回忆录参考实现https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=1b488aafda6466629c17c8a7de8f3e42的测试