q语言如何高效计算列表中小于各序号的数值数量并优化flip开销

功能说明 #

你提供的函数实际作用是：输出长度为n的整数列表，第x位（x取值范围为0到n-1）的值为数组k中严格小于x的元素总个数。

优化方案 #

方案1：最高效简洁实现（推荐）

q内置的bin函数本身就可以直接返回有序数组中小于目标值的元素个数，完全不需要生成二维矩阵、翻转、求和等操作，性能提升极大，代码更短：

// 适用于k已经是升序排列的场景（你给出的示例输入就是升序的）
f:{[n;k] k bin til n}

// 如果k不能保证有序，加一步排序即可，性能依然远高于原实现
f:{[n;k] (asc k) bin til n}

该实现时间复杂度为O(n log m)（m为k的长度），原实现时间复杂度为O(n*m)，数据规模越大性能优势越明显，输出结果和原代码完全一致。

方案2：原逻辑基础上去掉flip

如果不想调整原始逻辑，仅需移除flip操作，可以把比较的维度反过来，直接对每个x（来自til n）统计小于它的k元素数量：

f:{[n;k] sum each (til n) <\: k}

该实现和原始逻辑等价，没有flip开销，代码同样简洁。

内容的提问来源于stack exchange，提问作者Chechy Levas