scipy.sparse行列のインデックス演算のベクトル化

StackOverflow https://stackoverflow.com/questions/2404437

質問

次のコードは、すべてがベクトル化されているように見えますが、実行が遅すぎます。 

from numpy import *
from scipy.sparse import *

n = 100000;
i = xrange(n); j = xrange(n);
data = ones(n);

A=csr_matrix((data,(i,j)));

x = A[i,j]

問題は、インデックス作成操作が Python 関数として実装されており、 A[i,j] 次のプロファイリング出力が生成されます。

         500033 function calls in 8.718 CPU seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   100000    7.933    0.000    8.156    0.000 csr.py:265(_get_single_element)
        1    0.271    0.271    8.705    8.705 csr.py:177(__getitem__)
(...)

つまり、Python関数は、 _get_single_element 100000 回呼び出されるので、非常に非効率的です。なぜこれが純粋な C で実装されないのでしょうか?誰かがこの制限を回避し、上記のコードを高速化する方法を知っていますか?別のスパース行列タイプを使用する必要がありますか?

役に立ちましたか？

解決

使用できます A.diagonal() 対角線をより速く取得できます (0.0009 秒対私のマシンでは 3.8 秒です)。ただし、任意のインデックスを作成したい場合は、インデックスのリストとしてスライスを使用するわけではないため、問題はさらに複雑になります。_get_single_element 関数は、渡されたイテレータ (i と j) を反復処理するだけなので、100000 回呼び出されます。スライスは A[30:60,10] またはそれに類似したものになります。

また、私は使用します csr_matrix(eye(n,n)) 簡単にするために、反復子を使用して作成したのと同じ行列を作成します。

アップデート：

わかりました。あなたの質問は本当に多くのランダムな要素に素早くアクセスできるようにすることに関するものですので、できる限りお答えします。

  • なぜこれが純粋な C で実装されないのでしょうか?

答えは簡単です。誰もそれを回避できませんでした。私が見た限りでは、Scipy の疎行列モジュール領域にはやるべきことがまだたくさんあります。C で実装される部分の 1 つは、異なる疎行列形式間の変換です。

  • 誰かがこの制限を回避し、上記のコードを高速化する方法を知っていますか?

実際に疎行列モジュールを試して、高速化を試みることができます。そうすることで、CSR 行列を使用したランダム アクセスで上記のコードを試したところ、時間を元の 3 分の 1 以下に短縮することができました。そのためには、_get_single_element に直接アクセスし、バインド チェックの削除を含めてコードを大幅に削減する必要がありました。

ただし、lil_matrix を使用したほうが高速ですが (行列の初期化は遅くなりますが)、実行しているインデックス付けの種類に対して lil 行列が設定されていないため、リスト内包表記を使用してアクセスする必要がありました。ちなみに、 csr_matrix にリスト内包表記を使用しても、まだ lil 行列メソッドがはるかに先になります。最終的に、lil 行列は圧縮されていないため、ランダム要素へのアクセスが高速になります。

lil_matrix を元の形式で使用すると、上にリストしたコードの約 5 分の 1 の時間で実行されます。いくつかのバウンド チェックを取り除き、lil_matrix の _get1() メソッドを直接呼び出すと、時間をさらに元の時間の約 7% 短縮できます。わかりやすく言うと、これは 3.4 ～ 3.8 秒から約 0.261 秒への高速化です。

最後に、lil 行列のデータに直接アクセスし、関数呼び出しの繰り返しを避ける独自の関数を作成してみました。この時間は約0.136秒でした。これは、別の潜在的な最適化である並べ替えられたデータを利用していませんでした (特に、同じ行にある多数の要素にアクセスしている場合)。

それより高速にしたい場合は、おそらく独自の C コードの疎行列実装を作成する必要があります。

  • 別のスパース行列タイプを使用する必要がありますか?

そうですね、大量の要素にアクセスすることが目的の場合は、lil マトリックスをお勧めしますが、それはすべて、何をする必要があるかによって異なります。たとえば行列を乗算する必要もありますか?行列間の変更は、少なくとも場合によっては (特定の状況では) 非常に高速になる可能性があるため、異なる演算を実行するために別の行列形式に変更することを除外しないでください。

行列に対して実際に代数演算を行う必要がない場合は、defaultdict または類似のものを使用する必要があるかもしれません。defaultdicts の危険性は、dict にない要素が要求されるたびに、その項目をデフォルトに設定して保存するため、問題が発生する可能性があることです。

他のヒント

私は「オブジェクト」はデフォルトDTYPEが使用されている場合_get_single_elementだけと呼ばれていると思います。あなたはDTYPEを提供しようとしたことがあり、そのようcsr_matrix((data, (i,j)), dtype=int32)など

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top