Pythona grupę o macierzy A, a podsumowanie tablicy B - Wyniki

Question

podawana dwa nieuporządkowane tablice samej długości a i b:

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

Chciałbym grupie przez elementy w:

aResult = [7,3,5] 

zsumowanie tych elementów B (przykład zużytych podsumować gęstość):

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

Alternatywnie, losową a i BI n python:

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

Mam dwa podejścia, które z pewnością są dalekie od dolnej granicy wydajności. Approach 1 (przynajmniej ładne i krótkie): Godzina: 0,769315958023

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

Podejście 2 (numpy.groupby, strasznie wolno) Czas: 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])) 

Aktualizacja: Approach3 przez Pablo. Czas: 1.0265750885

def approach_Pablo(a,b):  

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

Aktualizacja: Podejście 4, przez Unutbu. Czas: ,184849023819 [WINNER do tej pory, ale tylko jako liczba całkowita]

def unique_Unutbu(a,b): 

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

Może ktoś znajdzie inteligentniejsze rozwiązanie tego problemu niż ja :)

Answer 1

jeśli a składa wskazówki < 2 ** 31-1 (to znaczy, jeśli a ma wartości, które może zmieścić się w dtype int32), a następnie można użyć np.bincount z ciężarkami:

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) powraca [3 5 7], więc wynik pojawia się w innej kolejności:

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

Jednym z potencjalnych problemów z używaniem np.bincount jest to, że zwraca tablicę, której długość jest równa wartości maksymalnej w a. Jeśli a zawiera nawet jeden element o wartości zbliżonej do 2 ** 31-1, wówczas bincount musiałby przydzielić tablicę o rozmiarze 8*(2**31-1) bajtów (lub 16GiB).

Więc np.bincount może być najszybszym rozwiązaniem dla tablic a które mają dużą długość, ale nie wielkie wartości. W przypadku tablic a, które mają małą długość (i duże lub małe wartości), użycie collections.defaultdict byłoby prawdopodobnie szybsze.

Edycja: Zobacz artykuł J.F. Sebastian's solution, aby poznać ograniczenia związane z wartościami całkowitymi i problemami z dużymi wartościami.

Answer 2

Jak o tym podejściu:

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 

Wykonuje się tylko iteracje po każdym elemencie i używa się słownika do szybkiego wyszukiwania. Jeśli naprawdę chcesz dwa oddzielne tablice wyników, jak w końcu można poprosić o nich:

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

Answer 3

Poniżej podobne podejście @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 

Pozwala typu niecałkowitą do a tablicy. Pozwala na duże wartości w tablicy a. Zwraca elementy a w posortowanej kolejności. Jeśli jest to pożądane, można łatwo przywrócić pierwotną kolejność, używając argumentu return_index funkcji return_index.

Jego wydajność pogarsza się wraz ze wzrostem liczby unikatowych elementów w zestawie a. Jest 4 razy wolniejsza od wersji @ unutbu na danych z twojego pytania.

Zrobiłem performance comparison z trzema dodatkowymi metodami. Liderzy są: dla liczb całkowitych - hash-based implementation w Cython; dla tablic double (dla rozmiaru wejściowego 10000) - sort-based impl. również w języku Cython.