# Quickly find percentile with high precision

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]

• 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? – Mathias Ettinger Mar 18 '16 at 19:23
• 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 – 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)

• You are right - the minimize function adds nothing. I found this unintuitive. – kilojoules Mar 18 '16 at 21:32