6

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

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で実装されないのですか？この制限を回避し、上記のコードを高速化する方法を知っている人はいますか？別のスパース行列タイプを使用する必要がありますか？

4

2 に答える 2

7

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にない要素が要求されるたびに、そのアイテムをデフォルトに設定して保存するため、問題が発生する可能性があることです。

于 2010-03-08T21:14:23.027 に答える
0

_get_single_elementは、デフォルトのdtypeである「object」が使用されている場合にのみ呼び出されると思います。次のようなdtypeを提供してみましたかcsr_matrix((data, (i,j)), dtype=int32)

于 2010-03-08T21:30:17.837 に答える