Otimização

Otimização

> Tutorial LeekScript

Aqui falaremos sobre otimização, o objetivo da otimização é melhorar o desempenho de um algoritmo. Em geral, quando falamos de otimização, falamos de tempo de execução, com o objetivo de reduzir o tempo necessário para executar uma série de instruções.

No LeekScript, esse tempo de execução é estimado por um número: o número de operações usadas por esse cálculo. Vamos, portanto, falar de certas boas práticas e bons reflexos para otimizar um programa, qualquer que seja a linguagem, bem como algumas otimizações mais específicas do LeekScript, e intimamente ligadas à forma como as operações são contadas.

Se ainda não o fez, convido-o a ler o artigo LeekScript Tutorial: Operações.

Bons reflexos

• Não otimize antes de ter um código que funcione: De fato, há uma boa chance de que o trecho de código que escrevemos seja chamado apenas uma vez por turno, o que significa que o tempo gasto otimizando o código não terá efeito perceptível no consumo total das operações.

Por exemplo, salvar 500 operações em uma função chamada apenas uma vez salvará apenas 500 operações. (lógica) Por outro lado, a economia de uma única operação, em uma função que é chamada em um loop de loop de loop, pode reduzir o custo em operações de várias dezenas de milhares de operações.

O que me leva ao segundo ponto:

• identifique onde é caro!

Metade do trabalho de otimização de um código consiste simplesmente em procurar onde as operações saem (então você tem que gritar bem alto e dizer para eles voltarem). O que é caro no código?

Para isso, sem segredo, vamos medir!

Em nosso arsenal, o LeekScript fornece uma função que será muito útil: getOperations. Esta função permite saber o número de operações gastas até agora no código.

Exemplo de uma ferramenta simples para medir o custo de uma função:

global __debug_operation; função inícioOp(){ __debug_operation = getOperations(); } function stopOp(título){ deixe ops = getOperations()-__debug_operation - 3; debug("Operações (" + titulo + "): " + ops); }

inícioOp(); stopOp("teste vazio"); // teste vazio: 0

inícioOp(); diga("olá mundo"); stopOp("olá mundo"); // olá mundo: 30

Podemos assim confirmar que digamos que custa 30 operações, conforme anunciado pela documentação.

É possível, e recomendo fortemente que você faça ferramentas para medir outras coisas em sua IA, como o número de chamadas para uma função, bem como seu custo médio por exemplo, que medirá melhor a evolução dos custos em sua IA, e o impacto de certas otimizações.

A página Complexity ajudará você a entender por que um algoritmo é caro e como resolver o problema. Para resumir de maneira muito simples, preferimos evitar loops de aninhamento entre eles tanto quanto possível. Também procuraremos limitar o tamanho de nossos loops, por exemplo, navegando apenas em nossas células acessíveis em vez de navegar em todas as células do mapa. É importante observar que um algoritmo com menor complexidade usará muito menos operações para um número suficientemente grande de itens a serem processados, pense nisso antes de tentar fazer pequenas otimizações!

Removendo loops que não mudam

Imagine o seguinte código:

deixe TP = getTP();

// atire o máximo de vezes possível no inimigo! for (var i = 0; i < floor(TP / getWeaponCost(getWeapon())); i++) { useWeapon(getNearestEnemy()); }

A função getNearestEnemy será chamada a cada iteração do loop enquanto sempre retornará o mesmo resultado! Para evitar isso, basta colocar o resultado em uma variável antes da função. Fazemos o mesmo para floor(TP / getWeaponCost(getWeapon())) que também é avaliado a cada iteração. Que dão:

deixe TP = getTP();

// atire o máximo de vezes possível no inimigo! var inimigo = getNearestEnemy(); var nbShots = floor(TP / getWeaponCost(getWeapon())); // número de tiros possíveis com a arma atual for (var i = 0; i < nbShots; i++) { useArma(inimigo); }

Recursos do Leek Wars que são caros

inArray, o inArray é prático, faz o que queremos, mas envolve um custo significativo em operações que não necessariamente percebemos à primeira vista. Na verdade, por dentro é assim:

function inArray(elemento, array){ for (valor var na matriz) if (valor == item) retornar verdadeiro; retorna falso; }

Este exemplo é uma boa ilustração para falar sobre um pouco de complexidade. Vemos aqui que o custo real dessa função depende, no pior caso, do tamanho do array array, que chamaremos de n*. Esta função, portanto, tem uma complexidade *n, é