> LeekScript Tutorial
To estimate how many operations a function or an algorithm will consume, it is useful to have an idea of the relationship between the size of the arguments you give it, or the size of a parameter, and the maximum number of operations performed. This is called algorithmic complexity.
Let's start with a simple example: a for loop.
for (var i=0; i N, f(n) n² grows much more slowly than the function n -> 4^n: as MP increase, a poorly written accessible-cells function will become extremely expensive, while the same function, well written, will keep a reasonable cost.
The natural question is then: how do you calculate these O's, and what are the useful functions to compare our code with? So I'll give a few complexities that come up regularly, ranked from lowest to highest, along with calculation rules to evaluate the complexity of an algorithm. You'll then have to combine these rules to find the complexity of a given piece of code!
--- The complexities you'll come across most often are the following, in ascending order:
O(1): "constant complexity" O(n): "linear complexity" O(n log(n)): "quasi-linear complexity" O(n²): "quadratic complexity" O(n^k) with k an integer: "polynomial complexity" O(k^n): "exponential complexity" O(n!): "factorial complexity (it can be shown to be the same as O(sqrt(2πn)(n/e)^n))"
--- // code costing O(g(n)), then // code costing O(h(n))
When two blocks of code follow each other, you keep the "largest" term: if g is a higher complexity than h, then the code is in O(g(n)). If h is a higher complexity than g, then the code is in O(h(n)). If both pieces of code have the same complexity, the whole block has that same complexity.
We saw in the examples how for loops behave:
for (var i=0; i 1), it first computes the combos of n-1 elements, then for each combo found it puts 2 in the list it finally returns (a copy of the combo, and a copy of the combo plus the first element of the list). So if we call N(n) the number of elements in the list of combos returned for an input list of n elements, we have N(n) = 2*N(n-1) for n > 1. Moreover, N(1) = 2, since if the list contains only one element, we return a list containing 2 combos. So, by induction, we get N(n)=2^n. And if we end up with 2^n elements, it means we did 2^n pushes. We could also count the number of function calls, of counts, etc.: there are no more of them than pushes. So this function has a complexity of O(2^n).
So the idea, to study the complexity of a recursive function, is to find a recurrence formula. This one was particularly simple; you can run into far more twisted ones!
--- Finally, I'll list a few LeekScript functions whose cost depends on their input (non-exhaustive list). If the function you're looking for isn't listed, run some tests or ask on the chat!
Array functions: n is the size of the array
Function | Cost ---------|----- arrayFilter | O(n) arrayFoldLeft | O(n) arrayFoldRight | O(n) arrayIter | O(n) arrayMap | O(n) arrayMax | O(n) arrayMin | O(n) arrayPartition | O(n) arraySort | O(n log(n)) assocSort | O(n log(n)) average | O(n) fill | I don't know (array resizing hidden behind it) inArray | O(n) join | Um... No idea on that one. keySort | O(n log(n)) pop and push | I don't know (array resizing hidden behind it) remove | ? removeElement | ? removeKey | ? reverse | O(n) search | O(n) shift and unshift | I don't know (array resizing hidden behind it) shuffle | O(n), in theory. But LW's shuffle is fishy: it costs less than n on large arrays... sort | O(n log(n)) sum | O(n)
Movement and distance functions: n is the number of MP between the start and the destination
Function | Cost ---------|----- getPath | O(n²) (probably, I don't know the exact code) getPathLength | O(n²) (same remark)
Impossible de charger les données du jeu.
Vérifiez votre connexion et réessayez.