Indexing dynamic vector of class probabilities

user_13214893 0
Viewed 37

For my code, I have a large (up to 40,000) vector of class probabilities. This set of class probabilities also needs to be reweighted regularly, so assume it will change on every call of the code. The vector sums to 1. I need to efficiently search through this for the index corresponding to that probability.

As an example - say the vector was [0.25, 0.25, 0.25, 0.25], uniform prob across 4 objects. My probability result is a 0.67. This corresponds to index 3, since 0.67 > sum(probvec[0:1]) but 0.67 <= sum(probvec[0:2]).

I'm open to changing the probability vector to make it the running sum, i.e. [0.25, 0.5, 0.75, 1], though then I'd also need a suggestion as to how to perform updates.

Any help would be appreciated.

probability python-3.x numpy python
1 Answers
  • Step 1: pre-compute all the partial sums up to the i-th index.
  • Step 2: scan your sums_probvec with binary search for obtaining the result in 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
user_46077330
Related