KDB性能:快速搜索第一项

Question

我有一个大约20K项目的排序列表v.我想在第一个v [i]> K的点处将其拆分为2个列表

N:20000;
v:asc N?100000;     / N random numbers sorted
K:200;              / threshold
v1:v[where v<=K];   / "v<=K" has O(N) complexity, "where" has O(N) too
v2:(count v1) _ v;  / list is sorted, this holds.

问题:如何避免v <= 200,所以它不计算长度为N的整个中间布尔向量,换句话说,在第一次匹配后找不到值？我实际上需要一个索引来执行拆分.假设K靠近列表的开头.

这是与绩效相关的问题.(注意忽略在"asc"上花费的时间.)

Answer 1

为了避免计算布尔列表,您可以利用列表的排序和使用事实binr:

c:v binr K  //42
v1:c # v
v2:c _ v

这大大提高了操作速度:

q)\ts:10000 v1:v[where v<=K];v2:(count v1) _ v
680 262608
q)\ts:10000 c:v binr K;v1:c # v;v2:c _ v
75 262560