在列表中查找排名和百分比排名

Question

我正在处理一些非常大的列表（>100 万行），我正在尝试找到一种快速（最快？）的方法，给定一个浮点数，与列表相比对浮点数进行排名浮动，并找到它与列表范围相比的百分比排名。这是我的尝试，但速度非常慢：

X =[0.595068426145485,
0.613726840488019,
1.1532608695652,
1.92952380952385,
4.44137931034496,
3.46432160804035,
2.20331487122673,
2.54736842105265,
3.57702702702689,
1.93202764976956,
1.34720184204056,
0.824997304105564,
0.765782842381996,
0.615110856990126,
0.622708022872803,
1.03211045820975,
0.997225012974318,
0.496352327702226,
0.67103858866700,
0.452224068868272,
0.441842124852685,
0.447584524952608,
0.4645525042246]

val = 1.5
arr = np.array(X) #X is actually a pandas column, hence the conversion
arr = np.insert(arr,1,val, axis=None) #insert the val into arr, to then be ranked
st  = np.sort(arr)

RANK      = float([i for i,k in enumerate(st) if k == val][0])+1 #Find position
PCNT_RANK = (1-(1-round(RANK/len(st),6)))*100 #Find percentage of value compared to range


print RANK, PCNT_RANK
>>> 17.0 70.8333

对于百分比排名，我可能会构建一个分布并从中抽取样本，但还不太确定，欢迎任何建议...它将被大量使用，因此任何加速都会是有利的。

谢谢。

Answer 1

排序数组似乎很慢。如果不需要数组最后排序，那么numpy的布尔运算更快

arr = np.array(X)
bool_array = arr < val # Returns boolean array
RANK = float(np.sum(bool_array))
PCT_RANK = RANK/len(X)

或者，更好的是，使用列表理解并避免使用 numpy。

RANK = float(sum([x<val for x in X]))
PCT_RANK = RANK/len(X)

做一些计时，上面的 numpy 解决方案在我的系统上给出了 6.66 us，而列表理解方法给出了 3.74 us。

Answer 2

您的代码的两个缓慢部分是：

st = np.sort(arr)。对列表进行排序平均需要 O(n log n) 时间，其中 n 是列表的大小。
RANK = float([i for i, k in enumerate(st) if k == val][0]) + 1。遍历列表需要 O(n) 时间。

如果您不需要对列表进行排序，那么正如@ChrisMueller 指出的那样，您可以只迭代一次而不进行排序，这需要 O(n) 时间并且将是最快的选择。

如果您确实需要对列表进行排序（或者可以访问预先排序的列表），那么第二步最快的选择是RANK = np.searchsorted(st, val) + 1。由于列表已经排序，通过二分查找查找索引只需要 O(log n) 时间，而不必遍历整个列表。这仍然比您的原始代码快很多。

在列表中查找排名和百分比排名

Find rank and percentage rank in list

python

performance

numpy

rank

pandas