Notas sobre algoritmos

Recentemente, li um artigo do Rob Pyke (um dos criadores do Go e do Unix) sobre suas ideias de como escrever programas em C. Meio que um mini Clean Code, mas escrito em 1989. O artigo trazia ideias sobre como escrever nomes para variáveis e funções, comentários etc - muito do que a gente já conhece sobre código limpo. Porém, de todos esses tópicos, o que mais me chamou atenção foi a parte sobre algoritmos.

De modo geral, eu sempre tento escrever um código que seja fácil de ler e manter, mesmo que isso signifique refatorar várias e várias vezes. Eu acredito muito na frase de Donald Knuth sobre otimização prematura:

Premature optimization is the root of all evil.

A questão que muita gente esquece é o que vem antes dessa frase.

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

Essa é a ideia: focar na otimização onde e quando você realmente precisar. E esse é realmente um dos pontos que Rob Pyke traz em seu artigo: algoritmos sofisticados (no artigo, fancy) nem sempre são a resposta. No geral, a sofisticação do algoritmo tem um custo, seja na complexidade, dificuldade de manutenção e localização de bugs.

Mesmo um algoritmo de complexidade O(n^2), quando utilizado poucas vezes e em quantidades pequenas, já é suficiente. Claro, se necessário, quanto mais otimizado melhor, mas nem sempre é preciso. Um exemplo seria um algoritmo de ordenação com complexidade O(log n), como o QuickSort, comparado com algoritmos mais simples, porém de complexidade exponencial, como o Bubble Sort. Claro que a maioria das linguagens possui algoritmos de ordenação já implementados, mas a ideia ainda vale.

Uma coisa muito importante que o artigo ressalta é a necessidade de sempre mensurar o algoritmo, pois sem dados reais sobre o seu uso, não é possível saber em que local é necessário otimizar.

Além disso, muito mais importante do que a linguagem de programação e o algoritmo utilizado, é a estrutura de dados utilizada. Embora linguagens como JavaScript e Python tenham opções nativas bem específicas no que diz respeito a dados, ainda assim vale a pena saber mais sobre elas. Às vezes, é mais barato percorrer todos os elementos de um array em busca de um item do que utilizar um Map (mesmo o array sendo O(n) e o Map sendo O(1)).

Claro que o elemento estava logo na segunda posição e o array tem tamanho curto. Mesmo assim, acho interessante mostrar a comparação.

Por curiosidade, mesmo procurando o último elemento, o desempenho fica bem próximo:

Se quiser dar uma lida no artigo, pode acessar ele clicando aqui.