Tecnologia. Inteligente.

Algum tempo atrás, durante o desenvolvimento de um dos nossos produtos, surgiu a necessidade de codificarmos uma daquelas features recorrentes em vários sistemas de computação: um estimador de tempo, que daria ao usuário uma previsão de quanto tempo uma tarefa levaria para ser concluída.

A reação intuitiva da grande maioria das pessoas é acreditar que um estimador de tempo é algo fácil, talvez até óbvio de ser feito. Quem nunca riu das estimativas de tempo fora da realidade fornecidas por vários programas, bem como de suas barras de progresso “loucas” que avançam aos saltos de forma bizarra e às vezes até retrocedem? Elas soam engraçadas em parte porque estão executando de maneira esdrúxula uma tarefa que deveria ser fácil. Afinal, um computador é uma máquina determinística, e sabendo as complexidades dos algoritmos envolvidos, o tamanho da massa de dados que os mesmos usam de entrada, e a capacidade de processamento da máquina ou máquinas executando o sistema, é trivial calcular o tempo requerido para uma tarefa completar, certo?

Errado.

Na prática, um computador do mundo real está longe de funcionar de forma tão previsível assim. Vários eventos que normalmente ocorrem em um computador - por exemplo outros processos rodando na mesma máquina, necessidade de swap em disco, acesso a rede (no caso de aplicações distribuídas), só para ficar nos mais mais óbvios, podem fazer a diferença (às vezes drástica) entre o tempo estimado e o realmente medido. Nos casos em que o próprio processo cuja duração você quer estimar já tem algum “indeterminismo” embutido, independentemente de fatores externos, a situação pode ficar ainda pior para seu estimador de tempo.

Anos atrás, durante o desenvolvimento de uma das primeiras encarnações dos nossos softwares de bioinformática desenvolvidos para a Biomind, nos deparamos com esse enganadoramente “simples” problema da estimativa de tempo. Nosso produto possuía um lugar-comum de vários sistemas de computação, uma fila de tarefas que eram processadas sequencialmente. Quando uma nova tarefa era submetida, deveria ser apresentada ao usuário uma estimativa para o tempo de conclusão da mesma, que seria a soma do tempo estimado para a tarefa em questão mais os tempos estimados de todas as tarefas à sua frente.

No início, ingenuamente determinamos a complexidade computacional de todos os algoritmos envolvidos, rodamos um número razoável de vezes algumas tarefas diferentes para determinarmos valores médios que seriam usados como constantes de tempo, e desenvolvemos um estimador baseado nesses preceitos que pareciam lógicos e de muito bom senso. E foi um completo desastre, com as estimativas frequentemente errando o tempo medido real por mais de uma ordem de magnitude.

Em parte esse desastre poderia ser explicado por ao menos alguns dos componentes envolvidos na execução de uma tarefa não serem lá a coisa mais previsível do mundo. Tratavam-se de algoritmos de aprendizagem de máquina, cujo tempo de execução pode variar conforme as escolhas que o programa faz para “caminhar” pelo Espaço de Busca. Outra parte poderia ser explicada pelos velhos conhecidos que atrapalham a vida dos estimadores de tempo, as já mencionadas “distorções de tempo” causadas por outros eventos ocorrendo na mesma máquina, máquinas ou rede. (A propósito, nosso sistema também era distribuído, ainda que com poucos nodos de processamento.)

Como, então, lidar com todos esses fatores de incertezas?

Interessantemente, a inspiração veio dos próprios processos de aprendizagem de máquina trabalhando no cerne de nosso produto: decidimos criar um estimador de tempo que aprendesse a estimar o melhor o tempo à medida que mais e mais tarefas fossem sendo rodadas.

Nossa escolha metodológica para o estimador de tempo é um dos mais simples algoritmos de aprendizagem de máquina existentes: o KNN. Em sua forma mais simplória - que de fato foi a usada - o KNN começa como uma lista de exemplos conhecidos do que se quer prever - um “conjunto de treinamento”, em jargão de IA. No caso do nosso estimador, esse conjunto era uma massa de centenas de tarefas já rodadas: cada tarefa continha o seu tempo de execução real, medido, e um vetor de características contendo vários parâmetros e medidas relativos aos dados e algoritmos usados. Quando então uma nova tarefa era apresentada ao estimador, o mesmo comparava os parâmetros e medidas da nova tarefa com todas as existentes, e descobria a tarefa antiga mais parecida com a nova. O tempo estimado para a tarefa nova então era assumido como sendo igual ao tempo de execução dessa tarefa antiga “irmã”.

Depois de completada, e com seu tempo real medido, a tarefa nova era então adicionada à base de comparação. Assim, as estimativas de tempo tendiam a ficar mais precisas quanto mais tarefas eram processadas, o que de fato, com o sistema já em testes avançados, pudemos comprovar plotando gráficos mostrando a convergência. Aliás, essa capacidade do KNN de naturalmente e com custo computacional desprezível incorporar mais “experiência” foi um dos fatores que nos levaram a escolher como o método definitivo para o nosso estimador de tempo. Além disso, na primeira rodada de testes, usando só a base de treiamento inicial, o KNN não mostrou resultados ruins quando comparado com métodos bem mais sofisticados (e com custo computacional bem maior).

Esse “causo” do estimador de tempo encerra umas duas lições de “auto-ajuda para computeiros”, como diz nosso amigo Kenji. A primeira é a de que nivelar por baixo a estimativa da dificuldade de se implementar um requisito é uma política que pode se mostrar desagradavelmente errada mais para a frente. A segunda é a de que nosso velho conhecido, o princípio KISS (Keep it Simple, Stupid) às vezes atende não só seu objetivo primordial de tornar desenvolvimento descomplicado e rápido, mas também atinge resultados finais de alta qualidade, superiores aos que seriam conseguidos de formas mais elaboradas…