Porque aprender Algoritmos?

Esta é uma das matérias que são dadas na faculdade e, ao menos no meu caso, em que eu já programava a um bom tempo, eu não dei a atenção a ela como deveria.

Conforme vamos evoluindo na carreira, acabamos assimilando e aprendendo de forma orgânica como criar algoritmos que resolvam nossos problemas. Porém, não necessariamente eles tem a melhor performance possível. 

Aprender como integrar estruturas de dados e algoritmos da maneira correta faz com que nossos algoritmos não apenas sejam mais rápidos, mas eles também tendem a ser mais simples ao longo do tempo.

A grande dificuldade

Normalmente os desenvolvedores lidam com algoritmos em alguns momentos da sua vida: 

Quando estão estudando: neste caso, eles não possuem experiência suficiente para entender onde aplicar os conceitos e tendem a ficar muito na base teórica.

Quando passam por um processo seletivo: com experiência ou não, é normal o mercado avaliar os candidatos solicitando que resolvam um determinado desafio. Em muitos casos, este desafio é a criação de um algoritmo que irá resolver uma determinada tarefa dentro de uma janela de tempo.

E aqui entra o grande desafio: é normal até mesmo para desenvolvedores experientes, não ter um estudo profundo e principalmente a prática na identificação de padrões para resolução destes tipos de problemas. 

Veja bem, passamos a carreira inteira analisando problemas dos clientes, criando telas, gerenciando banco de dados, mas dificilmente precisamos criar um algoritmo que identifica uma palindrome, inverte uma string, ordena strings.

Analisando a performance de um algoritmo

Big (O)

Esta é uma notação matemática usada para classificar o comportamento de uma função de acordo com os seus argumentos respondendo a pergunta que indica qual a tendência de consumo de tempo e memória quando os argumentos crescem ou diminuem.

Exemplos principais:

O(1): É a forma mais rápida de execução, é quando o consumo da função não é alterado pelos seus argumentos

O(n): Quando a função cresce de forma linear aos argumentos recebidos

O(n²): Quando a função cresce de forma quadrática aos argumentos recebidos

O(log n): Quando a função cresce de forma logarítmica aos argumentos recebidos

Dicas de otimização simples que você pode usar agora

É sempre interessante dar uma olhada em análises de complexidade de algumas funções principais da linguagem.

Complexidade das funções do Python

Complexidade das funções em JavaScript

Complexidade dos Algoritmos

Removendo itens de uma lista

Sempre que for necessário fazer uma remoção de diversos itens em uma determinada lista, você pode varrer toda a lista e ir removendo cada item. 

Porém,  ao fazer isso iterando por cada item e chamando a função remove para cada item que for par vamos ter uma performance de O(n²). Isso acontece pois haverá uma busca no remove que é executada junto com a busca que identifica se o item é par ou impar.

Veja o exemplo abaixo:

def remove_odd_items_using_remove():
    my_list = list(range(100))
    for item in my_list:
        if item % 2 != 0:
            my_list.remove(item) 
    return my_list

Pensando na criação de uma forma mais otimizada, podemos criar uma outra lista somente com os itens que são considerados impares. Desta forma, podemos executar o algoritmo com uma performance de O(n).

def remove_odd_items_creating_another_list_simple():
    my_list = list(range(100))
    result = []
    for item in my_list:
        if item % 2 == 0:
            result.append(item)
    return result
Com o objetivo de deixar ele um pouco mais rápido, podemos utilizar os próprios recursos da linguagem para esta 
situação.
def remove_odd_items_creating_another_pythonic():
    my_list = list(range(100))
    return [item for item in my_list if item % 2 == 0]

Ao compararmos a execução de cada um dos algoritmos usando a biblioteca timeit, temos os seguintes resultados:

Utilizando a função remove tornando o algoritmo O(n²): 67 segundos

Criando uma nova lista somente com os números impares O(n): 26 segundos

Criando uma nova lista usando uma técnica mais otimizada do Python O(n): 19 segundos

Fazendo busca de dados com O(1)

Esta é uma técnica importante que pode definir inclusive qual tipo de banco de dados deverá ser utilizado em sua aplicação.

Por exemplo, você tem um número de gravações baixo na base de dados e, ao mesmo tempo, é necessário fazer buscas no mesmo com uma frequência elevada, mas a partir de uma chave específica. Nestas situações você pode considerar utilizar bancos de dados NoSQL, pois uma busca a partir de uma chave específica pode ser efetuada com a performance de O(1) e não O(n).

Apesar de este tipo de dado trazer algumas características importantes como elaborar bem quais chaves devem ser utilizadas para a busca, traz um resultado bastante eficiente em diversas situações.

Sendo assim, vamos fazer um exemplo de busca de dados de forma linear, como é feito em bancos de dados relacionais normal:

