How can I merge two lists using a custom comparator ?

Community Support
1

This means I must iterate until both lists are exausted,

taking the current element which compares lower off its

list at each iteration.

In pseudo code

<pre>

  A= (1,3, 5, 6, 10, 13, 18, 26, 42, 48)

  B= (1,3, 4, 7, 10, 12, 19, 24, 42, 44)

  a=firstItem(A); b=firstItem(B); next=null; 

  while (a!=null and b!=null) {

    n= compare(a,b) ;

    if (n<=0) { output(a) ; a=nextItem(A) ;}

    if (n>=0) { output(b) ; b=nextItem(B) ;}

  }

  while (a!=null) { output(a); a=nextItem(A) ;}

  while (b!=null) { output(b); b=nextItem(B) ;}

</pre>  

How can I do this properly in kdb (ie without while loops) ?

Here “compare” and “output” will be custom operations, and the real data will tables not lists of numbers,

But the sticking point seems to be just the need to advance through one list or the other conditionally, as illustrated here.

2

On Friday, May 5, 2017 at 3:03:43 AM UTC-4, dan wrote:

This means I must iterate until both lists are exausted,

taking the current element which compares lower off its

list at each iteration.

Assuming A and B are sorted, it looks like what you want is

   asc A,B

if you can replace a custom comparator with a key function (compare:{f<f[y]}), then you can merge the lists with

   x iasc f each x:A,B

3

The expression ?[A<B;A;B] is a vector conditional not a merge.
The lists A and B are required to be the same length and the output
will be that length as well, containing the lower of the element from
A or B in each position.

A merge requires that the two lists be sorted, and will produce
a list with the same sort order containing all elements from both lists.

For my example that would be:
(1,1,3,3,4,5,6,7,10,10,12,13,18,19,24,26,42,42,44,48)

The difference in the logic is that the vector conditional bumps to
the next element of BOTH lists on each iteration. The merge only
bumps to the next element of the list whos element is outputted.

That means which list gets advanced must be conditioned on the outcome
of the comparison.

I am actually trying to build a custom join (for tables) based on a multi part key,
which outputs something for partial matches (on the first few fields of the key).
I might base that on a “cross” which will require filtering though the product of
the numbers of elements in the two lists. I’d rather not, because the sequential
logic shown above only needs to go though the sum.  Maybe I can also adapt the
“union join”, to get what I need. 

4

So, if the lists are already sorted “asc” will do a merge  (that makes sense),
and the iasc form allows me to specify a “key function”, which unlike a
custom comparator cannot transform the input based on the result of the
comparison.  will that also work for  tables, or do I need xasc which only
allows you to select a list of field names for the key ?

5

q)a

1 3 5 6 10 13 18 26 42 48

q)b

1 3 4 7 10 12 19 24 42 44

q)asc (b,a[where a in b]),(a[where not a in b]) 

`s#1 1 3 3 4 5 6 7 10 10 12 13 18 19 24 26 42 42 44 46 48

Kumar

6

Or did you mean to do:

q)a

1 3 5 6 10 13 18 26 42 48

q)b

1 3 4 7 10 12 19 24 42 44

q) asc a,b  / much more straightforward

`s#1 1 3 3 4 5 6 7 10 10 12 13 18 19 24 26 42 42 44 48

q)(asc a,b)~(asc (b,a[where a in b]),(a[where not a in b]))

1b

performance numbers :

q)a:10000000?10000000

q)b:10000000?10000000

q)\t asc a,b

10284

q)\t asc (b,a[where a in b]),(a[where not a in b])  

15135

q)(asc a,b)~( asc (b,a[where a in b]),(a[where not a in b]) ) // just to show equivalence

1b

So both lists get merged, elements from both lists appear in the final list, in *sorted* order. 

Kumar

7

This response and others have suggested that I do a sort instead of a merge, I suppose that might work.
But will it really do a merge when the two lists are already sorted ( and have the sorted attribute set ) ?
I don’t think it can know to do that because both asc and iasc sort a SINGLE input list. The syntax
 asc A,B  or  x iasc f each x:A,B  will just concatenate B onto A and then sort, rather than actually
 perform a merge, am I wrong  ?

Also note that this is an oversimplification of the actual problem where the input is two tables,
and custom processing is desired to be added to each of the conditional blocks of the sequential
algorithm shown as my example. I will post a new question with the issues that raises.
 

8

 asc A,B  or  x iasc f each x:A,B  will just concatenate B onto A and then sort, rather than actually
 perform a merge, am I wrong  ?

You are right.  It’s still the fastest known way of merging two sorted lists in q.

Also note that this is an oversimplification of the actual problem where the input is two tables,
and custom processing is desired to be added to each of the conditional blocks of the sequential
algorithm shown as my example. I will post a new question with the issues that raises.