KX Community

Find answers, ask questions, and connect with our KX Community around the world.
KX Community Guidelines

Home Forums kdb+ Fastest Fibonacci sequence generator

  • Fastest Fibonacci sequence generator

    Posted by albin on February 12, 2024 at 12:00 am

    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 pre-calculating 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; i-2] + @[s; i-1]]; i+1}; (f[s]/)[n-2; 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?

    albin replied 3 months, 1 week ago 2 Members · 4 Replies
  • 4 Replies
  • albin

    Member
    February 12, 2024 at 12:00 am

    It’s perhaps nicer to always fill the entire input array instead of taking the number of values to generate as an argument.

    fibn:{[s] n: count get s; @[s; 0 1; :; 0 1]; f: {[s; i]; @[s; i; :; @[s; i-2] + @[s; i-1]]; i+1}; (f[s]/)[n-2; 2]; s} x: zeros[`long; 1000000] ts fibn[`x] / 319 576

    Interestingly, this reduces the number of bytes allocated by 352, but seems to be slightly slower.

  • jfealy

    Member
    February 13, 2024 at 12:00 am

    Arthur’s K solution for first n+1 numbers

    k)n(|+) 1 fib:{x,sum -2#x}/[;0 1] // first n+2 aq:{first flip x(reverse sums::) 1} 
    // first n+1 
    q)ts fib 100000 1359 2097392 
    q) 
    q) 
    q)ts aq 100000 14 6345952
  • jfealy

    Member
    February 16, 2024 at 12:00 am

    (reverse sums::) is another method of generating a function composition https://code.kx.com/q/ref/compose/

    q)'[reverse;sums]~(reverse sums::) 1b

     

    The definition you see for reverse is the monad form of the K verb | . The colon is an aid to the interpreter, as unless immediately used, the verb always denotes it’s dyad.

    e.g. you can see the difference here, where the first item returned is the reverse of the list, and the second item is a projection of the OR dyad.

    q)(|:;|)@:1 2 3 3 2 1 |[1 2 3]

     

    You can examine these in the .q namespace & there is further reading here https://code.kx.com/q/basics/exposed-infrastructure/#unary-forms

    q)5#.q | :: neg | -: not | ~: null | ^: string| $:

     

    In terms of the colons & their meanings, you can find more info & examples on this (and much more) in this excellent link https://github.com/quintanar401/DCoQ?tab=readme-ov-file#mystery-of-

     

     

  • albin

    Member
    February 16, 2024 at 12:00 am

    Thank you for the suggestion  . That’s an elegant solution.

    I’m struggling to understand it though. Could you please help explain the following?

    q) reverse sums 1 2 3 6 3 1 / This makes sense. q) (reverse sums) 1 2 3 1 3 6 / Why did we lose the reverse? q) (reverse sums::) 1 2 3 6 3 1 / Why did this recover the reverse? q) q) sums + / Makes sense. q) reverse |: / Reverse is a combination of the max and assignment operators? q) reverse sums + / Reverse was lost. q) reverse sums:: |+ / Max operator combined with sums?

    I suspect the issue is I don’t understand the meaning of | and ::. I had thought | was just the max operator but maybe is also has other meanings? I know :: has at least these meanings:

    • Defining a view.
    • Assignment in-place.
    • Assignment to a global variable.
    • The generic null.
    • The identity function.
    • An elided index used to select everything.

    Does :: have yet another meaning here or does one of the above apply?

Log in to reply.