
Fastest Fibonacci sequence generator
Hello,
I’ve been playing around with generating Fibonacci sequences with the goal of learning how to write performant q code.
First, the solution given in the docs, while elegant, is hardly performant:
fib:{x,sum 2#x} ts 1000 fib/0 1 / 0 16768 ts 10000 fib/0 1 / 7 262528 ts 100000 fib/0 1 / 875 2097536 ts 1000000 fib/0 1 / 226615 16777600
In particular, there are many unnecessary allocations.
At the expense of some elegance (and precalculating the output list), we can speed things up significantly:
zeros: {[t; n] n#t$0} fibn:{[s; n] @[s; 0 1; :; 0 1]; f: {[s; i]; @[s; i; :; @[s; i2] + @[s; i1]]; i+1}; (f[s]/)[n2; 2]; s} x: zeros[`long; 1000] ts fibn[`x; 1000] / 0 928 x: zeros[`long; 10000] ts fibn[`x; 10000] / 3 928 x: zeros[`long; 100000] ts fibn[`x; 100000] / 30 928 x: zeros[`long; 1000000] ts fibn[`x; 1000000] / 307 928
Now, my question is whether anyone knows of an even faster way to do it? Alternatively, whether there’s a more elegant way to do it with similar performance.
The lack of lexical scoping and having function arguments always be copied seems unfortunate from a performance point of view. Is my approach (i.e., to allocate data structures in the global scope and then pass around the symbol name) the standard approach?
Log in to reply.