减少峰谷 [英] Cut peaks and troughs

问题描述

这是我想使用numpy实现的算法：

Here is an algorithm I would like to implement using numpy:

对于给定的一维数组，计算滑动窗口上的最大值和最小值。
创建一个新数组，其第一个值等于给定数组中的第一个值。
对于每个后续值，从滑动窗口的最小值和最大值之间裁剪插入到新数组中的先前值。

For a given 1D array, calculate the maximum and the minimum over a sliding window. Create a new array, with the first value equals to the first value in the given array. For each subsequent values, clip the previous value inserted in the new array between the min and the max from the sliding window.

作为示例，让我们数组 a = [3，4，5，4，3，2，3，3] 和大小为3的滑动窗口。我们找到了min和max：

As an example, let's take the array a=[3, 4, 5, 4, 3, 2, 3, 3] and a sliding window of size 3. We find for min and max:

min = [3, 4, 3, 2, 2, 2]
max = [5, 5, 5, 4, 3, 3]

现在，我们的输出数组将从<$ c中的第一个元素开始$ c> a ，所以它是 3 。对于下一个值，我将3（插入的最后一个值）剪辑为4到5（在索引1处找到的最小值和最大值）之间。结果是4。对于下一个值，我将4修剪在3到5之间。仍然是4。依此类推。所以我们终于有了：

Now our output array will start with the first element from a, so it's 3. And for the next value, I clip 3 (the last value inserted) between 4 and 5 (the min and max found at index 1). The result is 4. For the next value I clip 4 between 3 and 5. It's still 4. And so on. So we finally have:

output = [3, 4, 4, 4, 3, 3]

我找不到在我的代码中避免使用python for循环的方法。这是我目前的情况：

I cannot find a way to avoid using a python for loop in my code. Here is what I have for the moment:

def second_window(array, samples):
    sample_idx = samples - 1
    output = np.zeros_like(array[0:-sample_idx])
    start, stop = 0, len(array)
    last_value = array[0]
    # Sliding window is a deque of length 'samples'.
    sliding_window = deque(array[start : start+sample_idx], samples)
    for i in xrange( stop - start - sample_idx):
        # Get the next value in sliding window. After the first loop,
        # the left value gets discarded automatically.
        sliding_window.append(array[start + i + sample_idx])
        min_value, max_value = min(sliding_window), max(sliding_window)
        # Clip the last value between sliding window min and max
        last_value = min( max(last_value, min_value), max_value)
        output[start + i] = last_value
    return output

仅使用numpy就能实现此结果吗？

Would it be possible to achieve this result with only numpy?

推荐答案

我认为你不能。您有时可以使用无缓冲的函数来进行这种迭代计算，但实际情况并非如此。但是，让我ellaborate ...

I don't think you can. You can sometime do this kind of iterative computation with unbuffered ufuncs, but this isn't the case. But let me ellaborate...

好的，首先可以最小化/最大化窗口计算速度：

OK, first the windowing an min/max calculations can be done much faster:

>>> a = np.array([3, 4, 5, 4, 3, 2, 3, 3])
>>> len_a = len(a)
>>> win = 3
>>> win_a = as_strided(a, shape=(len_a-win+1, win), strides=a.strides*2)
>>> win_a
array([[3, 4, 5],
       [4, 5, 4],
       [5, 4, 3],
       [4, 3, 2],
       [3, 2, 3],
       [2, 3, 3]])
>>> min_ = np.min(win_a, axis=-1)
>>> max_ = np.max(win_a, axis=-1)

现在，让我们创建并填充您的输出数组：

Now, lets create and fill up your output array:

>>> out = np.empty((len_a-win+1,), dtype=a.dtype)
>>> out[0] = a[0]

如果 np.clip 的地方，我们可以尝试这样做：

If np.clip where a ufunc, we could then try to do:

>>> np.clip(out[:-1], min_[1:], max_[1:], out=out[1:])
array([4, 3, 3, 3, 3])
>>> out
array([3, 4, 3, 3, 3, 3])

但这是行不通的，因为 np.clip 不是ufunc，而且似乎涉及一些缓冲。

But this doesn't work, because np.clip is not a ufunc, and there seems to be some buffering involved.

如果分别应用 np.minimum 和 np.maximum ，那么它并不总是有效：

And if you apply np.minimum and np.maximum separately, then it doesn't always work:

>>> np.minimum(out[:-1], max_[1:], out=out[1:])
array([3, 3, 3, 3, 3])
>>> np.maximum(out[1:], min_[1:], out=out[1:])
array([4, 3, 3, 3, 3])
>>> out
array([3, 4, 3, 3, 3, 3])

尽管对于您的特定情况，反转另一个确实有效：

although for your particular case reversing the other does work:

>>> np.maximum(out[:-1], min_[1:], out=out[1:])
array([4, 4, 4, 4, 4])
>>> np.minimum(out[1:], max_[1:], out=out[1:])
array([4, 4, 4, 3, 3])
>>> out
array([3, 4, 4, 4, 3, 3])

这篇关于减少峰谷的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！