分类概率的动态向量索引

Question

对于我的代码，我有一个很大的(最多40,000)类概率向量。这组类概率也需要定期重新加权，因此假设它在每次调用代码时都会发生变化。向量和为1。我需要有效地搜索与该概率相对应的索引。

举个例子，假设向量是[0.25, 0.25, 0.25, 0.25]，均匀分布在4个对象上。我的概率结果是0.67。这对应于索引3，因为是0.67 > sum(probvec[0:1])而是0.67 <= sum(probvec[0:2])。

我愿意改变概率向量，使其成为运行和，即[0.25, 0.5, 0.75, 1]，不过我还需要一个关于如何执行更新的建议。

任何帮助都将不胜感激。

Answer 1

• Step 1 index.
• Step :预计算出i-th 2的所有部分和:使用二进制搜索扫描sums_probvec，以获得logtime内的结果。

import numpy as np

probvec = np.full(4, 0.25)
prob = 0.67

# pre-compute all the partial sums up to the i-th index
sum_probvec = [probvec[0]]
for i in range(1, len(probvec)) :
    sum_probvec.append(sum_probvec[i-1] + probvec[i])

# use binary search for logtime results
i = 0
j = len(sum_probvec)
while i != j-1:
    mid = (i + j) // 2
    if prob > sum_probvec[mid]:
        i = mid
    else:
        j = mid
index = i+2

print (index) # 3