コード最適化 - Pythonでの関数呼び出しの数

Question

私のコードでnp.sum()関数呼び出しのオーバーヘッドを減らすためにこの問題をどのように変換できるか知りたいのですが。

私は、shape=(1000, 36)というinputの行列を持っています。各行はグラフ内のノードを表します。私は、各行に対して繰り返し処理を行い、可変数の他の行に要素的な追加を行う操作を実行しています。これらの「他の」行は、各行について、合算する必要がある行のリストを記録する辞書nodes_nbrsで定義されています。ここ

nodes_nbrs = {0: [0, 1], 
       1: [1, 0, 2], 
       2: [2, 1], 
       ...} 

は、ノード0ノード0と1の和に変換されることになる次のような例があります。ノード1は、ノード1,0、および2の合計に変換されます。残りのノードについても同様です。

私が現在実装している現在の（そして素朴な）方法はそのままです。私は最初、私がしたい最終形状のゼロ配列をインスタンス化し、次いでnodes_nbrs辞書の各キーと値のペアを反復：

output = np.zeros(shape=input.shape) 
for k, v in nodes_nbrs.items(): 
    output[k] = np.sum(input[v], axis=0) 

このコードは、小テスト（shape=(1000, 36)）内のすべてのクールで結構ですが、より大きいテスト（shape=(~1E(5-6), 36)）では、完了までに2〜3秒かかります。私はこの作業を何千回もやらなければならなくなるので、これを行うためのより最適化された方法があるかどうかを確認しようとしています。

回線プロファイリングを実行した後、ここで重要なキラーはnp.sum関数を繰り返し呼び出していることに気付きました。これは合計時間の約50％を占めます。このオーバーヘッドを排除する方法はありますか？それとも、これを最適化できる別の方法がありますか？それとは別に

---

、ここで私が行っているもののリスト、および（非常に簡単に）その結果である：

• cythonバージョンは：、オーバーヘッドチェックforループ型を排除し、30％削減時間がかかる。 cythonバージョンでは、np.sumが、壁時計の合計時間の約80％を占め、50％ではなくなります。
• をnpsumとして事前に宣言してから、forループ内でnpsumを呼び出します。オリジナルとの違いはありません。
• np.sumをnp.add.reduceに置き換え、それを変数npsumに割り当ててから、forループ内にnpsumを呼び出します。壁時計の時間が約10％短縮されますが、次にautogradと互換性がありません（以下、疎な行列の箇条書きの説明を参照）。
• numba JIT-ing：デコレータの追加以上の試みはしませんでした。改善はしなかったが、もっと努力しなかった。
• nodes_nbrs辞書を高密度numpyバイナリアレイ（1と0）に変換してから、np.dotオペレーションを1回実行します。理論的には良いですが、メモリ使用量が二次的なshape=(10^n, 10^n)の正方行列を必要とするため、実際には悪いです。

私がしようとしたが、そうすることを躊躇していなかったもの：

• scipyスパース行列を：私はscipyスパース行列に対してdot操作の自動微分をサポートしていないautogradを、使用しています。興味がある人のため

---

、これは本質的に、グラフ構造データ上の畳み込み演算です。大学院のためにこれを開発することは楽しいですが、知識の最先端にいくらか不満を抱いています。

Answer 1

scipy.sparseがオプションでない場合は、データにマッサージして、ベクトル化された関数を使用してコンパイル済みのレイヤーのすべてを処理できるようにすることができます。ネイバー辞書を2次元配列に変更して欠損値に適切なフラグを付ける場合は、np.takeを使用して必要なデータを抽出し、次にsum()コールを1つ実行することができます。ここで

は、私が考えているものの例です：

import numpy as np 

def make_data(N=100): 
    X = np.random.randint(1, 20, (N, 36)) 
    connections = np.random.randint(2, 5, N) 
    nbrs = {i: list(np.random.choice(N, c)) 
      for i, c in enumerate(connections)} 
    return X, nbrs 

def original_solution(X, nbrs): 
    output = np.zeros(shape=X.shape) 
    for k, v in nbrs.items(): 
     output[k] = np.sum(X[v], axis=0) 
    return output 

def vectorized_solution(X, nbrs): 
    # Make neighbors all the same length, filling with -1 
    new_nbrs = np.full((X.shape[0], max(map(len, nbrs.values()))), -1, dtype=int) 
    for i, v in nbrs.items(): 
     new_nbrs[i, :len(v)] = v 

    # add a row of zeros to X 
    new_X = np.vstack([X, 0 * X[0]]) 

    # compute the sums 
    return new_X.take(new_nbrs, 0).sum(1) 

今、私たちはその結果が一致を確認することができます

>>> X, nbrs = make_data(100) 
>>> np.allclose(original_solution(X, nbrs), 
       vectorized_solution(X, nbrs)) 
True 

を我々はスピードアップ見て物事を時間を計ることができます。

を

