Revisamos de forma completamente cada secciones en nuestra página web con el objetivo de enseñarte siempre información certera y actual.
Solución:
Enfoque #1: podrías usar 1D filtro máximo de Scipy –
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]
Enfoque #2: Aquí hay otro enfoque con strides : strided_app para crear un 2D versión desplazada como vista en el array de manera bastante eficiente y eso debería permitirnos usar cualquier operación de reducción personalizada a lo largo del segundo eje después:
def max_filter1d_valid_strided(a, W):
return strided_app(a, W, S=1).max(axis=1)
Prueba de tiempo de ejecución –
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 tiene un método de balanceo tanto para Series como para DataFrames, y eso podría ser útil aquí:
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]
Para mantener la coherencia, puede obligar a cada elemento de lst1 a 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]
He probado varias variantes ahora y declararía la versión Pandas como la ganadora de esta carrera de rendimiento. Probé varias variantes, incluso usando un árbol binario (implementado en Python puro) para calcular rápidamente máximos de subrangos arbitrarios. (Fuente disponible bajo demanda). El mejor algoritmo que se me ocurrió fue una simple ventana rodante usando un búfer de anillo; el máximo de eso solo necesitaba volver a calcularse por completo si el valor máximo actual se eliminó en esta iteración; de lo contrario, se mantendría o aumentaría al siguiente valor nuevo. En comparación con las bibliotecas antiguas, esta implementación de Python puro fue más rápida que el resto.
Al final, descubrí que la versión de las bibliotecas en cuestión era muy relevante. Las versiones bastante antiguas que todavía usaba eran mucho más lentas que las versiones modernas. Aquí están los números para 1 millón de números, rodando al máximo con una ventana de tamaño 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
Aquí está la implementación de la versión numpy pura usando un búfer de anillo:
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()))
Para mi entrada, esto funciona muy bien porque estoy manejando datos de audio con muchos picos en todas las direcciones. Si pones una señal constantemente decreciente (por ejemplo, -np.arange(10000000)), entonces experimentará el peor de los casos (y tal vez debería invertir la entrada y la salida en tales casos).
Solo incluyo esto en caso de que alguien quiera hacer esta tarea en una máquina con bibliotecas antiguas.
Comentarios y puntuaciones del post
No se te olvide recomendar esta división si lograste el éxito.