Pythonのグループ、および配列bをまとめ - 性能

Question

2つの順序付けられていない同じ長さの配列および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] 

あるいは

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

、ランダムAおよびBI：Bの要素の

加算は（例は、確率密度関数を要約するために使用されます） n Python：

2つのアプローチがありますが、これはパフォーマンスの低い境界からは離れています。 アプローチ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 

更新：Approut 4 by Unutbu。時間：0.184849023819 [SO FAR WINNERが、整数としてのみ]

def unique_Unutbu(a,b): 

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

たぶん誰かが私よりも、この問題に対するよりスマートな解決策を見つけた:)

Answer 1

aがint型< 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を使用した場合の1つの潜在的な問題は、長さがaの最大値に等しい配列を戻すことです。 aに2 ** 31-1に近い値を持つ要素が1つでも含まれている場合、はサイズ8*(2**31-1)バイト（または16GiB）の配列を割り当てる必要があります。

したがってnp.bincountは、長さは大きいが大きな値は持たない配列aの最速の解決策となる可能性があります。小さな長さ（大きい値または小さい値）を持つ配列aの場合は、collections.defaultdictを使用するほうがおそらく高速です。

編集：整数値のみの制限と大きな値の問題については、J.F. Sebastian's solutionを参照してください。

Answer 2

どのようにこのアプローチについて：

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() 

Answer 3

はここ@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個の要素を返します。それが望ましい場合はreturn_index引数をnp.unique()として元の順序に戻すのは簡単です。

aの固有の要素の数が増えるとパフォーマンスが悪くなります。あなたの質問のデータでは、@ unutbuのバージョンより4倍遅いです。

さらに、私はperformance comparisonに3つの方法を追加しました。指導者は次のとおりです：整数配列の場合 - hash-based implementation、Cython; double配列（入力サイズ10000の場合） - sort-based impl.もCythonにあります。