Question

Исходное описание проблемы

Я пытаюсь написать функцию, которая может как читать, так и записывать из кэша, но я сталкиваюсь с проблемой, когда компилятор говорит, что я не могу одновременно и непостоянно, и постоянно занимать кеш.

Я прочитал https://doc.rust -lang.org / book / ch04-02-reference-and-loaning.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`.

Я не понимаю, почему он считает, что я непременно заимствую cache в строке 26. Я понимаю, что main создает экземпляр CacheForMove и владеет этим значением. Он передает значение функции stairs, и теперь stairs получает значение. Я ожидал, что смогу вызвать как get_for_n, так и insert_for_n по этой заимствованной ссылке.

Ответы, которые я пока не понимаю

Является ли это дубликатом Как можно изменить другие элементы HashMap при использовании шаблона ввода? ?

В этом вопросе SO ОП хочет, чтобы их обновление для одного ключа в кэше зависело от значения другого ключа в кэше. В конце концов, я хочу сделать это, но у меня возникла проблема, прежде чем я достигну этой точки. Я не смотрю на другие записи в кеше, чтобы вычислить «эту» запись. Ответы на этот вопрос говорят о том, что им нужно будет разделить получение из кэша от вставки в кэш следующим образом:

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`.

Является ли это дубликатом Каков идиоматический способ реализации кэширования для функции, которая не является методом struct? ?

В этом вопросе SO OP заявляет, что не хочет использовать struct, а в предоставленных ответах используется некоторая комбинация unsafe, mutex, lazy_static!, RefCell и т. Д.

У меня противоположный вопрос. Я совершенно готов использовать struct (и на самом деле я использую его в своей первоначальной постановке задачи), но использование unsafe, mutex, lazy_static! и т. Д. Звучит гораздо опаснее или сложнее для я.

ОП этого вопроса подразумевает, что если бы мы могли использовать структуру, решение было бы очевидным. Я хотел бы узнать это очевидное решение.

Вы неизменны, одолжив его - запустить метод 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`.

Nebu Pookins · Answer 1 · 28 апреля 2019

Я думаю, что я понял это, поэтому записываю мой ответ на случай, если кто-то застрянет с той же проблемой.Это компилирует и запускает:

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);
    }
}

Есть 2 основных изменения:

stairs больше не возвращает &Vec<Vec<usize>> и вместо этого возвращает Vec<Vec<usize>>
В случае 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 неизменен навсегда (поскольку я понятия не имею, что может делать вызывающий абонент).

Fodil · Answer 2 · 28 апреля 2019

Упаковка в Rc является возможным решением.

Rc - это указатель с «подсчетом ссылок», который позволяет вам иметь несколько «заимствований» для одного и того же значения. Количество будет увеличено, когда вы вызовете метод "клон". Когда значение будет уничтожено, количество будет уменьшено. И, наконец, если счетчик ссылок достигает 0, указатель и его «остроконечное» значение уничтожаются. Возможно, вы захотите использовать Arc в параллельной среде (это, в основном, указатель с атомным подсчетом ссылок) или если вы создаете ящик, так как он дает большую гибкость. Arc будет выполнять ту же работу, что и Rc , за исключением того, что подсчет будет сделан атомарно.

Таким образом, ваша проблема владения будет решена, не копируя весь Vec, а просто имея еще один указатель на то же «значение».

Я также заменил использование Option :: unwrap_or_else , что является более идиоматическим способом развернуть Option :: Some (T) или лениво вычислить значение по умолчанию в случае Option :: ни один.

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);
    }
}

Niall Moore · Answer 3 · 26 апреля 2019

Проверка для 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 детская площадка

Как написать функцию ржавчины, которая может как читать, так и записывать в кеш?

Исходное описание проблемы

Ответы, которые я пока не понимаю

Является ли это дубликатом Как можно изменить другие элементы HashMap при использовании шаблона ввода? ?

Является ли это дубликатом Каков идиоматический способ реализации кэширования для функции, которая не является методом struct? ?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 3 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Как написать функцию ржавчины, которая может как читать, так и записывать в кеш?

Исходное описание проблемы

Ответы, которые я пока не понимаю

Является ли это дубликатом Как можно изменить другие элементы HashMap при использовании шаблона ввода? ?

Является ли это дубликатом Каков идиоматический способ реализации кэширования для функции, которая не является методом struct? ?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 3 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы