Running Sum of 1d Array

Running Sum of 1d Array

Vinicius Lucchesi
Vinicius Lucchesi

Engenheiro de Software
12/04/2024

Este artigo visa demonstrar que a versão lógica mais simples e fácil de implementar pode não ser a melhor, quando medimos sua velocidade, assim como sua facilidade no entendimento e manutenibilidade do software.

Introdução

Como já fazia um certo tempo desde que eu não programava em Rust decidi não ficar parado e treinar um pouco das minhas skills, sendo assim, resolvi iniciar na plataforma LeetCode, e seguindo seu tutorial de como a plataforma funciona fui apresentado ao problema número 1480 chamado Running Sum of 1d Array.

Esse problema é bem simples, ele consiste em recebermos um Input de um array e devolvermos outro array, porém para cada item dentro do nosso array devemos somar os itens anteriores.

Exemplo

  • Entrada: [1, 2, 3, 4]
  • Saída: [1, 3, 6, 10]

Ou seja, olhando nosso array, item a item, teremos que realizar os cálculos [ 1 , 1+2 , 1+2+3 , 1+2+3+4 ].

Solução Óbvia

pub fn running_sum(nums: Vec<i32>) -> Vec<i32> {
    let mut result: Vec<i32> = Vec::new();
    let mut aux: i32 = nums[0].into();
    
    for (idx, num) in nums.iter().enumerate() {
        match idx {
            0 => { result.push(*num) }
            _ => {
                let sum = num + aux;
                aux = sum;
                result.push(sum);
            }
        }
    }
    result
}

Aqui eu fiz a primeira coisa que me veio a cabeça:

  1. Criar um vetor chamado result que irá armazenar o resultado da soma dos itens do vetor passado como parâmetro;
  2. Instanciar uma variável chamada aux, que receberá o valor da soma, para manter o resultado entre uma iteração e outra, iniciando com o valor do primeiro item da lista;
  3. Montar um For Loop que extraia a posição do item no vetor, através do método enumerate;
  4. Criar uma verificação dentro do loop para somar o item atual com o item anterior e adicioná-lo no vetor que será retornado, com exceção do primeiro item, que já será adicionado na lista final;
  5. E por fim retornar o vetor resultante;

Observando a proposta do exercício e a velocidade de execução do código, que com o vetor [3,1,2,10,1] passado como parâmetro, nos retornou uma média de ~ 620ns era de se esperar que a maior parte das pessoas parasse por aí. Submetesse o exercício para a plataforma e já pulasse para o próximo.

Mas se você ainda está lendo é porque quer entender como a solução abaixo (que você provavelmente já deve ter batido o olho) funciona.

Solução mais elaborada

pub fn running_sum(nums: Vec<i32>) -> Vec<i32> {
    nums.into_iter()
        .scan(0, |state, x| {
            *state += x;
            Some(*state)
        })
        .collect()
}

Logo de cara já podemos nos maravilhar com a simplicidade da função, aqui o propósito da função runnig_sum está muito mais claro do que antes. Mas não se preocupe, irei explicar linha a linha, destrinchando o que está acontecendo com nosso vetor nums passado como parâmetro.

Into_iter

nums.into_iter()

O operador into_iter retorna um iterador que se apropria da coleção e retorna itens por valor, ou seja, ao utiliza-lo fazemos com que a posse dos itens passe da coleção para o consumidor, eliminando a coleção no processo.

Porém, mesmo que a coleção nums esteja sendo consumida pelo iterador into_iter não há a necessidade de instanciar um vetor vazio para armazenarmos nosso vetor resultante, já que estamos retornando um valor para cada item do vetor e concatenando todos novamente em uma coleção.

Scan

.scan(0, |state, x| {
    *state += x;
    Some(*state)
})

O método scan recebe dois argumentos:

  1. Estado Inicial: sendo representado pelo valor 0 no início da chamada ao método, e também na closure através do nome de variável state, se tratando de uma variável mutável;
  2. Elemento atual: sendo representado pela variável x na closure;

Para cada número dentro do vetor nums será feito o cálculo *state += x que soma o valor da variável state, que inicia em zero, ao valor do elemento atual.

Por fim retornamos o valor da variável *state dentro de uma option Some(), pois o método scan finaliza a iteração caso suas validações retornem None.

Ou seja, a medida que o nosso vetor nums está sendo consumido, o método scan já está construindo outro iterador, que será transformado em um vetor de inteiros assinados de 32 bits através do método collect.

Collect

.collect()

Por fim temos o método collect que consegue inferir o tipo Vec<i32> requisitado pelo rust, por ser o tipo retornado pela função.

Caso fosse necessário fazer a conversão de maneira explícita poderíamos optar por utilizar a seguinte sintaxe collect::<Vec<i32>>();.

Conclusão

Nossa Solução mais elaborada nos da uma visão muito mais clara e intuitiva a respeito do funcionamento da função running_sum, facilitando a manutenção futura do código caso sua “regra de negócio” mude.

Assim como nos artigos técnicos anteriores, também realizei alguns benchmarks utilizando o Rust Playground - Running Sum of 1d Array, onde podemos observar uma leve vantagem de tempo a favor da solução mais elaborada, mas não representa um ganho grande de performance.

Mesmo assim, é animador ver que horas e horas de pesquisa, tentativas e testes foram recompensados com um código mais limpo e performático do que o inicial, que vale lembrar, também resolvia o problema.

← Artigos