A importância dos algoritmos para um engenheiro de software

Estou muito satisfeito por estar a ajudar a renovar as equipas que vão representar a FEUP nos concursos de programação da ACM. Há muitos alunos novos que estão a ver este "mundo" pela primeira vez e foi giro ver a sua reacção no concurso interno que fizemos esta semana :-)

No entanto, apesar deste interesse inicial dos alunos, uma pergunta natural é: porque é que isto é importante? Ou, por outras palavras, porque é que eles hão de despender parte do seu tempo livre a aprender mais sobre algoritmos, estruturas de dados e tudo o resto que está relacionado com os concursos?

Parte da resposta já foi dada noutros sítios. Neste post vou apenas realçar algumas das razões.
Eu sugiro a leitura do tutorial do TopCoder sobre a importância dos algoritmos e o artigo da Academia ONI sobre a análise de algoritmos.

Antes de mais.. o que é um algoritmo?
Um algoritmo pode ser definido como uma sequência de passos que transforma um dado input (um valor ou conjunto de valores) no resultado pretendido - output - sendo este tipicamente um valor ou conjunto de valores.
Na prática, um engenheiro de software gasta grande parte do seu tempo a implementar algoritmos. Para cada parte do projecto de desenvolvimento de software, existem um conjunto de desafios e é necessário definir qual vai ser a abordagem para os ultrapassar. Estes desafios podem ser coisas simples como ler um ficheiro de texto e apresentar a informação ao utilizador ou coisas mais avançadas como o processamento de giga, tera ou mais bytes de dados para determinar alguma estatística.

Análise do tempo de execução de algoritmos
Imaginem que têm este problema: dados N números inteiros, existem 2 números que somados dão um número S?
Uma solução natural é testar todos os pares de números e verificar se a sua soma dá S. Exemplo em C++:

1 2 3 4 5 6 7

bool VerificaPares(int* valores, int N, int soma) { for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) if (valores[i]+valores[j] == soma) return true; return false; }

O código é simples e tudo indica que dá a resposta certa. No entanto, um factor importante na vida real é saber se esta performance chega para as nossas necessidades. Qual é a quantidade máxima de números que este algoritmo suporta se o nosso programa tiver no máximo 1 segundo para executar?

Para responder a esta pergunta, é necessário analisar o tempo de execução do algoritmo apresentado. A notação mais popular para representar o tempo de execução (ou complexidade temporal) é a notação Ó-grande e é expressa em função do tamanho do input. Neste caso, é em função do número N de elementos do array.

Para cada número do array (ciclo i), é verificada a sua soma com todos os outros números (ciclo j). Assim, para cada iteração do ciclo i, o ciclo j tem N-1, N-2, N-3, .., 1, 0 iterações.
O número total de iterações é a soma dos números [0, N-1] que é a soma da conhecida progressão aritmética de passo 1, igual a N*(N-1)/2 = (N² - N) / 2. Na definição da complexidade temporal do algoritmo, só utilizamos o valor mais significativo e ignoramos as constantes. Assim,

• O((N² - N) / 2) = O(N² / 2), ignoramos o factor N porque este é dominado pelo factor N²
• O(N² / 2) = O(N²), ignoramos o factor 1/2 visto que é uma constante.

Deste modo, conseguimos uma definição compacta para a complexidade temporal do algoritmo proposto (ler os links dados para mais detalhes): O(N²). O processo pode parecer complexo ou envolvendo muita matemática mas na verdade é tipicamente muito simples porque ignoramos as constantes e outros factores dominados (e.g. o N acima).

Agora que sabemos qual é o tempo de execução, falta-nos estimar o N máximo para que o programa execute no máximo em 1s. O meu portátil tem um processador com frequência de 2.53 GHz, isto significa que o processador executa cerca de 2.53 * 10⁹ instruções por segundo. No entanto, o processador não está 100% dedicado ao nosso programa e aquilo que programamos é tipicamente traduzido em mais do que uma instrução do processador.

A experiência diz-nos que uma estimativa razoável é considerar que 100 milhões de operações são executadas em 1 segundo. Como o nosso programa tem um tempo de execução O(N²), o nosso programa pode processar √10⁸ = 10000 números em 1s. A tabela seguinte contém algumas estimativas do tempo de execução em função do tamanho do input (ver análise de algoritmos).

Nota: como diz no artigo, estes tempos consideram apenas ciclos que demoram um determinado tempo, ignorando o resto do programa. Daí a diferença de 1s para 0.1s, 1s é uma estimativa mais conservadora.

Exercício para o leitor: a solução apresentada é propositadamente ineficiente. Como fazer melhor do que 2 ciclos encadeados? Isto é, como fazer melhor do que O(N²)?

Impacto na vida real e no meu estágio na Google
Não há necessidade de reinventar a roda nestes posts. Volto a sugerir a leitura dos links referidos para obtenção de mais informação. Existem diversos tipos de algoritmos e conhecimento é poder.
Este conhecimento de determinados algoritmos ou técnicas pode permitir transformar uma ideia que parecia impossível (como vimos acima, um algoritmo poderia demorar centenas de anos ou mais até dar a resposta) numa feature bem real e popular que torna a nossa aplicação melhor do que a concorrência.

Muitos dos problemas dos concursos de programação são apresentados via uma história que pode parecer irrealista. No entanto, os algoritmos usados para resolver estes problemas são úteis para as situações que aparecem na vida profissional de um engenheiro de software.

As skills desenvolvidas ao participar nos concursos de programação são úteis no desenho e implementação de soluções para os desafios do software. Não só a parte dos algoritmos, mas também a capacidade de trabalho sob pressão, debugging e coding skills. Com a experiência destes concursos, e lendo soluções de outros concorrentes se possível (e.g. TopCoder, CodeChef), nós aprendemos a estruturar os nossos algoritmos da forma mais simples possível, resultando tipicamente em código bastante sucinto e eficiente.

Eu já resolvi alguns milhares de problemas online, seja em treino, seja por hobby. Assim, já enfrentei desafios muito diversos e também problemas semelhantes mas com restrições ou enquadramentos diferentes.
Deste modo, o meu cérebro foi treinado ao longo do tempo para analisar e identificar rapidamente quais são os requisitos e as restrições verdadeiramente importantes de diversas situações, seguido-se a identificação da solução mais apropriada para cada situação.
A consequência disto foi estar à vontade durante as entrevistas e conseguir um estágio na Google. Além disso, quer se queira, que não, parte do desenvolvimento de software é pouco desafiante e/ou repetitivo. A experiência adquirida ao resolver este tipo de exercícios permitia-me resolver as minhas tarefas muito rapidamente porque estava (tipicamente) perante problemas (mais fáceis ou mais difíceis) que já tinha enfrentado antes. Daí o ganho na produtividade.
Frequentemente, os meus superiores tinham de me arranjar outros projectos para me manter ocupado ("I have to find something to keep this guy busy"), enquanto que eles tentavam arranjar tempo para me fazerem code reviews :-)