Python的組由陣列的，並總結數組b - 性能

鑑於相同的長度a和b兩個無序陣列：Python的組由陣列的，並總結數組b - 性能

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

我想由元素組中的一個：

aResult = [7,3,5]

求和超過b中的元素（實施例用來總結的概率密度函數）：

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

可替換地，隨機地和雙向蟒蛇：

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

我有兩種方法，肯定遠離性能較低的邊界。方法1（至少好和短）：時間：0.769315958023

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

方法2（numpy.groupby，可怕的慢）時間：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]))

更新：Approach3，由巴勃羅。時間：1.0265750885

def approach_Pablo(a,b):  

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

更新：方法4，由Unutbu。時間：0.184849023819 [WINNER至今，但作爲唯一的整數]

def unique_Unutbu(a,b): 

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

也許有人發現一個更聰明的辦法解決這個問題比我:)

來源

2011-09-24 Helga

什麼是無序數組？ –

我的意思是你不能假定列表a已排序。 – Helga

如果a由整數< 2 ** 31-1（即，如果a具有可適應值DTYPE int32），那麼你可以使用np.bincount配重塊：

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)回報[3 5 7]，因此結果會出現在不同的順序：

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

使用np.bincount時出現的一個潛在問題是它返回的數組長度等於a中的最大值。如果a甚至包含一個值接近2 ** 31-1的元素，則bincount將不得不分配大小爲8*(2**31-1)字節（或16GiB）的數組。

因此，np.bincount可能是最快的解決方案，其中數組a具有很大的長度，但不是很大的值。對於長度較小（大或小的值）的數組a，使用collections.defaultdict可能會更快。

編輯：請參閱J.F. Sebastian's solution以解決整數值限制和大值問題。

來源

2011-09-24 12:29:56 unutbu

[測量]（https://gist.github.com/da57326584a3811652aa#file_measurements.org）顯示'np.bincount（）即使對[基於Cython的解決方案]也表現良好（https://gist.github.com/ da57326584a3811652aa＃file_pdf.pyx）。 – jfs

如何對這種做法：

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

您只需遍歷每個元素一次，並使用字典進行快速查找。如果你真的想兩個獨立的數組作爲最終結果，你可以問他們：

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

來源

2011-09-24 10:36:41 Pablo

你可以使用defaultdict（int），它更乾淨。 –

謝謝！我不知道。更新回答:) – Pablo

我喜歡這個方法，很漂亮。不幸的是，它似乎比'方法1'更慢，尤其是對於長陣列... – Helga

這裏的類似的方法來@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

它允許非整數型爲a陣列。它允許在a數組中有較大的值。它按排序順序返回a元素。如果希望使用np.unique()函數的return_index參數恢復原始順序，很容易。

隨着a中獨特元素數量的增加，性能會變差。它比你的問題數據的@unutbu版本慢4倍。

我用另外三種方法制作了performance comparison。領導者是：用於整數陣列--Cython中的hash-based implementation;對於double數組（輸入大小爲10000） - sort-based impl.也在Cython中。

來源

2011-09-24 13:24:28 jfs

Python的組由陣列的，並總結數組b - 性能

回答

相關問題