Normalizando listas para otimizar buscas em JavaScript

#javascript #beginners #performance #ptbr

Um pouco de contexto

Tendo ensinado pessoas que estão iniciando nas carreiras de programação, tem alguns "vícios" que conseguimos identificar que sempre aparecem e podem gerar problema quando precisamos de um pouco mais de performance.

Em JavaScript, talvez o mais constante deles seja um excesso no uso de listas, principalmente quando precisamos buscar informações dentro delas. Normalmente isso não é um problema (quando estamos rodando em localhost😅), mas à medida que os sistemas crescem isso pode se tornar um grande problema de performance, principalmente se estivermos falando de ambientes que podem ter baixo poder de processamento e necessidade de processar grandes listas (React Native tô olhando pra você!)

Existem algumas práticas que a gente pode usar pra melhorar nossa vida nessas horas. As que eu mais gosto são o uso do Set e a normalização das nossas estruturas de dados, que é o que vamos falar nessa postagem.

Nosso exemplo

Nesse contexto, sempre tento passar para o pessoal iniciante a ideia de normalizar listas para que possamos encontrar informações de forma mais otimizada. Vamos supor que estamos trabalhando em um sistema de lojas online onde é necessário implementar um carrinho de compras. Além disso, também é possível adicionar itens mais de uma vez através de um campo de quantidade. Inicialmente, podemos representar o carrinho como uma lista de produtos:

const carrinho = [
    { id: 1, nome: 'Açucar 1kg', quantidade: 1 },
    { id: 2, nome: 'Tempero', quantidade: 1 },
    { id: 3, nome: 'E tudo que há de bom', quantidade: 6 }
];

Exemplo de lista representando um carrinho de compras

Em seguida, para adicionar itens ao carrinho, precisamos identificar se um item já está ou não presente, para que possamos incrementar a quantidade. Podemos pensar em uma função de adição da seguinte forma:

function adicionarItem(item) {
    const { id, nome } = item;

    const index = carrinho.findIndex(itemAtual => itemAtual.id === id);

    // Já está presente
    if (index >= 0) {
        carrinho[index].quantidade++;   
    } else {
        carrinho.push({ id, nome, quantidade: 1);
    }
}

Função de adicionar item ao carrinho

Da mesma forma, também precisamos verificar se o item já existe na hora de remover, para que possamos decrementar a quantidade ou remover do carrinho caso a quantidade se torne 0:

function removerItem(item) {
    const { id } = item;

    const index = carrinho.findIndex(itemAtual => itemAtual.id === id);

    if (index >= 0 && carrinho[index].quantidade > 1) {
        carrinho[index].quantidade--;
    } else {
        // Remove o item caso seja o último presente no carrinho
        carrinho.splice(index, 1);
    }
}

Função de remover item ao carrinho

As funções de adicionar e remover acima funcionam como esperado, entretanto, a operação de adicionar e remover será provavelmente a mais comum que o usuário da sua aplicação realizará. Pensemos em um carrinho de compras de um supermercado por exemplo, nosso carrinho pode chegar a ter mais de 100 produtos e cada produto ainda pode ter diferentes valores de quantidade.

Além disso, outro requisito que podemos precisar é determinar se um item já está presente no carrinho. Podemos escrever uma função pra isso:

function presenteNoCarrinho(id) {    
    const index = carrinho.findIndex(item => item.id === id);
    return index >= 0;
}

Função para saber se um item está ou não presente no carrinho

Agora imagine que, na tela de escolha dos produtos da sua aplicação, você precise indicar na sua UI que determinado item já está presente no carrinho. Utilizando a função acima, perceba que teremos que usar o método findIndex, que itera sobre o carrinho, para cada item da sua loja! Temos então um for de for, ou o famoso O(N²) para os amantes de complexidade de algoritmos. Dependendo de onde nossa aplicação estiver rodando, podemos ter aí um problema de performance. Se eu fosse você não duvidaria da velocidade que um usuário pode adicionar e remover itens do carrinho.

Normalizando

Para resolver o problema de performance criado pela nossa implementação, além de facilitar o entendimento do código, podemos normalizar a lista que representa o carrinho para que não precisemos utilizar o método .findIndex() sempre que for necessário operar sobre a lista.

Normalizar para o nosso contexto significa transformar a lista em um objeto no formato de dicionário. Assim, operações de busca podem ser feitas com apenas uma única chamada, ao invés de um loop para iteração.

Nota: Para que seja possível normalizar, os itens da lista necessariamente precisam de uma chave única que os identifiquem, como um ID do banco, por exemplo.
O nosso objeto de carrinho normalizado pode ser representado da seguinte forma:

// Antes, como array
const carrinho = [
    { id: 1, nome: 'Açucar 1kg', quantidade: 1 },
    { id: 2, nome: 'Tempero', quantidade: 1 },
    { id: 3, nome: 'E tudo que há de bom', quantidade: 6 }
];

// Depois de normalizar
const carrinho = {
    1: { id: 1, nome: 'Açucar 1kg', quantidade: 1 },
    2: { id: 2, nome: 'Tempero', quantidade: 1 },
    3: { id: 3, nome: 'E tudo que há de bom', quantidade: 6 }
}

Comparação de carrinho utilizando lista e com estrutura normalizada

Com a estrutura do nosso carrinho normalizada, além de mais rápidas, o código das operações de adicionar, remover e verificar se já existe ficam bem mais legíveis! Podemos até mostrar a implementação em um único snippet :)

function adicionarItem(item) {
    const itemAtual = carrinho[item.id];

    if (itemAtual) {
        itemAtual.quantidade++;   
    } else {
        carrinho[itemd.id] = item;   
    }
}

function removerItem(item) {
    const itemAtual = carrinho[item.id];

    // Tentando remover um item que não existe no carrinho? Deu ruim.
    if (!itemAtual) return;

    if (itemAtual.quantidade === 1) {
        delete carrinho[item.id];
    } else {
        itemAtual.quantidade--;   
    }  
}

function presenteNoCarrinho(id) {
    return !!carrinho[id];   
}

Comparação de carrinho utilizando lista e com estrutura normalizada

Podemos ver como a função de verificar se um item já existe no carrinho fica simples. Precisamos apenas verificar se um item com o id informado existe no objeto do carrinho e converter o valor para um boolean utilizando negação dupla: !!carrinho[id] (evita retornar o objeto inteiro). Fora isso, as funções de adicionar e remover itens do carrinho não mais precisam iterar sobre a lista de itens, melhorando a performance O(1) e a legibilidade do código.

Conclusão

Na próxima vez que você precisar utilizar uma lista para representar seus dados, pense se você precisará realizar operações sobre essa lista. É bem comum trabalharmos com listas de objetos retornadas de um banco relacional, então sempre teremos um identificador único e poderemos normalizar os dados para melhorar nossa vida ao ver aquele código 6 meses depois quando estiver dando um problema de IndexOutOfBoundsException porque não normalizamos nossa lista. Se você nunca teve um problema parecido, é só questão de tempo.