matching head of a list

Community Support
1

i’m having a hard time finding a neat solution to finding if a list (a head) matches the start of another list

say i have a two “heads” to match, a and b, and c is the list to match with:

 a:1 2

 b:1 2 1

 c:1 2

 a~(count a)#c

1b

 b~(count b)#c

1b

but i don’t want 1 2 1 to be a head of 1 2 (no wrapping around)

i can fix it, using shape:

 a~first(0N,count a)#c

1b

 b~first(0N,count b)#c

0b

but it’s a little unsatisfying because the reshape is costly just to find the first two elements.  

am i going to have to involve count[c]?

jack

2

You could use sublist for this, which doesn?t wrap around:<o:p></o:p>

<o:p> </o:p>

q)a:1 2<o:p></o:p>

q)b:1 2 1<o:p></o:p>

q)c:1 2<o:p></o:p>

q)a~(0;count a) sublist c<o:p></o:p>

1b<o:p></o:p>

q)b~(0;count b) sublist c<o:p></o:p>

0b<o:p></o:p>

<o:p> </o:p>

Hope that helps<o:p></o:p>

Jonathon<o:p></o:p>

<o:p> </o:p>

From: Jack Andrews
Sent: 06 January 2017 13:16
To: Kdb+ Personal Developers
Subject: [personal kdb+] matching head of a list

<o:p> </o:p>

i’m having a hard time finding a neat solution to finding if a list (a head) matches the start of another list

say i have a two “heads” to match, a and b, and c is the list to match with:

 a:1 2

 b:1 2 1

 c:1 2

 a~(count a)#c

1b

 b~(count b)#c

1b

but i don’t want 1 2 1 to be a head of 1 2 (no wrapping around)

i can fix it, using shape:

 a~first(0N,count a)#c

1b

 b~first(0N,count b)#c

0b

but it’s a little unsatisfying because the reshape is costly just to find the first two elements.  

am i going to have to involve count[c]?

jack

–
Submitted via Google Groups

3

Sorry, the 0 here isn?t needed, as 0 is the default starting position:

<o:p> </o:p>

q)a~count[a] sublist c<o:p></o:p>

1b<o:p></o:p>

q)b~count[b] sublist c<o:p></o:p>

0b<o:p></o:p>

<o:p> </o:p>

Hope that helps<o:p></o:p>

Jonathon<o:p></o:p>

<o:p> </o:p>

From: Jonathon McMurray
Sent: 06 January 2017 13:26
To: Jack Andrews; Kdb+ Personal Developers
Subject: RE: [personal kdb+] matching head of a list

<o:p> </o:p>

You could use sublist for this, which doesn?t wrap around:<o:p></o:p>

<o:p> </o:p>

q)a:1 2<o:p></o:p>

q)b:1 2 1<o:p></o:p>

q)c:1 2<o:p></o:p>

q)a~(0;count a) sublist c<o:p></o:p>

1b<o:p></o:p>

q)b~(0;count b) sublist c<o:p></o:p>

0b<o:p></o:p>

<o:p> </o:p>

Hope that helps<o:p></o:p>

Jonathon<o:p></o:p>

<o:p> </o:p>

From: Jack Andrews
Sent: 06 January 2017 13:16
To: Kdb+ Personal Developers
Subject: [personal kdb+] matching head of a list

<o:p> </o:p>

i’m having a hard time finding a neat solution to finding if a list (a head) matches the start of another list

say i have a two “heads” to match, a and b, and c is the list to match with:

 a:1 2

 b:1 2 1

 c:1 2

 a~(count a)#c

1b

 b~(count b)#c

1b

but i don’t want 1 2 1 to be a head of 1 2 (no wrapping around)

i can fix it, using shape:

 a~first(0N,count a)#c

1b

 b~first(0N,count b)#c

0b

but it’s a little unsatisfying because the reshape is costly just to find the first two elements.  

am i going to have to involve count[c]?

jack

–
Submitted via Google Groups

4

>sublist

thanks jonathon,

i note that sublist checks count y in the end… 

so i think there’s no magic use of primitives to solve the problem efficiently without involving count y.

5

There is another option without counting the second list. You can usetil count[a] to generate a list of indices to extract from the second list, e.g.

<o:p> </o:p>

q)a:1 2; b:1 2 1; c: 1 2<o:p></o:p>

q)f:{x~count sublist y}<o:p></o:p>

q)g:{x~y til count x}<o:p></o:p>

q)f[;c] each (a;b)<o:p></o:p>

11b<o:p></o:p>

q)g[;c] each (a;b)<o:p></o:p>

10b<o:p></o:p>

<o:p> </o:p>

However, this isn?t much faster<o:p></o:p>

<o:p> </o:p>

q)\t:1000000 f[b;c]<o:p></o:p>

1082<o:p></o:p>

q)\t:1000000 g[b;c]<o:p></o:p>

1064<o:p></o:p>

<o:p> </o:p>

Finally, you can replace til with the monadic ! primitive:<o:p></o:p>

<o:p> </o:p>

q)h:{x~y (!:) count x}<o:p></o:p>

q)h[;c] each (a;b)<o:p></o:p>

10b<o:p></o:p>

q)\t:1000000 h[b;c]<o:p></o:p>

546<o:p></o:p>

<o:p> </o:p>

Hope this helps<o:p></o:p>

Jonathon<o:p></o:p>

<o:p> </o:p>

From: Jack Andrews
Sent: 06 January 2017 13:46
To: Kdb+ Personal Developers
Subject: Re: [personal kdb+] matching head of a list

<o:p> </o:p>

>sublist

thanks jonathon,

i note that sublist checks count y in the end… 

so i think there’s no magic use of primitives to solve the problem efficiently without involving count y.

6

cool - so a simple sublist is {y x[0]+til x[1]+1-x[0]} - it didn’t occur to me to use indexing to get a sublist