Acelerar Pandas Cummin / Cummax

cummax funciones de pandas cummax y cummax parecen ser muy lentas para mi caso de uso con muchos grupos. ¿Cómo puedo acelerarlos?

Actualizar

 import pandas as pd import numpy as np from collections import defaultdict def cummax(g, v): df1 = pd.DataFrame(g, columns=['group']) df2 = pd.DataFrame(v) df = pd.concat([df1, df2], axis=1) result = df.groupby('group').cummax() result = result.values return result def transform(g, v): df1 = pd.DataFrame(g, columns=['group']) df2 = pd.DataFrame(v) df = pd.concat([df1, df2], axis=1) result = df.groupby('group').transform(lambda x: x.cummax()) result = result.values return result def itertuples(g, v): df1 = pd.DataFrame(g, columns=['group']) df2 = pd.DataFrame(v) df = pd.concat([df1, df2], axis=1) d = defaultdict(list) result = [np.nan] * len(g) def d_(g, v): d[g].append(v) if len(d[g]) > 1: d[g][-1] = tuple(max(a,b) for (a,b) in zip(d[g][-2], d[g][-1])) return d[g][-1] for row in df.itertuples(index=True): index = row[0] result[index] = d_(row[1], row[2:]) result = np.asarray(result) return result def numpy(g, v): d = defaultdict(list) result = [np.nan] * len(g) def d_(g, v): d[g].append(v) if len(d[g]) > 1: d[g][-1] = np.maximum(d[g][-2], d[g][-1]) return d[g][-1] for i in range(len(g)): result[i] = d_(g[i], v[i]) result = np.asarray(result) return result LENGTH = 100000 g = np.random.randint(low=0, high=LENGTH/2, size=LENGTH) v = np.random.rand(LENGTH, 40) %timeit r1 = cummax(g, v) %timeit r2 = transform(g, v) %timeit r3 = itertuples(g, v) %timeit r4 = numpy(g, v) 

da

 1 loop, best of 3: 22.5 s per loop 1 loop, best of 3: 18.4 s per loop 1 loop, best of 3: 1.56 s per loop 1 loop, best of 3: 325 ms per loop 

¿Tiene alguna otra sugerencia de cómo puedo mejorar mi código?

Antiguo

 import pandas as pd import numpy as np LENGTH = 100000 df = pd.DataFrame( np.random.randint(low=0, high=LENGTH/2, size=(LENGTH,2)), columns=['group', 'value']) df.groupby('group').cummax() 

Usaremos defaultdict donde el valor predeterminado será -np.inf porque tomaré los valores máximos y quiero un valor predeterminado que sea mayor que todo.

solución

Dada una matriz de grupos g valores para acumular máximos v

 def pir1(g, v): d = defaultdict(lambda: -np.inf) result = np.empty(len(g)) def d_(g, v): d[g] = max(d[g], v) return d[g] for i in range(len(g)): result[i] = d_(g[i], v[i]) return result 

demostración

 LENGTH = 100000 g = np.random.randint(low=0, high=LENGTH/2, size=LENGTH) v = np.random.rand(LENGTH) 

exactitud

 vm = pd.DataFrame(dict(group=g, value=v)).groupby('group').value.cummax() vm.eq(pir1(g, v)).all() True 



Bucear profundo

Comparar con la respuesta de Divakar.

gráfico del título
introduzca la descripción de la imagen aquí

