Como criar algoritmos rápidos por padrão (sem otimização prematura)
Thiago Brito
7 de Agosto de 2020 4 minutos de leitura

Existem técnicas simples que, se bem utilizadas, fazem com que você seja capaz de analisar e identificar pontos de melhoria em seus algoritmos muito rapidamente.

Antes de mais nada é importante discutirmos sobre um dos maiores males de um desenvolvedor que é a otimização prematura.

Esta é uma daquelas armadilhas que fazem com que a gente se divirta por horas e horas otimizando algo que no final não vai ter impacto algum no produto final.

Alguns exemplos simples são:

  • gastar horas otimizando uma área do código que não é representativa no tempo total gasto do algoritmo
  • otimizar algo de uma forma tão complexa e tão cheia de gambiarras que faz com que o código fique impossível de fazer manutenção
  • fazer unit tests que são baseados em tempo de execução tendem a ser um inferno pois podem se tornar instáveis dependendo do estado do ambiente em que são executados
  • simplesmente otimizar algo que está dentro de um tempo razoável, como otimizar a execução de 2 horas para 1 hora de uma rotina que é executada durante a madrugada sem impacto negativo algum para o sistema ou usuário
  • Eu poderia dar muitos outros exemplos simples que mostram que a otimização, quando má executada pode trazer problemas na manutenção do código ou ser a mais pura perda de tempo mesmo.

    Porém, existe algo interessante neste tema: caso você não tenha nenhuma noção de como desenvolver seus algoritmos e criar eles estruturalmente de forma errada, vai ser muito difícil de otimizar eles sem fazer uma grande mudança que poderá levar a um enorme e custoso refactoring.

    Depois que aprendi a fazer uma análise de algoritmo usando uma técnica simples de Big(O), passei a ter noção de como estruturar meu código de forma que ele mantenha uma velocidade aceitável de acordo com a quantidade de informações que ele processa neste momento e com a previsão de crescimento dos dados no futuro.

    Usando Big(O) para identificar pontos de melhoria

    A grande sacada é ao menos identificar como seu algoritmo se comporta com algumas análises simples. Lembrando que não vou representar todos os tipos de algoritmos, mas isso já te dá uma idéia do caminho que pode seguir:

  • O(1): É aquela rotina que não possui nenhum laço de repetição, ordenação de dados e nada. O tempo de processamento e o consumo de memória é o mesmo independente dos parametros passados. Por exemplo:
  • def function(x, y):
        return x + y
    
  • O(log n): Este é o tipo de algoritmo que está muito atrelado a estrutura de dados de árvore binária. A jogada aqui é ir entrando dentro dos seus dados, sempre buscando o menor caminho possível até encontrar o valor que você deseja.
  • O(n): Neste caso o processamento ou consumo de memória aumenta de forma linear a quantidade de dados de entrada que existem. Uma dica simples é, se existe um único laço de repetição dentro da rotina, na maioria das vezes ela é O(n). Por exemplo:
  • def function(x):
        for i in range(x):
            print(i)
    
  • O(n log n): Este é o típico que representa o melhor tipo de algoritmo de ordenação que pode ser feito.
  • O(n²): Aqui a coisa já fica um pouco mais complexa, neste caso o processamento ou consumo de memória aumenta exponencial ao número de dados que existem dentro da função. Aqui já estamos entrando em um padrão clássico que devemos buscar fugir. Por exemplo:
  • def function(x, y):
        for i in range(x):
            for l in range(y):
                print(i + l)
    

    Escolhendo sua estrutura de dados para ser mais fácil de ser manipulada

    Escolher bem a estrutura de dados de acordo com a situação do seu algoritmo faz uma enorme diferença na velocidade e consumo de memória do seu algoritmo.

    Treinar e entender estes conceitos te traz uma intuição e entendimento enormes que com certeza vão te diferenciar (muito) de outros desenvolvedores. É aqui que a brincadeira fica séria de verdade.

    Seguem alguns exemplos:

  • Arrays para acesso aos dados é O(1) mas para busca é O(n). Sendo assim, se você está construindo um algoritmo que exija muita busca dos dados e você já possui um identificador único do mesmo, prefira um dicionário (também conhecido como hash table)
  • Se você possui um algoritmo em que você precisa inserir ou remover dados constantemente no início ou fim da estrutura, não use um array, prefira uma queue ou uma stack
  • Sempre considere a possibilidade de usar NoSQL para fazer buscas simples de dados que precisa de grande velocidade. Eles são muito eficientes e para buscas de dados O(1), quando você já tem o ID da informação e não precisa de muita gravação, é excelente (isso me lembra uma hash table?)
  • Veja, estes são apenas alguns exemplos que fazem uma enorme diferença no momento em que você estiver criando seu algoritmo.

    A forma como você escolhe a sua estrutura de dados, como você vai criar sua função e como elas se relacionam faz com que seu algoritmo, desde de o momento da criação tenha uma performance muito maior.

    Quando é o melhor momento de usar a análise Big(O) ?

    A não ser em casos extremos, normalmente não é uma boa ideia criar Unit Tests para validar a velocidade de uma determinada função.

    Profilling é reativo, somente depois que você desenvolveu uma parte significativa do código será possível usar ele para identificar pontos de melhoria e pode ser que você não tenha uma visão real do que está acontecendo. Mas esta é uma ferramenta que você sempre pode usar para identificar pontos para fazer refactoring futuro.

    Pela minha experiência, o melhor a fazer é aplicar estes conceitos durante o processo de criação e revisão de código e tentar espalhar este conhecimento dentro da equipe. Somente analisando o codigo e discutindo muito bem como vamos estruturar os dados é que vamos evitar desperdícios de tempo e memória.

    Estes conceitos também são bastante importantes, por exemplo, para identificar em quais pontos devemos inserir sistemas de cache.

    Este é o método mais barato que eu conheço, em suma, este conhecimento faz com que o time sempre esteja atento a fazer a coisa certa do jeito certo desde o início do desenvolvimento. Apesar de não ser a forma mais fácil é o que paga maiores dividendos ao longo do tempo.

    Como aprender e praticar isso?

    Fazendo algoritmos diariamente, sabe aqueles algoritmos que são solicitados em entrevistas de emprego, competições ou até mesmo alguns professores de faculdade?

    Então, eles são os melhores para você praticar isso. Bons lugares são o HackerHank, Leetcode e outras bases de exercícios em que você pode treinar todos os dias, é algo que vai fazendo seu cérebro ficar cada dia melhor e você entender um pouco mais sobre como isso funciona.

    Obviamente, para resolver estes exercícios é importante que eles sejam performaticos e não tenham problemas de consumo de processamento e memória, sendo assim, você só vai ser capaz de resolver estes exercícios sabendo escolher os melhores algoritmos e os dados para cada um.

    Com certeza este é um daqueles exercícios que realmente ajudam seu cérebro a identificar padrões e aplica-los ao longo do seu dia profissionalmente.

    E aí? Já resolveu seu algoritmo hoje?