my_list = list(range(100))
def find_item_simple():
    for item in my_list:
        if item == 50:
            return True
E agora vamos fazer uma busca através da pesquisa pela chave do item a ser encontrado, conforme abaixo:
my_dict = dict((key, True) for key in list(range(100)))
def find_item_using_dict():
    return 50 in my_dict

Antes de mais nada, para deixar uma comparação mais justa, veja que eu separei o processo de carregamento dos bancos de dados, isso é feito pois o que estamos fazendo uma análise apenas do tempo de busca dos dados.

Agora vamos comparar o tempo de execução dos dois algoritmos de busca que trazem o mesmo resultado, mas usam técnicas diferentes:

Busca linear usando lista normal O(n): 4 segundos

Busca por chave usando dicionário O(1): 0.2 segundos

Veja que o tempo de execução do segundo algoritmo é cerca de 20 vezes mais rápida do que o primeiro, ou seja, uma simples técnica pode trazer uma velocidade surpreendente de execução.

Dicas simples em entrevistas

A primeira coisa que você deve ficar bom é descobrir que estes problemas possuem padrões, ou seja, quanto melhor for a sua capacidade de identificar estes padrões, mais rapidamente você será capaz de resolver estes problemas.

Para melhorar esta capacidade, você deve antes de tudo buscar praticar, somente a prática, resolvendo uma série de exercícios fará com que você consiga ser mais efetivo na resolucão dos problemas. Eu sugiro uma pratica diária, resolvendo ao menos um exercício, obviamente quanto mais melhor.

Identificação de palindromes/reverter uma string usando ponteiros

Uma palindrome é uma palavra que continua sendo a mesma mesmo quando ela é invertida. Seguem alguns exemplos:

radar, civic, "socorram me subi no onibus em marrocos".

Veja que no caso de frases, como no último exemplo, devem ser desconsiderados espaços.

Veja como podemos resolver este problema utilizando dois ponteiros:

def is_palindrome(str):
    right = len(str) - 1
    for left in range(len(str)):
        if left == right:
            return True
        if str[left] == ' ':
            continue
        while str[right] == ' ' and right > left:
            right -= 1
        if str[left] != str[right]:
            return False
        right -= 1

Na situação acima, utilizamos um ponteiro que é posicionado no início do texto e outro que é posicionado no final do texto. Ele vai fazer uma varredura completa comparando letra por letra até que os ponteiros se encontrem e, nesta situação é considerada uma palindrome. 

Caso alguma letra seja diferente, a função deverá sair imediatamente indicando que não é uma palindrome.

Este algoritmo é considerado O(n) pois ele precisa apenas de uma passagem em todos os dados para que a execução seja concluída quando considerado uma palindrome. Caso a string não seja, ele deverá parar antes do ponteiro chegar no meio da string.

Dynamic Programming

Programação dinamica é apenas uma otimização quando temos um processo de recursão. Sempre que vemos uma recursividade, uma função que chama ela mesma, nós podemos fazer um processo de otimização usando Dynamic Programming.

A idéia é muito simples, guardamos o resultado de subproblemas, desta forma nós não precisamos ficar recalculando eles com frequência. É a forma mais simples de reduzir o tempo de execução exponencial para linear.

Vamos brincar com o caso Fibonacci:

def fib_recursive(k):
    if k <= 1:
        return k
    return fib_recursive(k - 1) + fib_recursive(k - 2)

Veja que estamos usando recursividade e, sempre que a função é chamada ela deve fazer o calculo dos números anteriores.

def fib_dynamic(k):
    f = {}
    f[0] = 0
    f[1] = 1
    for i in range(2, k):
        f[i] = f[i - 1] + f[i - 2]
    return f[k-1]

Já usando dynamic programming os valores já previamente calculados são guardados em memória e não precisam ser reprocessados mais tarde.

Agora analisando os resultados, podemos verificar em alguns testes quanto maior o valor de N mais discrepante será o tempo de execução das duas funções, este é um fator extremamente importante que deve ser levado em conta. Para os testes, rodamos as duas funções de forma sequencial com os valores de N em 10, 4 e 3.

 Execução da função usando recursividade O(n^k): 80 segundos

Execução da função usando Dynamic Programming O(k): 8.9 segundos

Mais uma vez podemos entender que, usando técnicas bastante simples, somos capazes de otimizar em muitas vezes a execução de um algoritmo sem necessariamente aumentar a complexidade do mesmo. 

Sempre que possível, esteja sempre estudando novas técnicas e principalmente praticando com pequenos probleminhas para se manter ativo, ajudar o seu time entregando melhor performance e se preparando para a próxima vaga.

Caso queira aprender com mais profundidade esta e outras técnicas de programação que trazem um ganho exponencial na performance dos seus projetos entre no site do AlgoMania e ganhe 10% de desconto usando o cupom de desconto LIVE005.