> LeekScript Tutorial
Here we're going to talk about optimization. The goal of optimization is to improve the performance of an algorithm. In general, when we talk about optimization, we mean execution time, the aim being to reduce the time needed to execute a series of instructions.
In LeekScript, this execution time is estimated by a number: the number of operations used by the calculation. So we're going to look at some good practices and good habits for optimizing a program, whatever the language, as well as some optimizations that are more specific to LeekScript and closely tied to the way operations are counted.
If you haven't done so already, I encourage you to reread this article from the LeekScript Tutorial: Operations.
For example, saving 500 operations in a function that's called only once will only save 500 operations. (Makes sense.) On the other hand, saving a single operation in a function that's called inside a loop inside a loop inside a loop can cut the cost by several tens of thousands of operations.
Which brings me to the second point:
Half of the work of optimizing code is simply looking for where the operations are going (then you have to shout really loud and tell them to come back). What's expensive in the code?
For that, there's no secret: we're going to measure!
In our arsenal, LeekScript provides a function that will prove very useful: getOperations. This function tells you how many operations have been spent so far 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){ var 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
This confirms that say does cost 30 operations, as stated in the documentation.
It's possible, and I strongly recommend it, to build tools that measure other things in your AI, such as the number of calls to a function and its average cost, for example. This will help you better track how costs evolve in your AI, and the impact of specific optimizations.
The Complexity page will help you understand why an algorithm is expensive and how to solve the problem. To put it very simply, you should avoid nesting loops inside each other as much as possible. You should also try to limit the size of your loops, for example by only going through your accessible cells instead of going through every cell on the map. It's important to note that an algorithm with a lower complexity will use far fewer operations once the number of elements to process is large enough, so keep that in mind before trying to scrape together small optimizations!
Consider the following code:
var TP = getTP();
// shoot the enemy as many times as possible! for (var i = 0; i Going back to the previous example, this means first checking the value stored in our array before using it:
global WEAPON_MAX_RANGE = [:];
var pistolMaxRange;
var weaponMaxRange = WEAPON_MAX_RANGE[WEAPON_PISTOL]; if (weaponMaxRange !== null) { pistolMaxRange = weaponMaxRange; } else { var newMaxRange = getWeaponMaxRange(WEAPON_PISTOL); WEAPON_MAX_RANGE[WEAPON_PISTOL] = newMaxRange; pistolMaxRange = newMaxRange; }
This takes a few more operations than plain caching when retrieving results that are already known. But it avoids computing everything in advance, and possibly computing things we'll never need. However, it's still very cumbersome to write. Fortunately, we can automate this kind of thing. All we need is a function that takes as arguments the function to memoize, the cache in which to store the results, and the argument to pass to the function to memoize when the result isn't already in the cache:
function applyMemo(f, mem, x) { var ret = mem[x]; if (ret !== null) { return ret; } else { ret = f(x); mem[x] = ret; return ret; } }
For getWeaponMaxRange(WEAPON_PISTOL), we simply use applyMemo like this:
global WEAPON_MAX_RANGE = [:];
var pistolMaxRange = applyMemo(getWeaponMaxRange, WEAPON_MAX_RANGE, WEAPON_PISTOL);
We can make this even easier to use by defining a memoize function that takes a function to memoize as an argument and returns a memoized function. (Careful: the easier we make it to use, the more operations we consume. It's always a good idea to weigh which method is best for your performance and ease-of-use needs.)
function memoize(f) { var mem = [:];
return function(x) { return applyMemo(f, mem, x); }; }
For getWeaponMaxRange(WEAPON_PISTOL), we simply use memoize like this:
global mWeaponMaxRange = memoize(getWeaponMaxRange);
var pistolMaxRange = mWeaponMaxRange(WEAPON_PISTOL);
Note that the implementations given here are not the most optimized ones possible. Get to work!
> Note: for a more concise notation, you can use the fact that an assignment returns the assigned value:
Memoization is pretty handy, isn't it? But how can you use this method to store the result of a function that takes more parameters?
The idea of a hash is to encode information in a smaller space. According to Wikipedia, a hash function is a special function that, from a piece of input data, computes a digital fingerprint used to quickly identify the original data
Let's say we want to store the result of the lineOfSight function, which takes 2 parameters (the start cell and the end cell). We can simply do this: Quick reminder: a cell can have a value from 0 to 612.
And there you go, not very complicated! The resulting hash is a single number that contains the information of both cells! For cell1 = 13 and cell2 = 310, our hash will be 13310. Here, the multiplication costs 5 operations; with the if costing 1 operation and the accesses 2 operations, that makes at least 11 operations, compared to the 30 that lineOfSight costs.
But we can do better!
Oops, I can see some of you frowning. Nothing complicated, I swear! LeekScript uses numbers encoded on 64 bits, which means that a number is stored as 64 zeros or ones. The goal of this method is to use some of that space to store our data. An example is worth a thousand words, so let's go back to the lineOfSight function: We'll start by finding the power of 2 that's higher than the largest number we want to store:
2^ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ... | 63 ---|---|---|---|---|---|---|---|---|---|---|----|----|-----|--- Result |1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | | 9223372036854775808
For our cell, which goes up to 612, we'll therefore take 1024, i.e. 10 bits (2^10 = 1024).
Now all we have to do is use binary operators to store all of this. You'll need to know how to use at least two of them: | and << (take a quick look at using binary operators to refresh your memory). We start from an empty variable, equal to 0 by default:
var hash = cell1 << 10; //Add cell1 shifted by 10 bits hash = hash | cell2; //Add cell2 at the start
If we simplify this code, we get var hash = cell1 << 10 | cell2;, which only uses 3 operations! For cell1 = 13 and cell2 = 310, our hash will be 13622. So our hash variable contains a binary number, with 10 bits reserved for cell1 and 10 bits for cell2.
Our final function now only uses 7 operations: a small improvement, but not a negligible one.
The real power of binary hashes shows when you want to store more information in them:
What information would we need to memoize accessible cells? The starting position, the available movement points (MP) and, let's say, the leek's id (why not!)
First, we need to decide how many bits each element can use:
Well, we just pick a number large enough that it will never be exceeded! Off the top of my head, something like 20 MP. So we'll need 5 bits.
Wait, what?? Those have nothing to do with the numbers of bits we just picked, do they? Well, they do, and it's very simple:
mp needs 5 bits, so we shift id by 5 bits to make room for the MPid needs 6 bits, so we have to shift the cell by 5 + 6 = 11 bits! Makes sense.Be careful to check that the total number of bits you use doesn't exceed 64, otherwise they'll vanish into thin air! Here we have 10 + 6 + 5 = 21 bits, so there's plenty of room!
To avoid mistakes, you can take a sheet of paper and write down your layout:
Data | cell | id | mp | -------|------|----|----| Size (bits) | 10 | 6 | 5 Shift | 6 + 5 = 11 | 5 + 0 = 5 | 0
Now try storing 2 cells and a weapon/chip! If you can do it, you've mastered the art of binary hashing.
How do we handle the case where the data we want to store is bigger than 64 bits? For example, with an array of cells, we can't hash all of that with our binary cleverness.
Fortunately, a programmer never runs out of options: we're going to make mush. The advantage of our binary method is that we can get the stored information back if we ever need to. Here, we're giving up all hope of getting it back.
For an array, we can use a magic formula:
The idea is simply to modify the hash by multiplying it by a number that's large compared to element. Careful: this function works (ahem), but the uniqueness of its result is far from guaranteed. You have to trust your luck to be sure that the output will always be different when the input is different. (It has never let me down.)
Things to keep in mind when using this function:
array must be small (< 15 elements is fine; above that, you're taking risks)element, so you don't blow up the size of your hash and lose information.Sometimes, you have to sacrifice code readability to improve its performance. This section is about seriously dirty tricks for operation penny-pinchers: use them at your own risk! It's recommended to only use these methods in low-level functions that are called very often.
The floor function returns a number rounded down. For example, floor(0.9) = 0, floor(199.724) = 199, ... It turns out that binary operators convert numbers to integers for just one operation! So by using number | 0, you turn number into an integer (by dropping its decimal part), which gives the same behavior as floor for positive numbers! Careful, for negative numbers it truncates: -0.5 | 0 is 0, while floor(-0.5) is -1.
It only costs one operation: one operation saved!
The average of two values can be calculated with
For a total of 6 operations. Make it 2 with the following syntax:
We use the binary shift operator to divide by two. Careful! The result will be equivalent to floor((value1 + value2) / 2) because of the implicit conversion. (Thanks to Kavaliov)
The == and != operators cost 1 operation each: that's one operation too many!
Here we'll take advantage of behind-the-scenes conversions. It turns out that if(null) and if(0) both evaluate to false, which means that the block following this if won't run. If you're sure value will never be 0, false, or an empty string, array or map, you can simply leave out the != or the ==.
Impossible de charger les données du jeu.
Vérifiez votre connexion et réessayez.