If I have a list 0 1 2 3 4 5 and I want to transform it into a list 0 1 2 3 **99** 4 5
I can do (3#a),99,3_a, but this is appallingly slow.
What’s the fastest way to do this? The array data type is of course not really convenient for this kind of operation, but I want to make sure I’m not missing any information about list internals that makes this possible.
Many Thanks!
Rob
Don’t think there is a fast way for that in Q. Doing AOC?
You could use rotate for this https://code.kx.com/q/ref/lists/#rotate
->Victor Salgado
yes! I was doing day 9 (the one with the marbles game). In the end I implemented doubly linked circular lists in python which did the job. Using rotate is a very interesting idea actually, I will explore that.
Hi Rob,
Searching through arrays and or lists can be slow as you say. Your method works well on quite small list but I imagine you are dealing with very large lists at which point efficiency does indeed become an issue. I know that the example list you have given here happens to be numerically sorted. Im not sure if this was simply an example list or you are actually dealing with numerically sorted list in your actual problem. If the latter is true you can marginally improve the efficiency of your method my adding an “attribute” to your initial list, this lets q know that the list is sorted numerically and allows it to deal with it more efficiently under the hood. The two methods to do this are A) asc 0 1 2 3 4 5 or B) s#0 1 2 3 4 5 . Your numerically sorted list will then return prepended with as# attribute indicating it has been sorted. Once you have this sorted list your method of inserting at a given index works slightly more efficiently but still leaves a lot of room for improvement. I tried your method of (n#a),99,n_a with a attributed list and an unattributed list and timed both of them for 1000 iterations where the lists were themselves ten million numbers long. (\t do[1000;(5000#b),99,5000_b] ) The attributed version was a few seconds faster then the normal list. If anything else comes to mind that is more efficient I will let it be known.
Rotate is built on the same operators, wouldn’t expect that to help here.
The expensive part seems to be copying the array around in memory.
q)rotate
k){$[0h>@y;'rank;98h\<@y;'type;#y;,/|(0;mod[x;#y])_y;y]}
I’ve worked around this by limiting this - see somewhere at the bottom here:
https://www.reddit.com/r/adventofcode/comments/a4i97s/2018_day_9_solutions/
(Look for the very cool batching solution as well.)
Indexed assignment can be faster
q)a:til 6
q)\ts:100000 b:(3#a),99,3_ a
153 1664
q)\ts:100000 b:7#99;b[0 1 2 4 5 6]:a
133 1568
It doesnt scale, but does use less space
q)c:til 1000000
q)i:til[1+count c]except div[;2]count c
q)\ts:100 d:(500000#c),99,500000_ c
259 16777728
q)\ts:100 e:1000001#99;e[i]:c
1004 8389168
Stephen Taylor | Librarian | Kx | +44 7713 400852 | stephen@kx.com