Optimization

Optimization

> LeekScript Tutorial

Here we will talk about optimization, the objective of optimization is to improve the performance of an algorithm. In general, when we talk about optimization, we talk about execution time, the goal being to reduce the time required to execute a series of instructions.

In LeekScript, this execution time is estimated by a number: the number of operations used by this calculation. We are therefore going to talk about certain good practices and good reflexes for optimizing a program, whatever the language, as well as certain optimizations more specific to LeekScript, and intimately linked to the way in which operations are counted.

If you haven't already done so, I invite you to read the article on Tutorial_LeekScript: Operations.

Good reflexes

• Do not optimize before having a code that works: Indeed, there is a good chance that the piece of code that we write will only be called once per turn, which means that the time spent optimizing the code will have no noticeable effect on the overall consumption of operations.

For example, saving 500 operations on a function called only once will only save 500 operations. (logic) On the other hand, a saving of a single operation, on a function that is called in a loop of loop of loop can reduce the cost in operations of several tens of thousands of operations.

Which brings me to the second point:

• identify where it is expensive!

Half the work of optimizing a code consists simply of looking for where the operations leave (then you have to shout loudly and tell them to come back). What is expensive in the code?

For that, no secret, we will measure!

In our arsenal, the LeekScript provides a function that will prove very useful: getOperations. this function allows to know the number of operations spent until now in the code.

Example of a simple tool to measure the cost of a function:

global __debug_operation; function startOp(){ __debug_operation = getOperations(); } function stopOp(title){ let ops = getOperations()-__debug_operation - 3; debug("Operations (" + title + "): " + ops); }

startOp(); stopOp("empty test"); // empty test: 0

startOp(); say("hello world"); stopOp("hello world"); // hello world: 30

We can thus confirm that say costs 30 operations, as announced by the documentation.

It is possible, and I strongly recommend that you make tools to measure other things in your AI, such as the number of calls to a function, as well as its average cost for example, which will better measure the evolution of costs in your ai, and the impact of certain optimizations.

The Complexity page will help you understand why an algorithm is expensive and how to solve the problem. To summarize very simply, we prefer to avoid nesting loops between them as far as possible. We will also seek to limit the size of our loops, for example by browsing only our accessible cells instead of browsing all the cells of the map.

Removing loops which won't change

Imagine the following code:

let TP = getTP();

// shoot as many times as possible on the enemy! for (var i = 0; i < floor(TP / getWeaponCost(getWeapon())); i++) { useWeapon(getNearestEnemy()); }

The getNearestEnemy function will be called at each iteration of the loop while it will always return the same result! To avoid this, just put the result in a variable before the function. We do the same thing for floor(TP / getWeaponCost(getWeapon())) which is also evaluated at each iteration. Which give :

let TP = getTP();

// shoot as many times as possible on the enemy! var enemy = getNearestEnemy(); var nbShots = floor(TP / getWeaponCost(getWeapon())); // number of possible shots with the current weapon for (var i = 0; i < nbShots; i++) { useWeapon(enemy); }

Leek Wars features that are expensive

inArray, the inArray is practical, it does what we want, but it involves a significant cost in operations that we do not necessarily notice at first glance. In fact, inside it looks like this:

function inArray(element, array){ for (var value in array) if (value == item) return true; return false; }

This example is a good illustration to talk about a bit of complexity. We see here that the real cost of this function depends in the worst case on the size of the array array, which we will name n*. This function therefore has a complexity of *n, ie it will require up to n operations to find the result.

While using an associative table (Map), and in c