Veja além do óbvio
Acredito que se você já tem um tempo na área de programação, seja como estudante, ou entusiasta, já deve ter ficado claro que um mesmo problema apresentado para 2 pessoas diferentes, certamente produzirá 2 algoritmos diferentes para resolvê-lo.
Um problema possui um espectro de soluções.
Porém, dentro dos caminhos que você pode escolher, há sempre alguns que vão performar melhor que outros. Em um mundo aonde os recursos não são tão escassos como já foram, muitas vezes nos deixamos levar pela primeira ideia que nos vem a mente, sem nos preocuparmos se nossa decisão terá algum impacto, dado o cenário em que o problema surgiu.
No entanto, quando falamos de grandes escalas, a preocupação com recursos e tempo de resposta passam a ser parte fundamental até mesmo do SLO (Service Level Objective) do seu produto, bem como da experiência do usuário.
Como exemplo dessa reflexão, dias atrás me deparei com uma situação em que eu tinha uma lista de emails e uma lista de usuários aonde cada elemento possuía um campo email, e eu precisava identificar nesta lista de usuários a diferença com a lista de emails.
Inicialmente, resolvi assim:
const filterWithSome = (emails, users) => {
return emails.filter(
(email) => !users.some((user) => user.email === email)
);
};
Veja que não há nenhum problema no algoritmo. Ele está retornando da lista de emails, todos aqueles que não estão contidos na lista de usuários, o que é exatamente a solução do problema.
Porém, o cenário de sucesso desse algoritmo sempre atinge o pior custo de operação, pois suponha que na lista de usuários você possui 10 mil valores, e na lista de emails há 15 mil (5 mil a mais que são emails não contidos na lista de usuários). Isso significa pelo menos para 5 mil emails, a lista de usuários será percorrida por completo até determinar que o email não está presente ali. Isso sem contar os demais emails que farão um caminho similar, porém serão encontrados em algum ponto da lista de usuários.
O que significa que nosso pior caso é igual ao número de emails X número de usuários, ou seja O(n * m) em notação Big O.
Após alterar um pouco o algoritmo, cheguei em uma implementação que focava em reduzir esse custo. Veja:
const filterWithSet = (emails, users) => {
const usersEmailsSet = new Set(users.map((user) => user.email));
const difference = emails.filter((email) => !usersEmailsSet.has(email));
return difference;
};
Essa abordagem está mapeando a lista de emails do array de usuários e o transformando em um Set, ao utilizar o método filter na lista de emails, ao invés de percorrer todos os itens da lista de usuários, agora com uma única operação de leitura é possível determinar se o email está presente no Set, ou não (veja mais sobre como Set funciona na documentação oficial). O que significa que esse algoritmo agora tem um custo de O(n).
Para verificar se a mudança de fato obteve algum impacto, desenvolvi o seguinte cenário de teste:
const { faker } = require('@faker-js/faker');
const emails = [];
const users = [];
Array.from({length: 50000}, (_, i) => i).forEach(()=> {
const email = faker.internet.email({provider: 'fake'});
emails.push(email);
users.push({email});
});
Array.from({length: 10000}, (_, i) => i).forEach(()=> {
const email = faker.internet.email({provider: 'fake'});
emails.push(email);
});
const filterWithSome = (emails, users) => {
return emails.filter(
(email) => !users.some((user) => user.email === email)
);
};
const filterWithSet = (emails, users) => {
const usersEmailsSet = new Set(users.map((user) => user.email));
const difference = emails.filter((email) => !usersEmailsSet.has(email));
return difference;
};
console.time("filterWithSome");
filterWithSome(emails, users);
console.timeEnd("filterWithSome");
console.time("filterWithSet");
filterWithSet(emails, users);
console.timeEnd("filterWithSet");
Como pode ver, a configuração do teste gera 50 mil emails e os atribui para a lista de emails e para a lista de usuários; Na sequência, adiciono mais 10 mil emails para a lista de emails, o que significa que o array de email terá 10 mil valores diferentes da lista de usuários.
Após executá-lo, esse foi o resultado do tempo de execução para cada algoritmo, dado o cenário apresentado:
filterWithSome: 5.999s
filterWithSet: 9.168ms
Observe que a diferença é absurda, e enquanto a filtragem usando o Set custou aproximadamente 9 milisegundos, a outra abordagem custou quase 6 segundos.
A parte de todo o lado técnico apresentado, a reflexão que fica é: "Estou vendo além do óbvio?".
Nem sempre você vai precisar otimizar algo para obter performance, mas quando o momento chegar, exercite o entendimento do problema, e realmente conheça como a linguagem que você usa funciona e quais os limites de cada recurso.
Um forte abraço!