TechTips

A otimização de código é uma tarefa muitas vezes deixada de lado, e, muito pior, feita de formas erradas muitas vezes por inexperiência do programador, tendo como resultado programas que funcionam bem em testes com um volume pequeno de dados e que demoram horas conforme o volume de dados aumenta.

Para entender os passos necessários para otimizar seu código de uma forma que tenha um bom resultado prático sem comprometer a qualidade do código, deve-se entender alguns conceitos importantes:

1. Quando otimizar.
2. Como reconhecer qual parte do código toma mais tempo.
3. E o que fazer para diminuir o tempo tomado por essas partes do código.

Vou elaborar o primeiro item hoje, e deixar os próximos dois para artigos futuros.

Quando Otimizar

Donald Knuth escreveu, em 1974, a já famosa e gasta frase: "Devemos esquecer das pequenas eficiências, cerca de 97% do tempo. Otimização prematura é a raiz de todo o mal". Em seguida, ele elabora que não se deve ignorar os 3% restantes, mas apenas após que eles forem identificados.

Mais que isso, diz que a experiência universal de programadores (incluindo a minha), é que após utilizar ferramentas para medir a performance do código, você percebe que o que as tentativas de adivinhar quais são esses trechos críticos geralmente são falhas. É fácil perceber que tempo gasto otimizando partes do código que não são críticas para a performance é uma perda de tempo, e acabam tendo um impacto negativo quando se considera o tempo que será levado para depurar e manter esse código, agora mais complexo por otimizações desnecessárias.

O retorno da otimização costuma seguir o Principio de Pareto, que postula que apenas 20% do código é responsável por cerca de 80% da performance. Dessa forma, mesmo que se diminua pela metade o tempo levado por um trecho específico de código, se ele só influencia em 1% no tempo total de determinado processo, você só teve 0.5% de ganho de performance. Por outro lado, ao identificar um trecho que leva 30% do tempo, qualquer melhoria de performance nele terá um retorno 30 vezes maior. Na prática, vejo porcentagens ainda maiores que essa, acentuando ainda mais a importancia de localizar corretamente os trechos que levam mais tempo, conhecidos como gargalos, ou bottlenecks, se preferir um informatiquês mais elaborado.

Isso quer dizer, que, na prática, ao escrever código, evite tomar qualquer decisão no impacto de performance que ela vai ter. Decisões como usar uma ou outra função para realizar determinada tarefa devem ser tomadas com base nos méritos de legibilidade e mantenabilidade do código, muito acima de qualquer suposta diferença de performance entre elas. Não deixe a intuição de que algum ponto será um gargalo influenciar essa decisão (lembre-se, intuições geralmente são desbancadas por medições de performance). Qualquer escolha errada nesse ponto é facilmente adequada nas fases de medição e otimização.

O que isso não quer dizer, em contrapartida, é que se deve ignorar a performance na hora de planejar a solução que vai ser implementada, antes da codificação. É importante saber o que está sendo implementado e qual a complexidade dessa solução. Deve-se estimar a quantidade de itens que o código deve ser capaz de processar, e adequar a complexidade do algoritmo e estruturas de dados escolhidas para obter uma performance apropriada a esse número. Uma das soluções na etapa de diminuir o tempo tomado por determinado gargalo é substituir o algoritmo por um mais eficiente, mas tal substituição costuma ser trabalhosa e demanda mais trabalho que um planejamento adequado tomaria.

Complexidade de Algoritmos

A complexidade de algoritmos é uma medida da escalabilidade de um algoritmo. De quanto trabalho ele precisa fazer para resolver o problema conforme o número de itens aumenta. Existe uma forma padrão de analisar e representar a complexidade de algoritmos, que é a notação Big-O (raramente traduzida para Grande-O). Para determinar a complexidade de um algoritmo, conta-se o número de operações que ele faz para cada item, onde operação pode ser comparações, trocas, leituras de disco, etc. Em seguida, é determinada uma expressão que representa essa quantidade. Uma complexidade O(n), ou linear, representa que o número de operações é constante e proporcional ao número de itens na lista. O(n²), ou quadrática, mostra a proporção que o número de operações cresce conforme o número de itens aumenta.

É muito mais fácil de entender essa representação graficamente:

A figura representa o número de operações efetuadas por dois algoritmos hipotéticos, um O(n) e o segundo O(n²). Algumas características importantes:

