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.
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
LENGTH = 100000 g = np.random.randint(low=0, high=LENGTH/2, size=LENGTH) v = np.random.rand(LENGTH)
vm = pd.DataFrame(dict(group=g, value=v)).groupby('group').value.cummax() vm.eq(pir1(g, v)).all() True
gráfico del título
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:
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
results.T.plot.barh()
¡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)]
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