Início / coding / Perguntas / 79252843
Accepted
Ahmet Yazıcı
Asked: 2024-12-05 05:56:21 +0800 CST

Mesclando dois Vec<(u32, Vec<u8>)> sem chaves duplicadas

  • 772

Tenho 2 vetores que são do tipo Vec<(u32, Vec<u8>)>. Quero mesclar esses dois vetores e quero que o resultado tenha chaves únicas. No caso de chaves iguais, o 2º vetor deve sobrescrever o primeiro.

Aqui está minha tentativa de resolver esse problema:

pub fn merge(old_v: Vec<(u32, Vec<u8>)>, new_v: Vec<(u32, Vec<u8>)>) -> Vec<(u32, Vec<u8>)> {
    let mut new_map = HashMap::<u32, Vec<u8>>::from_iter(old_v);

    new_map.extend(new_v);
    new_map.into_iter().collect()
}

Isso funciona, mas o problema é que esses vetores carregam dados muito grandes, potencialmente de 500 KB a 1 MB de dados, com 1000s de entradas (especialmente old_v). E esse método cria bastante memória, considerando que eu chamo esse método com bastante frequência em meu aplicativo.

Há alguma maneira de melhorar a eficiência desse método? Estou OK em fazer mutações no local.

rust

1 respostas

  1. Best Answer

    Se as entradas forem pré-classificadas, você pode mesclar as duas entradas como iteradores, coalescer na chave e selecionar apenas a última das entradas com chaves correspondentes. Isso pode ser um pouco melhor, substituindo uma O(1)operação de caso médio por elemento, com sobrecarga constante moderada e localidade de memória ruim, por uma que seja estritamente O(1)com sobrecarga constante baixa e localidade de memória boa.

    Exemplo aproximado de uso da itertoolscaixa para evitar reinventar a roda:

    use itertools::Itertools; // 0.13.0

pub fn merge(old_v: Vec<(u32, Vec<u8>)>, new_v: Vec<(u32, Vec<u8>)>) -> Vec<(u32, Vec<u8>)> {
    old_v.into_iter()
        .merge_by(new_v, |(k1, _), (k2, _)| k1 <= k2)
        .coalesce(|a, b|
            if a.0 == b.0 {
                Ok(b)
            } else {
                Err((a, b))
            }
        ).collect()
}

    Link do Rust Playground

    Como eu disse, isso pressupõe que as entradas sejam classificadas na chave fornecida e se comportará mal se não forem. Você pode receber o Vecs como mutável, e .sort_by_key(|(k, _)| *k)para ambos ( demonstração do Rust Playground ) antes de fazer o resto do trabalho (e .sort_by_keydeclara explicitamente que se as entradas já estiverem classificadas, o trabalho é linear, não padrão O(n log n)). Mas se as entradas não forem classificadas, você provavelmente fará mais trabalho do que sua HashMapsolução ao executar O(n log n)a classificação completa.

    Assumindo que a entrada classificada não pode ser assumida como o caso, o que você tem parece ótimo. Você assume a propriedade das entradas, usando IntoIterator(implicitamente ao consumir as entradas, explicitamente ao converter de volta para o resultado), então você está realizando movimentos puros. Sua sobrecarga de memória incremental é apenas para memória adicional com base no que está armazenado em linha nas tuplas (a u32e o pequeno punhado de ponteiros Vec's são implementados em termos de que são esvaziados conforme você constrói o HashMapa partir do Vecs antes que o Vecs seja completamente esvaziado e o armazenamento subjacente liberado), você não está copiando nenhum dos Vecs internos.

    O melhor que posso ver para melhorá-lo para entradas não classificadas seria evitar armazenar o Vecs interno, então você só armazena as chaves para verificação de exclusividade e realiza menos movimentos (reconhecidamente baratos) mantendo o primeiro item visto imediatamente, descartando as duplicatas imediatamente na identificação sem movê-las. itertoolsajuda aqui também, e o código é muito simples, mas esconde um HashSetsegredo para realizar a uniquificação, então requer alguma memória auxiliar:

    use itertools::Itertools; // 0.13.0
use itertools::chain;

pub fn merge(old_v: Vec<(u32, Vec<u8>)>, new_v: Vec<(u32, Vec<u8>)>) -> Vec<(u32, Vec<u8>)> {
    // new_v comes first because first value seen is kept, and the rest are discarded
    chain!(new_v, old_v).unique_by(|(k, _)| *k).collect()
}

    Link do Rust Playground

    Com qualquer uma das soluções, você pode se beneficiar de retornar o próprio iterador (usando impl Iterator<(u32, Vec<u8>)>para evitar verbosidade), em vez de um new Vec. Se o seu chamador precisar de um Vec, ele collectmesmo pode fazê-lo. Se ele quiser apenas iterar os resultados, você pode evitar o custo de memória do new Vece o atraso para começar o processamento, processando e descartando conforme avança.

    • 1

relate perguntas