8

O(N) NxN のコレクションがscipy.sparse.csr_matrixあり、各スパース行列には N 要素セットのオーダーがあります。これらすべての行列を一緒に追加して、通常の NxN numpy 配列を取得したいと考えています。(N は 1000 のオーダーです)。行列内のゼロ以外の要素の配置は、結果として得られる合計が確かにまばらではないようになっています (事実上ゼロ要素は実際には残っていません)。

現時点では、私はちょうどやっています

reduce(lambda x,y: x+y,[m.toarray() for m in my_sparse_matrices])

これは機能しますが、少し遅いです。もちろん、そこで行われているゼロの無意味な処理の膨大な量は、絶対に恐ろしいものです。

より良い方法はありますか？docsには明らかなことは何もありません。

更新： user545424の提案に従って、疎行列を合計し、疎行列を密行列に合計する代替スキームを試しました。以下のコードは、同等の時間で実行するためのすべてのアプローチを示しています (クアッドコア i7 上の amd64 Debian/Squeeze 上の Python 2.6.6)。

import numpy as np
import numpy.random
import scipy
import scipy.sparse
import time

N=768
S=768
D=3

def mkrandomsparse():
    m=np.zeros((S,S),dtype=np.float32)
    r=np.random.random_integers(0,S-1,D*S)
    c=np.random.random_integers(0,S-1,D*S)
    for e in zip(r,c):
        m[e[0],e[1]]=1.0
    return scipy.sparse.csr_matrix(m)

M=[mkrandomsparse() for i in xrange(N)]

def plus_dense():
    return reduce(lambda x,y: x+y,[m.toarray() for m in M])

def plus_sparse():
    return reduce(lambda x,y: x+y,M).toarray()

def sum_dense():
    return sum([m.toarray() for m in M])

def sum_sparse():
    return sum(M[1:],M[0]).toarray()

def sum_combo():  # Sum the sparse matrices 'onto' a dense matrix?
    return sum(M,np.zeros((S,S),dtype=np.float32))

def benchmark(fn):
    t0=time.time()
    fn()
    t1=time.time()
    print "{0:16}:  {1:.3f}s".format(fn.__name__,t1-t0)

for i in xrange(4):
    benchmark(plus_dense)
    benchmark(plus_sparse)
    benchmark(sum_dense)
    benchmark(sum_sparse)
    benchmark(sum_combo)
    print

そしてログアウト

plus_dense      :  1.368s
plus_sparse     :  1.405s
sum_dense       :  1.368s
sum_sparse      :  1.406s
sum_combo       :  1.039s

N、S、Dパラメーターをいじることで、どちらかのアプローチを2倍程度先に進めることができますが...しかし、数値を考慮することで期待する桁違いの改善のようなものはありませんゼロの追加はスキップできるはずです。

4

4 に答える 4

4

行列が非常にまばらな場合、最大 10 倍高速化する方法を見つけたと思います。

In [1]: from scipy.sparse import csr_matrix

In [2]: def sum_sparse(m):
   ...:     x = np.zeros(m[0].shape)
   ...:     for a in m:
   ...:         ri = np.repeat(np.arange(a.shape[0]),np.diff(a.indptr))
   ...:         x[ri,a.indices] += a.data
   ...:     return x
   ...: 

In [6]: m = [np.zeros((100,100)) for i in range(1000)]

In [7]: for x in m:
   ...:     x.ravel()[np.random.randint(0,x.size,10)] = 1.0
   ...:     

        m = [csr_matrix(x) for x in m]

In [17]: (sum(m[1:],m[0]).todense() == sum_sparse(m)).all()
Out[17]: True

In [18]: %timeit sum(m[1:],m[0]).todense()
10 loops, best of 3: 145 ms per loop

In [19]: %timeit sum_sparse(m)
100 loops, best of 3: 18.5 ms per loop
于 2012-06-29T17:37:20.247 に答える
3

@ user545424 は、最速の解決策と思われるものを既に投稿しています。より読みやすく、〜同じ速度である同じ精神の何か... nonzero()には、あらゆる種類の便利なアプリケーションがあります。

def sum_sparse(m):
        x = np.zeros(m[0].shape,m[0].dtype)
        for a in m:
            # old lines
            #ri = np.repeat(np.arange(a.shape[0]),np.diff(a.indptr))
            #x[ri,a.indices] += a.data
            # new line
            x[a.nonzero()] += a.data
        return x
于 2012-07-02T22:47:43.470 に答える
1

これは完全な回答ではありません (私もより詳細な回答を希望します) が、中間結果を作成しないことで、簡単に 2 倍以上の改善を得ることができます。

def sum_dense():
    return sum([m.toarray() for m in M])

def sum_dense2():
    return sum((m.toarray() for m in M))

私のマシン (YMMV) では、これが最速の計算になります。()総和を aではなくa に配置することで、総和の[]前にリスト全体ではなくジェネレータを構築します。

于 2012-06-29T14:31:05.050 に答える
1

密行列に変換する前にそれらを足し合わせることができませんか?

>>> sum(my_sparse_matrices[1:],my_sparse_matrices[0]).todense()
于 2012-06-29T00:22:09.337 に答える