Python nhóm bằng mảng một, và tóm tắt mảng b - Hiệu suất

Question

Với hai mảng có thứ tự của cùng một độ dài a và b:

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

Tôi muốn nhóm của các yếu tố trong một:

aResult = [7,3,5] 

tổng hợp trên các yếu tố trong b (Ví dụ sử dụng để tóm tắt một hàm mật độ xác suất):

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

Ngoài ra, một cách ngẫu nhiên và bi n python:

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

Tôi có hai cách tiếp cận, chắc chắn nằm ngoài ranh giới hiệu suất thấp hơn. Tiếp cận 1 (ít nhất là tốt đẹp và ngắn): Thời gian: 0,769315958023

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

Tiếp cận 2 (numpy.groupby, khủng khiếp chậm) Thời gian: 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])) 

Cập nhật: Approach3, bởi Pablo. Thời gian: 1.0265750885

def approach_Pablo(a,b):  

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

Cập nhật: Cách tiếp cận 4, bởi Unutbu. Thời gian: ,184849023819 [WINNER SO FAR, nhưng một số nguyên như chỉ]

def unique_Unutbu(a,b): 

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

Có lẽ ai đó tìm thấy một giải pháp thông minh hơn cho vấn đề này hơn tôi :)

Answer 1

Nếu a gồm ints < 2 ** 31-1 (có nghĩa là, nếu a có giá trị mà có thể phù hợp trong dtype int32), sau đó bạn có thể sử dụng np.bincount với trọng lượng:

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) lợi nhuận [3 5 7], vì vậy kết quả xuất hiện theo một thứ tự khác nhau:

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

Một vấn đề tiềm tàng khi sử dụng np.bincount là nó trả về một mảng có độ dài bằng giá trị lớn nhất trong a. Nếu a chứa ngay cả một phần tử có giá trị gần 2 ** 31-1, thì bincount sẽ phải phân bổ một mảng có kích thước 8*(2**31-1) byte (hoặc 16GiB).

Vì vậy, np.bincount có thể là giải pháp nhanh nhất cho mảng a có độ dài lớn, nhưng không phải là giá trị lớn. Đối với mảng a có chiều dài nhỏ (và giá trị lớn hoặc nhỏ), sử dụng collections.defaultdict có thể sẽ nhanh hơn.

Chỉnh sửa: Xem J.F. Sebastian's solution để biết cách xung quanh hạn chế số nguyên-giá trị và vấn đề có giá trị lớn.

Answer 2

Làm thế nào về phương pháp này:

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 

Bạn chỉ lặp lại từng phần tử một lần và sử dụng từ điển để tra cứu nhanh. Nếu bạn thực sự muốn hai mảng riêng biệt như kết quả cuối cùng bạn có thể yêu cầu họ:

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

Answer 3

Dưới đây là cách tiếp cận tương tự như @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 

Nó cho phép loại không nguyên cho a mảng. Nó cho phép các giá trị lớn trong a mảng. Nó trả về a các yếu tố theo thứ tự được sắp xếp. Nếu nó là mong muốn nó dễ dàng để khôi phục lại trật tự ban đầu bằng cách sử dụng return_index đối số của np.unique() chức năng.

Hiệu suất trở nên tồi tệ hơn khi số lượng thành phần duy nhất trong số a tăng lên. Nó chậm hơn 4 lần so với phiên bản @ unutbu trên dữ liệu từ câu hỏi của bạn.

Tôi đã thực hiện performance comparison với ba phương thức bổ sung. Các nhà lãnh đạo là: cho mảng số nguyên - hash-based implementation trong Cython; cho double mảng (đối với kích thước đầu vào 10000) - sort-based impl. cũng bằng Cython.