I need to find the percentile where a list of values is higher than a threshold. I am doing this in the context of optimization, so it important that the answer is precise. I am also trying to minimize compute time. I have a O(n) solution which is not very precise, then I use scipy's minimize optimizer to find the exact solution, which is time-intensive. The numbers in my problem are NOT normally distributed.

Is there a more time-efficient way to do this while preserving precision?

from scipy.optimize import minimize
my_vals = []
threshold_val = 0.065
for i in range(60000):
    my_vals.append(np.random.normal(0.05, 0.02))

count_vals = 0.
for i in my_vals:
    count_vals += 1
    if i > threshold_val: break
percKnot = 100 * (count_vals/len(my_vals))
print minimize(lambda x: abs(np.percentile(my_vals, x[0]) - threshold_val), percKnot, bounds=[[0,100]], method='SLSQP', tol=10e-9).x[0]
  • \$\begingroup\$ Is it just me or are you just trying to count the amount of values lower than a threshold and convert that to a percentage? \$\endgroup\$ – 409_Conflict Mar 18 '16 at 19:23
  • \$\begingroup\$ The idea behind the minimization is that the percentile value can be more precise than just count_vals/len(my_vals) by interpolating to a percentile which exactly corresponds to the threshold \$\endgroup\$ – kilojoules Mar 18 '16 at 19:38

Use comprehensions

I understand that my_vals is not necessarily the real data and that you might have other means to generate them, but anyway building a list using append is often an antipattern. Use a list comprehension instead:

my_vals = [np.random.normal(0.05, 0.02) for _ in range(60000)]

Same for your actual computation, you basically want to count the amount of values lower than the threshold; use a generator expression and feed it to sum:

sum(1 if x <= threshold_val else 0 for x in my_vals)

This is still \$O(n)\$ and will compute the required value right away (after dividing by len(my_vals)).

Better is to use int(x <= threshold_val) instead of the ternary. Or even the comparison directly (even if more implicit) since True + True is 2.

Use functions

In order to improve reusability and testing.

This also means that you can wrap your demo code into bits that won't necessarily be called every time. For instance:

from scipy.optimize import minimize

def compute_percentile(values, threshold):
    count = sum(x <= threshold for x in values)
    percentage = 100. * count / len(values)
    # Improve precision of the percentile
    return minimize(lambda x: abs(np.percentile(values, x[0]) - threshold), percentage, bounds=[[0,100]], method='SLSQP', tol=10e-9).x[0]

if __name__ == "__main__" :
    demo_values = [np.random.normal(0.05, 0.02) for _ in range(60000)]
    print compute_percentile(demo_values, 0.065)
  • \$\begingroup\$ You are right - the minimize function adds nothing. I found this unintuitive. \$\endgroup\$ – kilojoules Mar 18 '16 at 21:32

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.