相关疑难解决方法(0)

我有输入数组A.

 A[0], A[1], ... , A[N-1]

我希望函数Max(T,A)返回B代表A在大小T所在的前一个移动窗口上的最大值

 B[i+T] = Max(A[i], A[i+T])

通过使用最大堆来跟踪当前移动窗口A [i]到A [i + T]的最大值,该算法产生O(N log(T))最坏情况.

我想知道有更好的算法吗？也许是O(N)算法

我想创建一个数组,它保存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()以某种方式使用,但无法找到实现目标的方法.

任何想法如何有效地做到这一点？