Fast first element match

Community Support
1

Hello,Suppose that one has a large list and wants to quickly find the firstelement matching a given condition. This condition typically will bemet in the first few elements, so it’s not efficient to scan the entirelist.Is there any easy way to efficiently acheive this search without havingto guess how much to truncate the list?q)r:(prd 8#10)?1fq)\t 0N!first r where 0.9<r0.9543722575q r where></r0.9543722575q>

2

To: “[kdb+] [kdb+]” X-Mailer: Apple Mail (2.1878.6)?http://code.kx.com/wiki/Reference/QuestionSymbolCheers, AttilaOn 17 Aug 2014, at 21:13, Josh Myzie wrote:> Hello,> > Suppose that one has a large list and wants to quickly find the first> element matching a given condition. This condition typically will be> met in the first few elements, so it’s not efficient to scan the entire> list.> > Is there any easy way to efficiently acheive this search without having> to guess how much to truncate the list?> > q)r:(prd 8#10)?1f> q)\t 0N!first r where 0.9 0.9543722> 575> q)\t 0N!first r where 0.9<10#r> 0n> 0> q)\t 0N!first r where 0.9<100#r> 0.9543722> 0> > > Thanks,> Josh> > – >

Submitted via Google Groups

3

On 17 August 2014 21:33 UTC, Attila Vrabecz <attila.vrabecz> wrote:> ?>> http://code.kx.com/wiki/Reference/QuestionSymbol&gt;&gt; Cheers,> AttilaTo which form of ? are you referring? It looks to me that the firstoccurrence functionality only works for exact matches, not conditional matches.Josh</attila.vrabecz>

4

q)r:(prd 8#10)?1f

q)\ts first r where 0.9<r

275 268435824

we only need the first value

q)\ts r first where 0.9<r

220 268435824

early termination with ? for the first

q)\ts r(0.9<r)?1b

100 134218080

we can keep growing to terminate early

(initial size and growth could be tweaked to problem/machine)

q)\ts:100000 n:100;while[n=i:(0.9<n sublist r)?1b;n*:10];i

224 2048

but of course the pathological case will take longer

q)\ts n:100;while[n=i:(1<n sublist r)?1b;n*:10];i

246 150995904

we could rewrite this with adverbs with some effort

q)\ts last first{$[y=i:?[;1b]1<y sublist r;1b,10*y;0b,i]}//1b,100

232 150995904

Cheers,

  Attila