grupo Python por matriz a, y resumir array b - Rendimiento

Question

Dados dos matrices no ordenadas de mismas longitudes A y B:

a = [7,3,5,7,5,7] 
b = [0.2,0.1,0.3,0.1,0.1,0.2] 

me gustaría grupo por los elementos en una:

aResult = [7,3,5] 

sumando sobre los elementos de b (Ejemplo utiliza para resumir una función de densidad de probabilidad):

bResult = [0.2 + 0.1 + 0.2, 0.1, 0.3 + 0.1] = [0.5, 0.1, 0.4] 

Alternativamente, un azar y bi n pitón:

import numpy as np 
a = np.random.randint(1,10,10000) 
b = np.array([1./len(a)]*len(a)) 

Tengo dos enfoques, que con seguridad se encuentran lejos de los límites de rendimiento inferior. Enfoque 1 (por lo menos agradable y corto): Tiempo: 0,769315958023

def approach_2(a,b): 
    bResult = [sum(b[i == a]) for i in np.unique(a)] 
    aResult = np.unique(a) 

Enfoque 2 (numpy.groupby, terriblemente lento) Hora: 4,65299129486

def approach_2(a,b): 
    tmp = [(a[i],b[i]) for i in range(len(a))] 
    tmp2 = np.array(tmp, dtype = [('a', float),('b', float)]) 
    tmp2 = np.sort(tmp2, order='a') 

    bResult = [] 
    aResult = [] 
    for key, group in groupby(tmp2, lambda x: x[0]): 
     aResult.append(key) 
     bResult.append(sum([i[1] for i in group])) 

Actualización: Approach3, de Pablo. Tiempo: 1.0265750885

def approach_Pablo(a,b):  

    pdf = defaultdict(int); 
    for x,y in zip(a,b): 
     pdf[x] += y 

Actualización: Approach 4, by Unutbu. Tiempo: ,184849023819 [GANADOR hasta ahora, pero un número entero como única]

def unique_Unutbu(a,b): 

    x=np.bincount(a,weights=b) 
    aResult = np.unique(a) 
    bResult = x[aResult] 

Tal vez alguien encuentra una solución más elegante a este problema que yo :)

Answer 1

Si a se compone de enteros < 2 ** 31-1 (es decir, si a tiene valores que pueden caber en dtype int32), entonces se podría utilizar np.bincount con pesas:

import numpy as np 
a = [7,3,5,7,5,7] 
b = [0.2,0.1,0.3,0.1,0.1,0.2] 

x=np.bincount(a,weights=b) 
print(x) 
# [ 0. 0. 0. 0.1 0. 0.4 0. 0.5] 

print(x[[7,3,5]]) 
# [ 0.5 0.1 0.4] 

np.unique(a) vuelve [3 5 7], por lo que el resultado aparece en un orden diferente:

print(x[np.unique(a)]) 
# [ 0.1 0.4 0.5] 

Un posible problema con el uso de np.bincount es que devuelve una matriz cuya longitud es igual al valor máximo en a. Si a contiene incluso un elemento con un valor cercano a 2 ** 31-1, entonces bincount tendría que asignar una matriz de tamaño 8*(2**31-1) bytes (o 16GiB).

Así que np.bincount podría ser la solución más rápida para las matrices a que tienen una gran longitud, pero no grandes valores. Para las matrices a que tienen una longitud pequeña (y valores grandes o pequeños), usar un collections.defaultdict probablemente sea más rápido.

Editar: Vea J.F. Sebastian's solution para solucionar el problema de restricción de valores enteros y valores altos.

Answer 2

¿Qué hay de este enfoque:

from collections import defaultdict 
pdf = defaultdict(int) 
a = [7,3,5,7,5,7] 
b = [0.2,0.1,0.3,0.1,0.1,0.2] 
for x,y in zip(a,b): 
    pdf[x] += y 

Solo itera sobre cada elemento una vez y utiliza un diccionario para una búsqueda rápida. Si realmente quiere dos matrices independientes como resultado en el final se puede pedir para ellos:

aResult = pdf.keys() 
bResult = pdf.values() 

Answer 3

Así es enfoque similar al @unutbu's one:

import numpy as np 

def f(a, b): 
    result_a, inv_ndx = np.unique(a, return_inverse=True) 
    result_b = np.bincount(inv_ndx, weights=b) 
    return result_a, result_b 

Permite tipo no entero para a matriz. Permite valores grandes en a matriz. Devuelve a elementos en un orden ordenado. Si es deseable, es fácil restablecer el orden original usando el argumento return_index de la función np.unique().

Su rendimiento empeora a medida que aumenta el número de elementos únicos en a. Es 4 veces más lenta que la versión de @ unutbu en los datos de su pregunta.

He hecho performance comparison con tres métodos adicionales. Los líderes son: para matrices de enteros - hash-based implementation en Cython; para las matrices double (para el tamaño de entrada 10000) - sort-based impl. también en Cython.