Rust: Nem tudo é o que parece ser
Engenheiro de Software
Este artigo apresenta uma nova solução ao problema da plataforma Exercism, abordado no artigo anterior, onde irei apresenta-los a uma solução que não utiliza uma estrutura de dados declarada.
Contexto
Em meu artigo anterior, Rust: Estrutura de dados e seu impacto na performance, eu abordei as estruturas de dados Vec e HashSet. Caso você não tenha lido esse artigo veja ao menos a sessão do Contexto, para que você fique ciente do que se trata o exercício que foi abordado, já que esse artigo será a explicação de uma solução mais inteligente.
Após o envio da minha solução utilizando HashSet fui dar uma olhada pelos códigos enviados por outros desenvolvedores ao mesmo exercício, e não pude deixar de notar que havia um código que se repetia inúmeras vezes por página, e é sobre ele que este artigo irá tratar.
Solução
Infelizmente como o código se repete inúmeras vezes por página eu não vou conseguir apontar o autor original, mas já adianto que a pessoa que escreveu esse código é um gênio.
pub fn sum_of_multiples_adapters(limit: u32, factors: &[u32]) -> u32 {
(1..limit)
.filter(|i| factors.iter().any(|&f|{
let result = f != 0 && i % f == 0;
result
}))
.sum()
}
Assim como nossas soluções escritas com Vetor e HashSet, essa versão do código também passa nos testes, mas não tem como deixar de notar que ela além de ser mais enxuta do que as outras, também consegue ser mais rápida, tanto em números de fases grandes quanto pequenos.
Execução
Vamos entender o que está acontecendo nessa nova solução que utiliza o adaptador filter e consome seu resultado através do método any. Para conseguir transmitir esse conhecimento de maneira simples irei passar linha a linha “executando” o código e explicando a teoria ao redor dele, e para isso vamos trabalhar com o próprio exemplo de execução mencionado pelo exercício e exibido no artigo anterior, durante a sessão Contexto, onde o nível da fase terá o valor 20 e a lista de itens será [3, 5].
Range
(1..limit)
O código já inicia criando um Range de 1 a 19 (o valor inicial é inclusivo e o final é exclusivo), através dele podemos pular algumas iterações desnecessárias para obtermos o resultado final, que é a soma da lista de números resultante.
Com isso quero dizer que, em nossos códigos do artigo mencionado na sessão Contexto, nós tinhamos que, após fazer a inserção e verificação dos números que entrariam na lista final, invocar o método iter() para tornar nossa lista final iteravel e chamar o método sum() para consumir esse iterador. Ou seja, nós fazíamos dois loops principais, um para gerar a lista e outro para somar os números dela.
Com o range essa segunda iteração não é necessária, pois criamos e somamos a lista dentro do mesmo loop. Isso pode ser observado nesse benchmark para exemplificar melhor o que eu estou falando.
# OUTPUT
1. Range -> 840ns | Result: 190
2. For ---> 3.25µs | Result: 190
Filter
.filter(|i| factors.iter().any(...))
O adaptador filter realiza a filtragem do iterador range através da closure |i|, utilizado para decidir quais itens serão dropados e quais irão continuar, baseado na comparação passada como parâmetro (se for verdadeiro o valor é mantido, caso seja falso será dropado).
Como objeto de filtragem foi passada uma iteração da lista de &[u32] recebida como parâmetro da função, que possui o valor de [3, 5]. No entanto, sua filtragem depende não apenas da iteração da lista [3, 5], mas também do método any(), que será abordado na sessão seguinte.
Mas para demonstrar a eficiência desse adaptador vamos aos benchmarks. Comecei fazendo uma modificação no benchmark anterior, realizado uma filtragem através do adaptador filter na solução com o range e uma filtragem com um if na solução do for loop, que pode ser encontrado aqui. Também aproveitei para colocar a solução com for loop juntamente com o adaptador filter no lugar do if e os resultados falam por sí só.
# OUTPUT
1. Range ------> 1.33µs | Result: 90
2. For+Filter -> 1.66µs | Result: 90
3. For+IF -----> 2.52µs | Result: 90
A filtragem realizada mantém somente os números pares, e seus tempos demonstram que em um vetor é melhor gerar a lista completa e depois aplicar o adaptador filter do que gerar a lista já filtrada através da cláusula if dentro do for loop. Interessante, não?
Any
.any(|&f|{
let result = f != 0 && i % f == 0;
result
})
O método any é que é o real pulo do gato dentro dessa solução, pois esse método, assim como o adaptador filter, também aplica uma closure |&f| entretanto, ele consome do iterador apenas os itens necessários para determinar a resposta.
Ou seja, quando o item atual que estiver sendo verificado já atender aos requisitos, o restante da lista não será verificada dentro da iteração atual. Caso ainda não esteja claro, aqui está um exemplo:
Se considerarmos que o range está atualmente no número 6, quer dizer que a variável i dentro da cláusula do filter também será 6. Ou seja, iniciaremos o loop na lista [3, 5] que terá seus valores passados a variável f onde são feitas as seguintes verificações:
f != 0=>3 é diferente de zero? Sim6 % 3 == 0=>6 é múltiplo de 3? Sim
Como as verificações retornam verdadeiro, o restante da lista não será verificado para a iteração do loop principal (o que está com o valor 6), ou seja, não será verificado se 5 diferente de zero e se 5 é múltiplo de 6.
Em outras palavras, essa solução pode ter uma lista com 10.000 itens, mas se o primeiro item da lista retornar positivo os demais 9.999 itens não serão verificados por já ter sido validado o número X do range, fazendo com que ele passe para o próximo número.
Extra
Assim como no artigo anterior vocês podem clicar no link: Sum of Multiples - New, onde eu adicionei essa nova versão do código para fins de comparação.
# INPUT
- limit: `10_000`
- factors: `&[2, 3, 5, 7, 11]`
# OUTPUT
1. Filter --> 1.33ms | Result: 39614537
2. HashSet -> 11.13ms | Result: 39614537
3. Vector --> 967.12ms | Result: 39614537