código
Me tomé algunas libertades con la función de Divakar para hacerla precisa.

 %%cython import numpy as np from collections import defaultdict # this is a cythonized version of the next function def pir1(g, v): d = defaultdict(lambda: -np.inf) result = np.empty(len(g)) def d_(g, v): d[g] = max(d[g], v) return d[g] for i in range(len(g)): result[i] = d_(g[i], v[i]) return result 

 def pir2(g, v): d = defaultdict(lambda: -np.inf) result = np.empty(len(g)) def d_(g, v): d[g] = max(d[g], v) return d[g] for i in range(len(g)): result[i] = d_(g[i], v[i]) return result def argsort_unique(idx): # Original idea : http://stackoverflow.com/a/41242285/3293881 n = idx.size sidx = np.empty(n,dtype=int) sidx[idx] = np.arange(n) return sidx def div1(groupby, value): sidx = np.argsort(groupby,kind='mergesort') sorted_groupby, sorted_value = groupby[sidx], value[sidx] # Get shifts to be used for shifting each group mx = sorted_value.max() + 1 shifts = sorted_groupby * mx # Shift and get max accumlate along value col. # Those shifts helping out in keeping cummulative max within each group. group_cummaxed = np.maximum.accumulate(shifts + sorted_value) - shifts return group_cummaxed[argsort_unique(sidx)] def div2(groupby, value): sidx = np.argsort(groupby, kind='mergesort') sorted_groupby, sorted_value = groupby[sidx], value[sidx] # factorize groups to integers sorted_groupby = np.append( 0, sorted_groupby[1:] != sorted_groupby[:-1]).cumsum() # Get shifts to be used for shifting each group mx = sorted_value.max() + 1 shifts = (sorted_groupby - sorted_groupby.min()) * mx # Shift and get max accumlate along value col. # Those shifts helping out in keeping cummulative max within each group. group_cummaxed = np.maximum.accumulate(shifts + sorted_value) - shifts return group_cummaxed[argsort_unique(sidx)] 

NOTAS:

  • Fue necesario factorizar los grupos en la solución de Divakar para generalizarlo.

exactitud

grupos enteros
Sobre grupos basados ​​en enteros, tanto div1 como div2 producen los mismos resultados

 np.isclose(div1(g, v), pir1(g, v)).all() True np.isclose(div2(g, v), pir1(g, v)).all() True 

grupos generales
Sobre los grupos basados ​​en cadenas y flotadores div1 vuelve inexacto pero se arregla fácilmente

 g = g / 1000000 np.isclose(div1(g, v), pir1(g, v)).all() False np.isclose(div2(g, v), pir1(g, v)).all() True 

prueba de tiempo

 results = pd.DataFrame( index=pd.Index(['pir1', 'pir2', 'div1', 'div2'], name='method'), columns=pd.Index(['Large', 'Medium', 'Small'], name='group size')) size_map = dict(Large=100, Medium=10, Small=1) from timeit import timeit for i in results.index: for j in results.columns: results.set_value( i, j, timeit( '{}(g // size_map[j], v)'.format(i), 'from __main__ import {}, size_map, g, v, j'.format(i), number=100 ) ) results 

introduzca la descripción de la imagen aquí

 results.T.plot.barh() 

introduzca la descripción de la imagen aquí

Enfoque propuesto

¡Vamos a traer algo de magia NumPy a la mesa! Bueno, vamos a explotar np.maximum.accumulate .

Explicación

Para ver cómo maximum.accumulate podría ayudarnos, supongamos que tenemos los grupos alineados secuencialmente.

Consideremos un ejemplo de grouby:

 grouby column : [0, 0, 0, 1, 1, 2, 2, 2, 2, 2] 

Consideremos un valor de muestra:

 value column : [3, 1, 4, 1, 3, 3, 1, 5, 2, 4] 

El uso de maximum.accumulate simplemente en el value no nos dará el resultado deseado, ya que necesitamos hacer estas acumulaciones solo dentro de cada grupo. Para hacerlo, un truco sería compensar a cada grupo del grupo anterior.

Podría haber pocos métodos para hacer ese trabajo de compensación. Una forma fácil sería compensar cada grupo con un desplazamiento de max de value + 1 más que el anterior. Para la muestra, ese desplazamiento sería 6 . Entonces, para el segundo grupo, agregaremos 6 , el tercero como 12 y así sucesivamente. Por lo tanto, el value modificado sería:

 value column : [3, 1, 4, 7, 9, 15, 13, 17, 14, 16] 

Ahora, podemos usar maximum.accumulate y las acumulaciones se restringirían dentro de cada grupo –

 value cummaxed: [3, 3, 4, 7, 9, 15, 15, 17, 17, 17]) 

Para volver a los valores originales, reste las compensaciones que se agregaron antes.

 value cummaxed: [3, 3, 4, 1, 3, 3, 3, 5, 5, 5]) 

Ese es nuestro resultado deseado!

