Alf*_*lfe 11 python performance numpy max scipy
我想创建一个数组,它保存max()一个窗口移动通过给定的numpy数组的所有es.如果这听起来令人困惑,我很抱歉.我举个例子.输入:
[ 6,4,8,7,1,4,3,5,7,2,4,6,2,1,3,5,6,3,4,7,1,9,4,3,2 ]
窗口宽度为5的输出应为:
[ 8,8,8,7,7,7,7,7,7,6,6,6,6,6,6,7,7,9,9,9,9 ]
每个数字应为输入数组宽度为5的子数组的最大值:
[ 6,4,8,7,1,4,3,5,7,2,4,6,2,1,3,5,6,3,4,7,1,9,4,3,2 ]
\ / \ /
\ / \ /
\ / \ /
\ / \ /
[ 8,8,8,7,7,7,7,7,7,6,6,6,6,6,6,7,7,9,9,9,9 ]
我没有在numpy中找到一个可以做到这一点的开箱即用的功能(但是如果有的话我不会感到惊讶;我并不总是在考虑numpy开发人员的想法).我考虑创建一个移位的2D版本的输入:
[ [ 6,4,8,7,1,4,3,5,7,8,4,6,2,1,3,5,6,3,4,7,1 ]
[ 4,8,7,1,4,3,5,7,8,4,6,2,1,3,5,6,3,4,7,1,9 ]
[ 8,7,1,4,3,5,7,8,4,6,2,1,3,5,6,3,4,7,1,9,4 ]
[ 7,1,4,3,5,7,8,4,6,2,1,3,5,6,3,4,7,1,9,4,3 ]
[ 1,4,3,5,7,8,4,6,2,1,3,5,6,3,4,7,1,9,4,3,2 ] ]
然后我可以申请np.max(input, 0)这个并得到我的结果.但这在我的情况下似乎并不高效,因为我的数组和窗口宽度都可以很大(> 1000000条目和> 100000窗口宽度).数据会被窗口宽度的因素或多或少地炸毁.
我也考虑过np.convolve()以某种方式使用,但无法找到实现目标的方法.
任何想法如何有效地做到这一点？
方法#1:您可以使用1DScipy的最大过滤器 -
from scipy.ndimage.filters import maximum_filter1d
def max_filter1d_valid(a, W):
hW = (W-1)//2 # Half window size
return maximum_filter1d(a,size=W)[hW:-hW]
方法#2:这是另一种方法strides:strided_app创建一个2D移位版本作为视图进入数组非常有效,这应该让我们之后沿第二轴使用任何自定义缩减操作 -
def max_filter1d_valid_strided(a, W):
return strided_app(a, W, S=1).max(axis=1)
运行时测试 -
In [55]: a = np.random.randint(0,10,(10000))
# @Abdou's solution using pandas rolling
In [56]: %timeit pd.Series(a).rolling(5).max().dropna().tolist()
1000 loops, best of 3: 999 µs per loop
In [57]: %timeit max_filter1d_valid(a, W=5)
...: %timeit max_filter1d_valid_strided(a, W=5)
...:
10000 loops, best of 3: 90.5 µs per loop
10000 loops, best of 3: 87.9 µs per loop
Pandas为Series和DataFrames提供了一种滚动方法,可以在这里使用:
import pandas as pd
lst = [6,4,8,7,1,4,3,5,7,8,4,6,2,1,3,5,6,3,4,7,1,9,4,3,2]
lst1 = pd.Series(lst).rolling(5).max().dropna().tolist()
# [8.0, 8.0, 8.0, 7.0, 7.0, 8.0, 8.0, 8.0, 8.0, 8.0, 6.0, 6.0, 6.0, 6.0, 6.0, 7.0, 7.0, 9.0, 9.0, 9.0, 9.0]
为了保持一致性,您可以强制的每个元素lst1到int:
[int(x) for x in lst1]
# [8, 8, 8, 7, 7, 8, 8, 8, 8, 8, 6, 6, 6, 6, 6, 7, 7, 9, 9, 9, 9]
我现在已经尝试了几种变体，并将宣布 Pandas 版本是这场性能竞赛的赢家。我尝试了几种变体，甚至使用二叉树（用纯 Python 实现）来快速计算任意子范围的最大值。（可按需提供来源）。我自己想出的最好算法是使用环形缓冲区的普通滚动窗口；如果在本次迭代中删除当前最大值，则只需要完全重新计算最大值；否则它将保持或增加到下一个新值。与旧库相比，这个纯 Python 实现比其他库更快。
最后我发现有问题的库的版本是高度相关的。我主要仍在使用的相当旧的版本比现代版本慢得多。以下是 100 万个数字的数字，使用大小为 100k 的窗口滚动最大化：
old (slow HW) new (better HW)
scipy: 0.9.0: 21.2987391949 0.13.3: 11.5804400444
pandas: 0.7.0: 13.5896410942 0.18.1: 0.0551438331604
numpy: 1.6.1: 1.17417216301 1.8.2: 0.537392139435
这是使用环形缓冲区的纯 numpy 版本的实现：
def rollingMax(a, window):
def eachValue():
w = a[:window].copy()
m = w.max()
yield m
i = 0
j = window
while j < len(a):
oldValue = w[i]
newValue = w[i] = a[j]
if newValue > m:
m = newValue
elif oldValue == m:
m = w.max()
yield m
i = (i + 1) % window
j += 1
return np.array(list(eachValue()))
对于我的输入，这非常有效，因为我正在处理各个方向都有大量峰值的音频数据。如果您将一个不断减小的信号放入其中（例如-np.arange(10000000)），那么您将遇到最坏的情况（在这种情况下，也许您应该反转输入和输出）。
我只是包括这个以防有人想在带有旧库的机器上执行此任务。
从 开始Numpy 1.20，sliding_window_view提供了一种在元素窗口中滑动/滚动的方法。然后您可以找到最大的窗口：
from numpy.lib.stride_tricks import sliding_window_view
# values = np.array([6,4,8,7,1,4,3,5,7,2,4,6,2,1,3,5,6,3,4,7,1,9,4,3,2])
np.max(sliding_window_view(values, window_shape = 5), axis = 1)
# array([8, 8, 8, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 7, 7, 9, 9, 9, 9])
在哪里：
window_shape是滑动窗口的大小np.max(array, axis = 1)找到每个子数组的最大值滑动的中间结果为：
sliding_window_view(values, window_shape = 5)
# array([[6, 4, 8, 7, 1],
# [4, 8, 7, 1, 4],
# [8, 7, 1, 4, 3],
# ...
# [7, 1, 9, 4, 3],
# [1, 9, 4, 3, 2]])