6

100000 X 100000 のオーダーのサイズの 2 つの正方行列 (a、b) があります。これら 2 つの行列 (c = ab) の差を取る必要があります。結果行列 'c' はスパース行列です。すべての非ゼロ要素のインデックスを見つけたいです。この操作を何度も行う必要があります (>100)。

最も簡単な方法は、2 つの for ループを使用することです。しかし、それは計算集約的です。これをできるだけ早く行うために、できればR/python/cのアルゴリズムまたはパッケージ/ライブラリを教えてください。

4

6 に答える 6

4

2つの密な行列があるため、doubleforループが唯一のオプションです。(i,j)のインデックスのリストのみを知りたいので、スパース行列クラスはまったく必要ありませんa[i,j] != b[i,j]。

RやPythonなどの言語では、doubleforループのパフォーマンスが低下します。私はおそらくこれをdoubleforループのネイティブコードで記述し、リストオブジェクトにインデックスを追加します。しかし、間違いなく、インタプリタされたコードのウィザード（つまり、R、Pythonなど）は、ネイティブコーディングに頼らずにそれを行う効率的な方法を知っています。

于 2011-09-09T13:21:22.190 に答える
3

R では、Matrixパッケージを使用sparseMatrixし、座標リストから疎行列への変換のために、次の方法で 3 列に戻すことができます。

TmpX <- as(M, "dgTMatrix")
X3col <- matrix(c(TmpX@i, TmpX@j, TmpX@val), ncol = 3)

これにより、疎行列の座標と値が得られます。

A と B のゼロ以外のエントリの位置によっては、疎行列表現よりも座標リストを使用する方がはるかに優れていることがわかる場合があります (ちなみに、数十の疎行列表現があります)。最適に実行するために疎行列パッケージに依存するのではなく、ベクトル化された操作の直接的な利点。関心のあるアルゴリズムで最速のパフォーマンスを得る方法に応じて、さまざまな言語で COO または疎行列サポートを交互に使用する傾向があります。

更新 1: A と B の 2 つの行列が密であることを知りませんでした。そのため、C でゼロ以外のエントリを見つけるための最も簡単な解決策は、最初は減算さえしないことです。単に A と B のエントリを比較するだけです。論理比較は、減算よりも高速である必要があります。最初に、 A と B のエントリを見つけて から、A != Bそれらのエントリだけを減算します。次に、A と B のインデックスのベクトル化を (row, col) 表現に変換するだけです。これは、Matlab の ind2sub および sub2ind に似ています。計算については、この R リファレンスを参照してください。

于 2011-09-09T12:54:00.203 に答える
1

numpyを見てください。あなたが求めるものすべてが揃っています。

スパース行列のサポートについては、これを参照してください

于 2011-09-09T12:15:50.787 に答える
1

このコードにかかる時間は 0.1 秒未満です。

m <- matrix(rpois(1000000,0.01),ncol=1000)
m0 <- lapply(seq(NCOL(m)),function(x) which(m[,x] != 0))

EDIT：任意のサイズのスパース行列（メモリに収まる）の場合。

データ

library(data.table)

N <- 1e+5
n <- 1e+6

ta <- data.table(r=sample(seq(N), n,replace=TRUE),
                 c=sample(seq(N), n,replace=TRUE),
                 a=sample(1:20,n,replace=TRUE))
tb <- data.table(r=sample(seq(N), n,replace=TRUE),
                 c=sample(seq(N), n,replace=TRUE),
                 b=sample(1:20,n,replace=TRUE))
setkey(ta,r,c)
setkey(tb,r,c)

コード

system.time(tw <- ta[tb][is.na(a)|is.na(b)|(a-b != 0),list(r=r,c=c)])
于 2011-09-09T13:27:09.630 に答える
1

メソッドを使用できますc.nonzero()：

>>> from scipy.sparse import lil_eye
>>> c = lil_eye((4, 10)) # as an example
>>> c
<4x10 sparse matrix of type '<type 'numpy.float64'>'
        with 4 stored elements in LInked List format>
>>> c.nonzero()
(array([0, 1, 2, 3], dtype=int32), array([0, 1, 2, 3], dtype=int32))
>>> import numpy as np
>>> np.ascontiguousarray(c)
array([  (0, 0) 1.0
  (1, 1)        1.0
  (2, 2)        1.0
  (3, 3)        1.0], dtype=object)

cの非ゼロ要素のインデックスを見つけるために行列を計算する必要はありませんc = a - b。あなたができる(a != b).nonzero()：

>>> a = np.random.random_integers(2, size=(4,4))
>>> b = np.random.random_integers(2, size=(4,4))
>>> (a != b).nonzero()
(array([0, 0, 1, 1, 1, 2, 3]), array([1, 2, 1, 2, 3, 2, 0]))
>>> a - b
array([[ 0,  1,  1,  0],
       [ 0,  1, -1, -1],
       [ 0,  0,  1,  0],
       [-1,  0,  0,  0]])
于 2011-09-09T12:25:57.310 に答える
1

私はそれを計っていませんが、最も単純なコードは

all.indices<- which (C>0, arr.ind=T)
于 2011-09-09T15:20:43.507 に答える