インデックスを持つnumpy配列を素早く変換します。インデックス上にキー配列されたnumpy配列のdictに変換します

Question

私はnumpy配列のセットを持っています。これらのうちの1つは "キー"のリストであり、そのキーをキーにした配列の辞書に配列を再配置したいと思います。現在のコードは

for key, val1, val2 in itertools.izip(keys, vals1, vals2): 
    dict1[key].append(val1) 
    dict2[key].append(val2) 

これはかなり遅いです。なぜなら、関係する配列は何百万ものエントリであり、これは何度も起こるからです。これをベクトル化された形式で書き直すことは可能ですか？可能なキーのセットは事前にわかっており、〜10個の別個のキーがあります。

編集： K異なるキーとリストが存在する場合のnの長さである、現在の答えはO（NK）（各キーについて一度反復）とO（N Nログ）（ソート最初）です。私はまだベクトル化されたO（n）ソリューションを探しています。これはうまくいけば可能です。結局のところ、最も簡単に可能な非ベクトル化されたもの（すなわち、私が既に持っているもの）はO（n）である。

Answer 1

これを行うベクター化された方法は、おそらくあなたのキーをソートする必要があります。基本的な考え方は、一致させるためにキーと値をソートすることです。ソートされたキー配列に新しいキーがあるたびにval配列を分割できます。

import numpy as np 

keys = np.random.randint(0, 10, size=20) 
vals1 = np.random.random(keys.shape) 
vals2 = np.random.random(keys.shape) 

order = keys.argsort() 
keys_sorted = keys[order] 

# Find uniq keys and key changes 
diff = np.ones(keys_sorted.shape, dtype=bool) 
diff[1:] = keys_sorted[1:] != keys_sorted[:-1] 
key_change = diff.nonzero()[0] 
uniq_keys = keys_sorted[key_change] 

vals1_split = np.split(vals1[order], key_change[1:]) 
dict1 = dict(zip(uniq_keys, vals1_split)) 

vals2_split = np.split(vals2[order], key_change[1:]) 
dict2 = dict(zip(uniq_keys, vals2_split)) 

この方法が原因argsortステップの複雑さはO（n *ログ（n）を）持っている：ベクトル化コードは次のようになります。実際には、nが非常に大きい場合を除き、argsortは非常に高速です。 argsortが著しく遅くなる前に、この方法でメモリ問題に遭遇する可能性が高いです。

Answer 2

レッツ・輸入numpyのといくつかのサンプルデータを作成しますのは、辞書を作成してみましょう、今

>>> import numpy as np 
>>> keys = np.array(('key1', 'key2', 'key3', 'key1', 'key2', 'key1')) 
>>> vals1 = np.arange(6) 
>>> vals2 = np.arange(10, 16) 

を：numpy背後

>>> d1 = {}; d2 = {} 
>>> for k in set(keys): 
... d1[k] = vals1[k==keys] 
... d2[k] = vals2[k==keys] 
... 
>>> d1 
{'key3': array([2]), 'key2': array([1, 4]), 'key1': array([0, 3, 5])} 
>>> d2 
{'key3': array([12]), 'key2': array([11, 14]), 'key1': array([10, 13, 15])} 

アイデアは、Cコードは、Pythonよりもはるかに高速であるとnumpyのは、提供することです多くの一般的な操作はCレベルでコード化されています。 "〜10個の別個のキー"しかないことに言及したように、これはPythonループが10回程度しか行われないことを意味します。残りの部分はCです。

Answer 3

defaultdictは、このような辞書を作成するためのものです。特に、新しいキーの新しい辞書項目を作成するステップを合理化します。

In [19]: keys = np.random.choice(np.arange(10),100) 
In [20]: vals=np.arange(100) 
In [21]: from collections import defaultdict 
In [22]: dd = defaultdict(list) 
In [23]: for k,v in zip(keys, vals): 
    ...:  dd[k].append(v) 
    ...:  
In [24]: dd 
Out[24]: 
defaultdict(list, 
      {0: [4, 39, 47, 84, 87], 
      1: [0, 25, 41, 46, 55, 58, 74, 77, 89, 92, 95], 
      2: [3, 9, 15, 24, 44, 54, 63, 66, 71, 80, 81], 
      3: [1, 13, 16, 37, 57, 76, 91, 93], 
      ... 
      8: [51, 52, 56, 60, 68, 82, 88, 97, 99], 
      9: [21, 29, 30, 34, 35, 59, 73, 86]}) 

しかし、あなたは簡単に前もって

dd = {k:[] for k in np.unique(keys)} 

の辞書のキーのエントリを作成することができますので、キーの小さな既知のセットで、あなたは、この専門的な辞書を必要としない。しかし、あなたが配列で始めているので、同様の値をソートして収集するための配列操作は、その価値があるかもしれません。

Answer 4

いくつかのタイミング：

import numpy as np 
import itertools 

def john1024(keys, v1, v2): 
    d1 = {}; d2 = {}; 
    for k in set(keys): 
    d1[k] = v1[k==keys] 
    d2[k] = v2[k==keys] 
    return d1,d2 

def birico(keys, v1, v2): 
    order = keys.argsort() 
    keys_sorted = keys[order] 
    diff = np.ones(keys_sorted.shape, dtype=bool) 
    diff[1:] = keys_sorted[1:] != keys_sorted[:-1] 
    key_change = diff.nonzero()[0] 
    uniq_keys = keys_sorted[key_change] 
    v1_split = np.split(v1[order], key_change[1:]) 
    d1 = dict(zip(uniq_keys, v1_split)) 
    v2_split = np.split(v2[order], key_change[1:]) 
    d2 = dict(zip(uniq_keys, v2_split)) 
    return d1,d2 

def knzhou(keys, v1, v2): 
    d1 = {k:[] for k in np.unique(keys)} 
    d2 = {k:[] for k in np.unique(keys)} 
    for key, val1, val2 in itertools.izip(keys, v1, v2): 
    d1[key].append(val1) 
    d2[key].append(val2) 
    return d1,d2 

私は10個のキー、2000万エントリを使用：だから

import timeit 

keys = np.random.randint(0, 10, size=20000000) #10 keys, 20M entries 
vals1 = np.random.random(keys.shape) 
vals2 = np.random.random(keys.shape) 

timeit.timeit("john1024(keys, vals1, vals2)", "from __main__ import john1024, keys, vals1, vals2", number=3) 
11.121668815612793 
timeit.timeit("birico(keys, vals1, vals2)", "from __main__ import birico, keys, vals1, vals2", number=3) 
8.107877969741821 
timeit.timeit("knzhou(keys, vals1, vals2)", "from __main__ import knzhou, keys, vals1, vals2", number=3) 
51.76217794418335 

が、私たちはソート技術よりも参照がnumpyのは、対応するインデックスを見つけせるよりも少し速いです各キーはもちろん、どちらもPythonでのループ処理よりもはるかに高速です。ベクトル化は素晴らしいです！

これは、Python 2.7.12上で、numpyの1.9.2