Python - 加快查找大于阈值的集合百分位数

Question

我需要找到一组数字的哪个百分位数超过阈值。有没有办法加快速度？我的实现对于预期的应用程序来说太慢了。万一这改变了什么，我正在使用mpirun -np 100 python program.py运行我的程序。我不能使用 numba，因为该程序的其余部分使用 try/except 语句。

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))
for i in np.arange(0,100,0.001):
    if np.percentile(my_vals,i) > threshold_val:
        perc = 1*i
        break
else: perc = 100

Answer 1

由于高斯（正态）分布产生钟形曲线，因此您应该能够计算出最优概率最高的百分位数，然后编写代码以首先检查那里，然后使用修改后的二叉搜索来查找最佳最低阈值。

例如，如果您确定您的参数最有可能支持例如 17.951（这只是一个例子，我实际上并没有费心计算它），那么从该点附近开始，而不是从 0 开始。 将其视为二分搜索 - 从 0 开始下限，从 100.0 开始上限，并将点设置为将列表平分为分布的最佳百分位数。

如果您当前的上限超过 threshold_val，则平分下半部分

以找到匹配的最低值;如果未超过阈值，则平分上半部分，依此类推。 因此，例如，在 0.000 到 100.000 的范围内，如果您从 17.951 开始并发现它没有高于阈值，请调整到 17.952 到 100.000 的边界并尝试 58.976（介于两者之间）。 一旦找到高于阈值的值，就使用该值作为上限（因为它是非最佳答案）。 继续此过程，直到下限和上限相距 0.001，这将为您提供最佳答案。 平均而言，您应该运行大约 17 个测试，而不是 100,000 个。

如果您的正态分布发生变化，您还可以自动计算最优值，因为分布会产生钟形曲线，并且无论如何您都会根据参数知道该钟形曲线的统计数据。

解决方案只需查找百分位数高于阈值的最小值，因此此方法应最大程度地减少需要检查的样本数。

还有一个提示：np.percentile 必须在代码中对my_vals进行 100,000 次排序;我不知道预排序列表是否有帮助，但可能值得检查（您可能需要测试几个可能的排序参数，因为它似乎没有记录它的排序方向）。

Answer 2

您可以通过对值进行排序并搜索超过阈值的第一个值来直接找到解决方案。 百分位数是此元素之前的数组值的分数：

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))
from bisect import bisect_right
print bisect_right(sorted(my_vals),threshold_val)/float(len(my_vals))*100