X, nbrs = make_data(1000) 
%timeit original_solution(X, nbrs) 
%timeit vectorized_solution(X, nbrs) 
# 100 loops, best of 3: 13.7 ms per loop 
# 100 loops, best of 3: 1.89 ms per loop 

さらに大きなサイズになる：

X, nbrs = make_data(100000) 
%timeit original_solution(X, nbrs) 
%timeit vectorized_solution(X, nbrs) 
1 loop, best of 3: 1.42 s per loop 
1 loop, best of 3: 249 ms per loop 

これは約5-10倍速く、目的に合っているかもしれません（ただし、これはあなたのnbrs辞書の正確な特性に大きく依存します）。

---

編集：ちょうど楽しみのため、私はカップルの他のアプローチ、numpy.add.reduceatを使用して1、scipy.sparseを使用してpandas.groupby、および1を使用して1を試してみました。私が最初に提案したベクタライズされたアプローチがおそらく最善の策であるようです。ここでは、それらは参照用です：

from itertools import chain 

def reduceat_solution(X, nbrs): 
    ind, j = np.transpose([[i, len(v)] for i, v in nbrs.items()]) 
    i = list(chain(*(nbrs[i] for i in ind))) 
    j = np.concatenate([[0], np.cumsum(j)[:-1]]) 
    return np.add.reduceat(X[i], j)[ind] 

np.allclose(original_solution(X, nbrs), 
      reduceat_solution(X, nbrs)) 
# True 

-

import pandas as pd 

def groupby_solution(X, nbrs): 
    i, j = np.transpose([[k, vi] for k, v in nbrs.items() for vi in v]) 
    return pd.groupby(pd.DataFrame(X[j]), i).sum().values 

np.allclose(original_solution(X, nbrs), 
      groupby_solution(X, nbrs)) 
# True 

-

from scipy.sparse import csr_matrix 
from itertools import chain 

def sparse_solution(X, nbrs): 
    items = (([i]*len(col), col, [1]*len(col)) for i, col in nbrs.items()) 
    rows, cols, data = (np.array(list(chain(*a))) for a in zip(*items)) 
    M = csr_matrix((data, (rows, cols))) 
    return M.dot(X) 

np.allclose(original_solution(X, nbrs), 
      sparse_solution(X, nbrs)) 
# True 

そして、すべてのタイミング一緒に：最近のまばらな質問への研究に基づいて

X, nbrs = make_data(100000) 
%timeit original_solution(X, nbrs) 
%timeit vectorized_solution(X, nbrs) 
%timeit reduceat_solution(X, nbrs) 
%timeit groupby_solution(X, nbrs) 
%timeit sparse_solution(X, nbrs) 
# 1 loop, best of 3: 1.46 s per loop 
# 1 loop, best of 3: 268 ms per loop 
# 1 loop, best of 3: 416 ms per loop 
# 1 loop, best of 3: 657 ms per loop 
# 1 loop, best of 3: 282 ms per loop 

Answer 2

、例えばExtremely slow sum row operation in Sparse LIL matrix in Python

ここでは、あなたの問題の種類を疎行列で解決する方法を説明します。このメソッドは、密なものにも同様に適用できます。考え方は、行（または列）が1のマトリックス製品として実装された疎なsumです。スパース行列のインデックス作成は遅いですが、行列積は良いCコードです。

この場合、合計したい行の1を持つ乗算行列を作成します。辞書の各エントリごとに異なる1のセットです。

サンプルマトリックス：

In [302]: A=np.arange(8*3).reshape(8,3)  
In [303]: M=sparse.csr_matrix(A) 

選択辞書：

In [304]: dict={0:[0,1],1:[1,0,2],2:[2,1],3:[3,4,7]} 

この辞書から疎行列を構築します。このような行列を構築する最も効率的な方法ではないかもしれませんが、そのアイデアを実証するだけで十分です。

In [305]: r,c,d=[],[],[] 
In [306]: for i,col in dict.items(): 
    c.extend(col) 
    r.extend([i]*len(col)) 
    d.extend([1]*len(col)) 

In [307]: r,c,d 
Out[307]: 
([0, 0, 1, 1, 1, 2, 2, 3, 3, 3], 
[0, 1, 1, 0, 2, 2, 1, 3, 4, 7], 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) 

In [308]: idx=sparse.csr_matrix((d,(r,c)),shape=(len(dict),M.shape[0])) 

の和を実行し、（密な配列として）結果を見て：

In [310]: (idx*M).A 
Out[310]: 
array([[ 3, 5, 7], 
     [ 9, 12, 15], 
     [ 9, 11, 13], 
     [42, 45, 48]], dtype=int32) 

ここでは比較のためのオリジナルです。

In [312]: M.A 
Out[312]: 
array([[ 0, 1, 2], 
     [ 3, 4, 5], 
     [ 6, 7, 8], 
     [ 9, 10, 11], 
     [12, 13, 14], 
     [15, 16, 17], 
     [18, 19, 20], 
     [21, 22, 23]], dtype=int32)