Complexidade em Notação Grande-O: conhecê-la irá permitir uma otimização mais bem direcionada de seu código
Você já se deparou com algum código que performava de um jeito um tanto suspeito? Ou então, mesmo após testar algum código em diversas ferramentas de performance (que confronta diferentes algoritmos), você ficou sem entender o porquê de determinado código ser tão lento?
Tudo isto pode ter a ver com a complexidade qual o código possui. E saiba, que por baixo de um código "chique", pode estar se escondendo uma futura dor de cabeça.
Um pequeno grande problema
const emptyArray = [...new Array(10000)];
const newArray = emptyArray.reduce((accumulator, _, index) => {
const a = index;
const b = (a * 2) - 1;
const c = a + b;
return [
...accumulator,
{ a, b, c }
];
}, []);Olhando para o código acima, você consegue identificar algum problema? Dica: em especial dentro do bloco do método reduce.
Antes de te dar a resposta, tente realizar alguns experimentos:
- Envolva o trecho anterior de código com
console.timeeconsole.timeEnd. Algo como:
console.time('Test');
// insert the previous code here
console.timeEnd('Test');2. Agora, faça repetidos testes incrementando o tamanho original do array. Faça pouco a pouco, de 10000 em 10000. Observe com cuidado o tempo de execução.
Disclaimer: quão maior essa entrada, maiores os riscos de seu navegador “travar” (ele irá tentar processar em segundo plano, mas ainda sim existe a chance de você não conseguir usar o navegador enquanto o processamento é realizado).
E aí, identificou alguma pista?
Aos mais atentos, o tempo de execução aumenta de uma forma bem diferente do incremento feito no tamanho da coleção original. Enquanto os testes alterando o tamanho da entrada da coleção foram feitos de forma linear, o tempo de execução ocorre numa ordem denominada quadrática.
A ciência da computação (e matemática) consegue nos explicar isso sob a ótica da notação grande-O (big O notation), e esse algoritmo acima pode ser descrito como O(n²).
Alguns de vocês podem discordar da constatação anterior, e defender de que o reduce é um método de complexidade O(n), ou seja, que executa de maneira linear em contraste com o tamanho da entrada. Exemplo: se uma coleção de 10 itens é processada em 10ms, uma de 50 itens será processada em 50ms, uma de 1000 em 1000ms e assim em diante. E sim, realmente o reduce funciona desta forma.
Mas então, qual o problema?
- De forma extremamente resumida: o problema está no
returncriando uma coleção a cada iteração, e usandospread(os...).
E qual a melhor forma de resolver o algoritmo em questão?
- Apenas uma operação de
push, direto no acumulador, dentro de cada iteração, é o suficiente. Ficando assim:
const emptyArray = [...new Array(100000)];
const newArray = emptyArray.reduce((accumulator, _, index) => {
const a = index;
const b = (a * 2) - 1;
const c = a + b;
accumulator.push({ a, b, c });
return accumulator;
}, []);Outra forma de escrever o mesmo algoritmo é renunciar ao reduce em favor de um forEach, e alimentar um array criado previamente, também com push. Assim:
const emptyArray = [...new Array(100000)];
const newArray = [];
emptyArray.forEach((_, index) => {
const a = index;
const b = (a * 2) - 1;
const c = a + b;
newArray.push({ a, b, c });
})Imagino que alguns dos leitores poderão torcer o nariz para as duas últimas sugestões de solução, e tentar argumentar em favor de legibilidade ou uma suposta simplicidade. E, novamente, tendo a concordar em certo nível, mas apenas nos casos quais conhecemos o tamanho da entrada de dados. É o famoso:
Tudo me é lícito, mas nem tudo me convém.
Portanto, caso você trabalhe com dados de tamanhos desconhecidos, ou ainda sim, tenha ciência de que irá iterar em coleções muito grandes, é mais do que interessante que você tenha o devido cuidado com o seu algoritmo. Em especial com métodos que iteram em coleções e declarações explícitas de laços de repetições. É muitíssimo interessante ficar de olho em recursividade nesses pontos, ou aninhamento de iterações.
Há também alguns métodos que podem aparentar serem inofensivos, mas que carregam uma complexidade em si, como por exemplo, um Array.shift(), que é O(n), pois, ao remover o primeiro elemento de um Array, fará com que a engine realoque todas as demais posições para o índice imediatamente anterior.
Nossa experiência
À primeira vista pode parecer que o algoritmo do início deste texto seja aleatório, mas ele realmente fez parte de um problema presente em uma de nossas telas mais importantes, e durante muito tempo acabamos por "desligar" determinadas funcionalidades para que a tela ficasse minimamente usável para grandes clientes (aqueles com as grandes coleções de dados).
A diferença que vale a menção, é que nosso erro acontecia com Object, mas da mesma forma: criando um objeto a cada iteração do reduce, e utilizando o spread para fazer um shallow clone do que havia sido (re)criado na iteração anterior.
A correção no nosso pior cenário nos ajudou a otimizar este processamento de ~37s para ~3ms.
A confiança foi tamanha, que ao darmos a notícia aos nossos stakeholders, incluso o time de produto, eles imediatamente ativaram as funcionalidades que antes estavam desligadas para esta gama de clientes.
Mas, como descobrimos o problema?
Antes, se me permitem: muitos de nós (incluso eu) não sabíamos da complexidade que o operador spread carrega. Até então, era algo "bonitinho" de uma das atualizações do ES, e, para nós, ele faria algum tipo de "reaproveitamento" do objeto antigo, e de forma rápida.
Ledo engano.
Dado isto, apenas olhar para o código passou a não fazer sentido em nosso caso, pois não conseguíamos entender onde estávamos falhando. Então tivemos que olhar de uma forma mais cuidadosa para o ferramental que os browsers nos oferecem, em especial o Chrome (ou algum dos browsers que utilizam da mesma engine), em específico o painel de Performance (não confundir com o Performance insights, que pode ajudar em vários outros pontos de melhoria do front-end, também).
Ao carregar uma tela, ou executar algum fluxo, sendo gravado pelo painel de Performance, nós temos alguns agrupadores (ou threads), onde o que nos interessava naquela situação era a Main. E é aqui onde conseguimos identificar este e outros pontos de "gargalo" do nosso código Javascript. Coisas que, em teoria, deveriam executar na casa de milissegundos, estavam consumindo alguns segundos (ou vários dependendo da função).
E foi repetindo o mesmo código, com diferentes tentativas é que fomos entender com o que estávamos lidando. Foi uma abordagem atípica talvez, mas foi o loop mais prático de aprendizado que conseguimos abordar naquele momento.
Após conseguirmos termos ganhos tão "inacreditáveis", precisávamos entender em baixo nível com o que estávamos lidando.
Da importância em entender a complexidade do código
Com o problema resolvido, ainda restava entender o que corrigimos, e como poderíamos repetir tamanha otimização e com tão pouco código, em situações similares.
Usando o Google, começamos a elaborar algumas pesquisas apoiadas em termos como "iterações", "criar novo objeto", "spread" etc., para encontrar alguém que pudesse nos explicar. E então achamos o artigo abaixo, artigo este que também compartilhamos com nosso time de engenharia na época.
Foi onde finalmente tivemos um holofote sobre a questão de complexidade, mas diretamente envolvida no uso do spread (que sendo justo, foi uma consequência razoável em se criar uma coleção a cada iteração).
E, coincidentemente, no último mês teve um artigo de uma otimização extremamente parecida em uma library de tabela do Tanstack. O colaborador que identificou e corrigiu o problema nos traz a perspectiva dele (e como ele realizou esse processo de investigação):
Conclusão
De forma algum este artigo é uma sugestão para parar de escrever seu código com sintaxes novas, ou abandonar o spread e o reduce.
Entretanto, realmente vale a provocação quanto ao que ainda é "novo", ou estranho a você como desenvolvedor. Sempre tenha interesse em entender o que ocorre de fato na engine Javascript com determinadas coisas que você pode acabar usando apenas "pelo hype".
Em contrapartida, se você trabalha com código que lidará com uma quantidade desconhecida de dados, ou no outro extremo, sabendo que lidará com dados na casa de dezenas, centenas de milhares, milhões etc., sempre tenha um olhar redobrado em como lidar com estes dados, para que assim você evite equívocos como estes.
Dica bônus
Apesar de ser muito interessante que nós, desenvolvedores, saibamos a complexidade qual o nosso código possui, realizei alguns testes com o ChatGPT em sua última versão (4, no momento de publicação deste artigo), e a ferramenta de IA tem tido uma taxa de acerto assustadoramente alta.
Este mesmo algoritmo, se questionado na versão 3.5, possui uma resposta (e explicação) equivocada. Algo que já não ocorre na versão 4, tendo uma explicação mais do que satisfatória.
É um fato curioso, e que pode ser um "game changer" no nosso futuro como desenvolvedores, pois até então era tido como um "tabu" (algo difícil, ou impossível, de ser feito, até então) uma ferramenta automatizada que saiba calcular a complexidade em notação grande-O (por favor, não confundam com complexidade ciclomática, algo viável e que existe aos montes, sendo o Sonar um dos grandes exemplos).
Feedbacks
Sintam-se bem-vindas(os) a comentar, fazer uma crítica construtiva, e/ou apontar qualquer equívoco neste artigo.
Até a próxima e obrigado! 👋
Oportunidades na Syngenta Digital
Por aqui na Syngenta Digital estamos sempre em busca de melhorarmos nossos softwares, e otimizá-los a fim de melhorar a experiência de nossos usuários.
Se vocês tiverem interesse nesse tipo de desafio e na Syngenta Digital, fiquem de olho nas vagas que temos disponíveis aqui:
Links úteis
- https://www.youtube.com/watch?v=KWM5wxlDuis (Guide to Chrome’s performance profiler)
- https://www.youtube.com/watch?v=zXBaLEGv0iM (Complexidade de Algoritmos em 3 simples passos utilizando a Notação Big O.)
