如何将加权随机采样的线性时间实现优化为log(n)时间复杂度的函数？

优化核心逻辑 #

你之前实现的方案中，生成的权重累积和数组c_arr存在一个关键特性：所有权重为正数，因此c_arr是严格单调递增的有序数组。
你需要定位的是第一个满足c_arr[i] >= 随机值val的下标，本质就是有序数组的目标值定位问题，完全可以用二分查找替代线性遍历，单次采样的时间复杂度就能从O(n)降低到O(logn)，整体逻辑和原方案完全兼容，只是替换了查找步骤。 #

具体修改步骤 #

• 预处理步骤保持不变：将输入的{名称:权重}对象先做权重归一化，再计算得到累积和数组c_arr，同时存储每个下标对应的名称数组name_arr，例如权重[0.25, 0.5, 0.25]转换后得到c_arr = [0.25, 0.75, 1]，对应name_arr = ["名称1", "名称2", "名称3"]
• 随机数生成步骤保持不变：调用库函数生成[0,1]区间的随机数val
• 查找步骤替换为二分查找：在有序数组c_arr中找到第一个大于等于val的元素下标，直接返回该下标在name_arr中对应的名称即可

查找示例 #

假设生成的随机数val = 0.6，对应上面的示例数组，二分查找过程如下：

1. 初始左右边界left=0，right=2
2. 取中间位mid = (0+2)>>1 = 1，c_arr[1] = 0.75 >= 0.6，因此缩小右边界到right=1
3. 再次计算中间位mid = (0+1)>>1 = 0，c_arr[0] = 0.25 < 0.6，因此缩小左边界到left=0+1=1
4. 左右边界重合，找到目标下标1，返回对应名称2，和原线性遍历结果完全一致
   如果有多次采样需求，累积和数组只需要预处理一次，所有后续采样都只需要O(logn)时间，在样本量较大的场景下效率提升非常明显。

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