Al principio, asumimos que los grupos eran secuenciales. Para obtener los datos en ese formato, usaremos np.argsort(groupby,kind='mergesort') para obtener los índices ordenados de manera que mantenga el orden de los mismos números y luego usaremos estos índices para indexar en la columna groupby .

Para tener en cuenta los elementos negativos de groupby, solo tenemos que compensar max() - min() lugar de max() .

Por lo tanto, la implementación se vería algo así:

 def argsort_unique(idx): # Original idea : http://stackoverflow.com/a/41242285/3293881 n = idx.size sidx = np.empty(n,dtype=int) sidx[idx] = np.arange(n) return sidx def numpy_cummmax(groupby, value, factorize_groupby=0): # Inputs : 1D arrays. # Get sorted indices keeping the order. Sort groupby and value cols. sidx = np.argsort(groupby,kind='mergesort') sorted_groupby, sorted_value = groupby[sidx], value[sidx] if factorize_groupby==1: sf = np.concatenate(([0], np.flatnonzero(sorted_groupby[1:] != \ sorted_groupby[:-1])+1, [sorted_groupby.size] )) sorted_groupby = np.repeat(np.arange(sf.size-1), sf[1:] - sf[:-1]) # Get shifts to be used for shifting each group mx = sorted_groupby.max()-sorted_groupby.min()+1 shifts = sorted_groupby*mx # Shift and get max accumlate along value col. # Those shifts helping out in keeping cummulative max within each group. group_cummaxed = np.maximum.accumulate(shifts + sorted_value) - shifts return group_cummaxed[argsort_unique(sidx)] 

Test de ejecución y verificación.

Verificación

1) Groupby como ints:

 In [58]: # Setup with groupby as ints ...: LENGTH = 1000 ...: g = np.random.randint(low=0, high=LENGTH/2, size=LENGTH) ...: v = np.random.rand(LENGTH) ...: In [59]: df = pd.DataFrame(np.column_stack((g,v)),columns=['group', 'value']) In [60]: # Verify results ...: out1 = df.groupby('group').cummax() ...: out2 = numpy_cummmax(df['group'].values, df['value'].values) ...: print np.allclose(out1.values.ravel(), out2, atol=1e-5) ...: True 

2) Groupby como flotadores:

 In [10]: # Setup with groupby as floats ...: LENGTH = 100000 ...: df = pd.DataFrame(np.random.randint(0,LENGTH//2,(LENGTH,2))/10.0, \ ...: columns=['group', 'value']) In [18]: # Verify results ...: out1 = df.groupby('group').cummax() ...: out2 = numpy_cummmax(df['group'].values, df['value'].values, factorize_groupby=1) ...: print np.allclose(out1.values.ravel(), out2, atol=1e-5) ...: True 

Tiempos –

1) Groupby como ints (igual que la configuración utilizada para los tiempos en la pregunta):

 In [24]: LENGTH = 100000 ...: g = np.random.randint(0,LENGTH//2,(LENGTH))/10.0 ...: v = np.random.rand(LENGTH) ...: In [25]: %timeit numpy(g, v) # Best solution from posted question 1 loops, best of 3: 373 ms per loop In [26]: %timeit pir1(g, v) # @piRSquared's solution-1 1 loops, best of 3: 165 ms per loop In [27]: %timeit pir2(g, v) # @piRSquared's solution-2 1 loops, best of 3: 157 ms per loop In [28]: %timeit numpy_cummmax(g, v) 100 loops, best of 3: 18.3 ms per loop 

2) Groupby como flotadores:

 In [29]: LENGTH = 100000 ...: g = np.random.randint(0,LENGTH//2,(LENGTH))/10.0 ...: v = np.random.rand(LENGTH) ...: In [30]: %timeit pir1(g, v) # @piRSquared's solution-1 1 loops, best of 3: 157 ms per loop In [31]: %timeit pir2(g, v) # @piRSquared's solution-2 1 loops, best of 3: 156 ms per loop In [32]: %timeit numpy_cummmax(g, v, factorize_groupby=1) 10 loops, best of 3: 20.8 ms per loop In [34]: np.allclose(pir1(g, v),numpy_cummmax(g, v, factorize_groupby=1),atol=1e-5) Out[34]: True