2
\$\begingroup\$

I need to find which percentile of a group of numbers is over a threshold value. Is there a way that this can be speed up? My implementation is much too slow for the intended application. In case this changes anything, I am running my program using mpirun -np 100 python program.py. I cannot use numba, as the rest of this program uses try/except statements.

import numpy as np
my_vals = []
threshold_val = 0.065
for i in range(60000):
    my_vals.append(np.random.normal(0.05, 0.02))

upper_bound = 100
lower_bound = 0
perc = 50.0
val = np.percentile(my_vals, perc)
while abs(val - threshold_val) > 0.00001:
    print val
    if val > threshold_val:
        upper_bound = perc
        perc = (perc + lower_bound)/2
    else:
        lower_bound = perc
        perc = (perc+upper_bound)/2
    val = np.percentile(my_vals, perc)

print perc
\$\endgroup\$
5
\$\begingroup\$

If I understand your question, you are asking to determine the percentile value of the first value that exceeds the threshold. The thing to do is the following:

  1. Specify the number of random.normal deviates in the call and pre-sort the array. That way you can just look at each element in the array, knowing that the next one is bigger than the last.

  2. Just count the number of values that fail to exceed the threshold, stopping after you find one that exceeds it. No need to continue beyond this point.

  3. Then, do the arithmetic.

my_vals = sorted(np.random.normal(0.05, 0.02, 60000))
count_vals = 0
for i in my_vals:
    count_vals += 1
    if i > threshold_val:
        break
percentile_val = 100 * (count_vals/len(my_vals))
print('{0:0.6}'.format(percentile_val))

As a check, you could then calculate the value of the element at that percentile using np.percentile.

print(np.percentile(my_vals, percentile_val))

Even easier is to do the counting this way:

count_vals = sum(i > threshold_val for i in my_vals)
percentile_val = 100 * (count_vals/len(my_vals))
\$\endgroup\$
  • \$\begingroup\$ Python makes it easy to make it look easy! :-) \$\endgroup\$ – Edward Carney Mar 5 '16 at 1:24
  • \$\begingroup\$ Good solution. Instead of looping over the whole list, I'd suggest using a binary search to find the first item over the threshold. You can do that, since the list is now sorted. \$\endgroup\$ – Sjoerd Job Postmus Mar 5 '16 at 8:44
  • \$\begingroup\$ Right, Sjoerd. Efficiencies are always welcome, especially as the list grows. Of course the sorting task grows along with the search task. \$\endgroup\$ – Edward Carney Mar 5 '16 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.