Обновление изменяемого HashMap в цикле while

Я пытаюсь реализовать алгоритм Каргера в Rust и столкнулся с проблемой при попытке обновить изменяемую хэш-карту в цикле while.

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

Я пробовал отлаживать и печатать значения карты, но последовательность событий не имеет для меня смысла.

use itertools::Itertools;  // 0.8.0
use rand::seq::{IteratorRandom, SliceRandom}; // 0.6.5
use std::collections::HashMap;

fn contract_edge(graph: &mut HashMap<i32, Vec<i32>>, num_trials: i32) {
    let mut count = 0;

    while graph.len() > 2 && count < num_trials {
        // clone graph so I can mutate graph later
        let imut_graph = graph.clone();

        // choose random node
        let from_value = imut_graph
            .keys()
            .choose(&mut rand::thread_rng())
            .unwrap()
            .clone();
        let values = imut_graph.get(&from_value);
        let to_value = values
            .unwrap()
            .choose(&mut rand::thread_rng())
            .unwrap()
            .clone();

        let from_edges = imut_graph[&from_value].iter().clone();

        // accessing to_value in imut_graph gives error here later
        let to_edges = imut_graph[&to_value]
            .iter()
            .clone()
            .filter(|&x| *x != from_value && *x != to_value);

        let new_edges = from_edges.chain(to_edges);

        // since I am mutating the graph I thought the next time is is clone it would be updated?
        graph.insert(from_value, new_edges.map(|v| v.clone()).collect());
        graph.remove(&to_value);
        for (_key, val) in graph.iter_mut() {
            *val = val
                .iter()
                .map(|v| if v == &to_value { &from_value } else { v })
                .unique()
                .cloned()
                .collect();
        }
        count += 1;
    }
}

Когда я пытаюсь получить доступ к карте, я получаю сообщение об ошибке «Элемент не найден», но удаленные ключи не должны существовать в векторных значениях в этой точке.

Я убежден, что это то, чего я не понимаю в (не)изменяемости в Rust.

Как вы думаете, что делает метод clone? Как вы думаете, почему необходимо «клонировать граф, чтобы я мог позже изменить граф»?

Shepmaster 22.05.2019 02:04

Немного сложно ответить на ваш вопрос, потому что он не включает минимальный воспроизводимый пример. Ваш код компилируется, но не включает код, демонстрирующий проблему, например пример main. Нам будет намного легче помочь, если вы попытаетесь воспроизвести свою ошибку на Детская площадка ржавчины, если это возможно, в противном случае в совершенно новом проекте Cargo, тогда редактировать ваш вопрос, чтобы включить дополнительную информацию. Есть Советы по MCVE для Rust, которые вы можете использовать, чтобы уменьшить исходный код для публикации здесь. Спасибо!

Shepmaster 22.05.2019 02:05

@Shepmaster Спасибо за внимание, я думаю, что этот клон делает неизменяемую копию карты? Это необходимо, потому что когда я пытаюсь получить доступ к содержимому карты, а затем изменить его, я получаю сообщение об ошибке. Насколько я понимаю, я должен клонировать теперь мутированную карту, поэтому значения в клоне должны быть обновлены?

Thomas C 22.05.2019 15:12

@ThomasC, у вас была возможность посмотреть предоставленный ответ? Чем это не соответствует вашим требованиям?

Peter Varo 27.05.2019 11:39
Почему Python в конце концов умрет
Почему Python в конце концов умрет
Последние 20 лет были действительно хорошими для Python. Он прошел путь от "просто языка сценариев" до основного языка, используемого для написания...
0
4
1 161
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Я не совсем уверен, чего вы пытаетесь достичь здесь, но на основании того, что я вижу выше, то есть вы хотели бы изменить свой оригинал graph (потому что вы передаете это как изменяемое заимствование в свою функцию) и что у вас нет возвращаемого значения, и что ваш вопрос касается изменения хэш-карты — я предполагаю, что вы хотите, чтобы изменения отражались в исходном HashMap. Так почему же вы клонируете его в первую очередь тогда?

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

Проблема, с которой вы сталкиваетесь, возникает из-за того, что на каждой итерации вы клонируете оригинал graph, а не свой клон imut_graph, то есть на каждой итерации вы создаете новый HashMap, который затем мутируете, затем вы начинаете новый цикл, и вы все еще проверяя длину исходного, а затем снова клонируете исходный.

Итак, у вас есть два варианта:

use std::collections::HashMap;

fn mutated(map: &mut HashMap<i32, Vec<i32>>) {
    map.insert(1, vec![4, 5, 6]);
}

fn cloned(map: &HashMap<i32, Vec<i32>>) -> HashMap<i32, Vec<i32>> {
    let mut map = map.clone();
    map.insert(2, vec![7, 8, 9]);
    map
}

fn main() {
    let mut map = HashMap::new();
    map.insert(0, vec![1, 2, 3]);

    println!("{:?}", cloned(&map));

    mutated(&mut map);
    println!("{:?}", map);
}

Что даст вам:

{0: [1, 2, 3], 2: [7, 8, 9]}
{0: [1, 2, 3], 1: [4, 5, 6]}

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

Thomas C 29.05.2019 14:12

Не беспокойтесь, я рад, если мой ответ чем-то помог!

Peter Varo 29.05.2019 15:04

Другие вопросы по теме