Quickly find percentile with high precision

Question

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]

Answer 1

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)