python - 计算每个值本身的大于操作的有效方法

Question

我有一个包含实数值的 numpy 向量。对于这个向量中的每个值，我想计算大于值本身的值的数量。

例如:

input: array([1.,2.,3.,1.,1.,0.,10.]) # numpy array
output: array([3, 2, 1, 3, 3, 6, 0])

我的第一个想法是:

# pandas
df[column].apply(lambda x: (df[column] > x).sum())

# numpy equivalent 
[(arr>x).sum() for x in arr]

但是速度很慢。有没有有效的方法来做到这一点？

Answer 1

一个简单的方法是使用 Python 的 bisect 模块:

import bisect
array = [1.,2.,3.,1.,1.,0.,10.]
n = len(array)
sorted_array = sorted(array)
print [n - bisect.bisect(sorted_array, val) for val in array]

这将创建数组的排序副本，然后使用二分查找排序数组以确定对于每个原始元素，有多少值更大。

与原始代码的 O(n^2) 相比，该算法的时间复杂度为 O(n logn)。为了进行比较，我在 10 万个元素的输入数组上对其进行了测试，速度提高了 200 倍。

附言整个事情可以重写为 NumPy 一行代码:

output = array.size - np.searchsorted(np.sort(array), array, side='right')

在我的 100K 元素测试阵列上，它比原来的快 1300 倍。