python - numpy.unique vs collections.Counter 性能问题
问题描述
我正在尝试计算成对值的出现次数。运行以下代码时,numpy 版本(pairs_frequency2)比依赖于 collections.Counter 的版本慢 50% 以上(当点数增加时会变得更糟)。有人可以解释原因。
是否有可能的 numpy 重写以实现更好的性能?
提前致谢。
import numpy as np
from collections import Counter
def pairs_frequency(x, y):
counts = Counter(zip(x, y))
res = np.array([[f, a, b] for ((a, b), f) in counts.items()])
return res[:, 0], res[:, 1], res[:, 2]
def pairs_frequency2(x, y):
unique, counts = np.unique(np.column_stack((x,y)), axis=0, return_counts=True)
return counts, unique[:,0], unique[:,1]
x = np.random.randint(low=1, high=11, size=50000)
y = x + np.random.randint(1, 5, size=x.size)
%timeit pairs_frequency(x, y)
%timeit pairs_frequency2(x, y)
解决方案
numpy.unique
对其参数进行排序,因此其时间复杂度为 O(n*log(n))。看起来这个Counter
类可能是 O(n)。
如果您的数组中的值是不是太大的非负整数,则此版本非常快:
def pairs_frequency3(x, y, maxval=15):
z = maxval*x + y
counts = np.bincount(z)
pos = counts.nonzero()[0]
ux, uy = np.divmod(pos, maxval)
return counts[pos], ux, uy
设置为 1 加上和maxval
中的最大值。(您可以删除参数,并添加代码以查找函数中的最大值。)x
y
时间(x
并y
在问题中生成):
In [13]: %timeit pairs_frequency(x, y)
13.8 ms ± 77.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [14]: %timeit pairs_frequency2(x, y)
32.9 ms ± 631 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
In [15]: %timeit pairs_frequency3(x, y)
129 µs ± 1.03 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
注意第三个结果的时间单位变化。
pairs_frequency3
以与 相同的顺序返回数组pairs_frequency2
,因此很容易验证它们是否返回相同的值:
In [26]: counts2, x2, y2 = pairs_frequency2(x, y)
In [27]: counts3, x3, y3 = pairs_frequency3(x, y)
In [28]: np.all(counts2 == counts3) and np.all(x2 == x3) and np.all(y2 == y3)
Out[28]: True