gruppo Python array a, e sintetizzare matrice b - Rappresentazione

Question

Dati due schiere ordinate di stesse lunghezze A e B:

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

mi piacerebbe gruppo dagli elementi in una:

aResult = [7,3,5] 

somma sugli elementi di b (Esempio utilizzato per sintetizzare una funzione di densità di probabilità):

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

alternativa, un casuale e bi n python:

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

Ho due approcci, che sicuramente sono lontani dal limite inferiore delle prestazioni. Approccio 1 (almeno piacevole e breve): Tempo: 0,769315958023

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

Approccio 2 (numpy.groupby, terribilmente lento) Tempo: 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])) 

Aggiornamento: Approach3, da Pablo. Tempo: 1.0265750885

def approach_Pablo(a,b):  

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

Aggiornamento: Approccio 4, di Unutbu. Tempo: 0,184849023819 [VINCITORE finora, ma come intero solo]

def unique_Unutbu(a,b): 

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

Forse qualcuno trova una soluzione intelligente a questo problema di me :)

Answer 1

Se a è composto di int < 2 ** 31-1 (cioè, se a ha valori che può andare bene in DTYPE int32), allora si potrebbe utilizzare np.bincount con i pesi:

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) rendimenti [3 5 7], in modo che il risultato appare in un ordine diverso:

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

Un potenziale problema con l'utilizzo di np.bincount è che restituisce un array la cui lunghezza è uguale al valore massimo in a. Se a contiene anche un elemento con valore vicino a 2 ** 31-1, quindi bincount dovrebbe allocare un array di dimensioni 8*(2**31-1) byte (o 16GiB).

Quindi np.bincount potrebbe essere la soluzione più rapida per gli array a che hanno una lunghezza grande, ma non valori elevati. Per gli array a che hanno una lunghezza ridotta (e valori grandi o piccoli), l'utilizzo di uno collections.defaultdict potrebbe essere più veloce.

Modifica: vedere J.F. Sebastian's solution per un modo per aggirare il problema dei valori interi e dei valori di grandi dimensioni.

Answer 2

Che ne dite di questo approccio:

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 

Si esegue iterazione su ciascun elemento solo una volta e si utilizza un dizionario per una ricerca rapida. Se si vuole veramente due array separati come risultato, alla fine, si può chiedere loro:

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

Answer 3

Ecco approccio simile a @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 

Permette tipo non intero per a matrice. Permette grandi valori nell'array a. Restituisce gli elementi a in un ordine ordinato. Se è preferibile, è possibile ripristinare facilmente l'ordine originale utilizzando l'argomento della funzione np.unique().

Le prestazioni peggiorano con l'aumento del numero di elementi univoci in a. È 4 volte più lento della versione di @ unutbu sui dati della tua domanda.

Ho effettuato performance comparison con altri tre metodi. I leader sono: per gli array di numeri interi - hash-based implementation in Cython; per gli array double (per l'input size 10000) - sort-based impl. anche in Cython.