• É fácil de observar a falta de escalabilidade do segundo algoritmo. Conforme o número de itens aumenta, o número de operações aumenta muito rapidamente.
• Não é um gráfico de f(x) = n e g(x)=x², apesar que esse seria um exemplo igualmente válido (e mais simples). A expressão mostrada pela notação O não é exatamente o número de operações que vão ser executadas, mas sim uma representação de como esse número muda em relação à quantidade de itens processados. Não existe O(n + 10) nem O(10n). Ambos seriam representados por O(n). Dois algoritmos podem ter a mesma complexidade mas um efetuar mais operações, ou o mesmo número de operações e levar um tempo maior que o outro (se a operação for mais demorada).
• O algoritmo mais complexo pode levar menos tempo que o menos complexo. O tempo extra gasto no caso mais simples pode ser a geração de uma tabela de pesquisa, por exemplo, que pode levar mais tempo do que a busca por força em um número pequeno de itens. Supondo que no gráfico acima a operação efetuada pelos dois algoritmos seja equivalente, o mais complexo vai ser mais rápido até um pouco mais de 150 itens. Se o número de itens vai ser baixo (por exemplo, processar as janelas abertas em um editor de imagens), a segunda opção pode ser a mais adequada. Se o número for alto (ou desconhecido), deve-se tomar uma extrema atenção na complexidade do algoritmo que será usado.

Sabendo desses detalhes, fica mais fácil determinar a complexidade de um algoritmo qualquer. Um exemplo seria a busca de um item em uma lista desordenada. Em pseudocódigo:

resultado = -1
de i := 1 até Lista.Count
  se Lista[i] = Item
    resultado = i
retorne resultado

A operação que está sendo contada é a comparação. O número de operações é sempre igual ao número de itens na lista, claramente O(n). Uma otimização óbvia reduz o número de comparações:

de i := 1 até Lista.Count
  se Lista[i] = Item
    retorne i
retorne -1

Nesse novo exemplo, no melhor caso, o item procurado é o primeiro da lista, sendo feita apenas uma comparação. No pior caso, não é encontrado, sendo feitas n comparações. O complexidade analisa o pior caso, ainda mantendo esse algoritmo como O(n). Perceba que se forem feitas diversas buscas em uma lista, o número médio de comparações será entre 1 e N, e cresce proporcionalmente a N, mantendo a característica de complexidade.  A média seria 3n/4 para uma lista não ordenada e n/2 em uma lista ordenada, caso tenha curiosidade.

Um algoritmo para encontrar todos os itens duplicados em uma lista poderia ser escrito assim:

de i := 1 até Lista.Count
  de j := 1 até Lista.Count
    se (i <> j) e (Lista[i] = Lista[j])
      Duplicados.Adiciona(i, j)

Este seria um exemplo de O(n²). Para cada item, todos os outros itens são percorridos. Otimizações simples, como no exemplo anterior, podem ser limitar a iteração no loop interno de 1 até N-1, e no loop interno para a faixa i + 1 até N, que diminuem o número de comparações, mas não alteram a complexidade. O número de iterações ainda é proporcional ao quadrado do número de itens.

Algumas medidas Big-O comuns são as seguintes, em ordem crescente de complexidade:

• O(1), ou constante - O tempo do algoritmo independe do número de itens. Claramente a melhor opção quando N pode crescer muito. É a complexidade em inserção e busca em Tabelas Hash
• O(log n), ou logarítmico - É proporcional ao logaritmo de n, que cresce em uma taxa muito mais lenta que n. É uma opção bem adequada quando não é possível utilizar O(1). A busca binária em uma lista ordenada tem essa complexidade.
• O(n), ou linear - É o exemplo que já vimos de uma busca de força bruta em uma lista qualquer. Começa a ser um problema quando seu código tem que tratar um número indeterminado de itens.
• O(n²), ou quadrática - O número de operações é proporcional ao quadrado do número de itens. O algoritmo intuitivo de ordenação, a ordenação por inserção, tem essa complexidade. Deve ser evitada praticamente para qualquer número de itens que não estejam sobre estrito controle.
• O(n!), ou fatorial - Proporcional ao fatorial de n, ou seja, cresce extremamente rápido. Mesmo que as operações sejam rápidas, rapidamente com o crescimento de n o tempo tomado pelo algoritmo passará a ser excessivamente grande (horas, dias, ou mais). A força bruta de uma senha tem essa essa complexidade, ou a solução do problema do caixeiro viajante.

Conclusão

A complexidade de algoritmos é um ponto importante para ser considerado na escolha do design ou das estruturas usadas na codificação, evitando introduzir problemas de escalabilidade. Para isso, é importante saber estimar a complexidade de um código e reconhecer a complexidade de inserções e buscas em estruturas de dados comuns. Apesar disso, deve-se evitar a tentação de intuitivamente deduzir quais serão os gargalos no momento da codificação e tomar decisão baseadas nessa intuição, prezando a legibilidade acima de tudo. É muito mais fácil localizar e corrigir gargalos depois de ter o código escrito do que localizar e corrigir problemas de estilo.

Se você é novo por aqui, não deixe de assinar o feed RSS ou notificações por email. Não perca novos artigos!

• Deixe um comentário... (6)