Hi all, i have two sorted tables, sorting based on same combination of columns. What is the most effective way of combining these two table to a sorted table?
Thanks!
i can’t beat asc x,y for simple lists although it should be possible.
q)f:{$[not count x;(();();z,y);not count y;(();();z,x);(first x)<first y;(1_x;y;z,first x);(x;1_y;z,first y)]}
q){last ((f .)/)x}(1 2;1 3 4;())
1 1 2 3 4
a recursive approach runs out of stack quickly
q)m:{o:.z.s;$[not count x;y;not count y;x;(first x)<first y;(first x),o[1_x;y];(first y),o[x;1_y]]}
q)s:{asc x?x}
q)t:{m . s each 2#x}
q)u:{asc raze s each 2#x}
q)v:{last ((f .)/)(s each 2#x),enlist[()]}
q)\ts:100 u 1000
26 49328
q)\ts:100 t 1000
707 10952640
q)\ts:100 v 1000
620 69952
This is a classic case of binary merge which can be performed in linear time (i.e. at least as fast as asc).
I’ve tried a couple of times to beat asc x,y for sorted lists but can’t find it. as you note, its an O(n) problem, but my linear time methods just have too much overhead.
Thanks all!
Using the algorithm below, with cursors instead of drop, should work well.
From https://en.wikipedia.org/wiki/Merge\_algorithm:
**algorithm** merge(A, B) **is**** inputs **A, B : list** returns **list C := new empty list** while **A is not empty and B is not empty** do ****if** head(A) ? head(B) **then** append head(A) to C drop the head of A **else** append head(B) to C drop the head of B_// By now, either A or B is empty. It remains to empty the other input list._ **while** A is not empty **do** append head(A) to C drop the head of A **while** B is not empty **do** append head(B) to C drop the head of B **return** C
On Friday, July 22, 2016 at 12:46:12 AM UTC-7, effbiae wrote:
I’ve tried a couple of times to beat asc x,y for sorted lists but can’t find it. as you note, its an O(n) problem, but my linear time methods just have too much overhead.
On 22/07/2016 12:26 PM, “investt…@yahoo.com” <investt…@gmail.com> wrote:
This is a classic case of binary merge which can be performed in linear time (i.e. at least as fast as asc).
I’d be interested in seeing code that beats asc x,y. I’ve tried indexing to avoid drop/join (I could dig up the code if anyone’s interested). I hope its something I never would have thought of - which would make me feel better - and more educated!
Binary merge will do at most N-1 comparisons (with very low overhead) where N:(#x)+#y plus copying each new column’s value atomically and in order into the result table.
asc x,y does N log N comparisons (assuming that quicksort is still the general case sorting algorithm) plus a copying each column’s values into the correct location.
The comparison function should be identical.
>O(n)
Yes, in theory, merging two sorted lists should be super fast. In k4 it isn’t (at least, noone has shown any code to the contrary). This is the code I expect should be fast:
q)k)f:{e:{~(*x)<#x 1};a:{@/|x};d:{(1+*x;:/x)};n:{(|1#:\x 1;|1#:\y 1;z)}[x;y];$[(e x)&e y;(x;y;z);e x;n z,a y;e y;n z,a x;(a x)<a y;(d x;y;z,a x);(x;d y;z,a y)]}
q)g:{last ((f .)/)((0;x);(0;y);())}
q)g[1 2 5;0 4 6]
0 1 2 4 5 6
but this is the timespace comparison to asc x,y:
q){a::(asc x?)each 2#x;{(x;system"t ",x)}each(“g . a”;“asc raze a”)}each 3 (10*)\100
“g . a” 2 “asc raze a” 0
“g . a” 19 “asc raze a” 0
“g . a” 219 “asc raze a” 0
“g . a” 35710 “asc raze a” 12
i’ve tried a few different ways to implement asc x,y for sorted lists but can’t find a fast way.
asc does show O(n log n) behaviour here:
q){a::(asc x?)each 2#x;{(x;system"t ",x)}“asc raze a”}each 3 (10*)\10000
“asc raze a” 0
“asc raze a” 6
“asc raze a” 59
“asc raze a” 718
q){((f .))((0;x);(0;y);())}[1 2 5;0 4 6]
(0;1 2 5) (0;0 4 6) ()
(0;1 2 5) (1;0 4 6) ,0
1 1 2 5 1 0 4 6 0 1
(2;1 2 5) (1;0 4 6) 0 1 2
(2;1 2 5) (2;0 4 6) 0 1 2 4
(3;1 2 5) (2;0 4 6) 0 1 2 4 5
(1;3;1 2 5) (1;3;0 4 6) 0 1 2 4 5 6