KDB 性能：快速搜索第一项

Question

我有一个包含大约 2 万个项目的排序列表 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

KDB 性能：快速搜索第一项

KDB performance: searching first item quicky

kdb

q-lang