Come trovare indici di elementi non zero in grandi matrice sparsa?

Question

Ho due matrice mq (a, b) di dimensioni in ordine di 100000 x 100000. Devo prendere la differenza di queste due matrice (C = AB). La matrice risultante 'C' è una matrice sparsa. Voglio trovare gli indici di tutti gli elementi diversi da zero. Devo fare questa operazione molte volte (> 100).

Il modo più semplice è usare due per loop. Ma questo è intensivo computazionale. Puoi dirmi qualsiasi algoritmo o pacchetto/libreria preferibilmente in R/Python/C per farlo il più rapidamente possibile?

Answer 1

Dato che hai due matrici dense, il doppio loop è l'unica opzione che hai. Non hai bisogno affatto di una lezione di matrice sparsa poiché vuoi solo conoscere l'elenco degli indici (i,j) per cui a[i,j] != b[i,j].

In lingue come R e Python il doppio per loop funzionerà male. Probabilmente scrivo questo in codice nativo per un doppio per loop e aggiungi gli indici a un oggetto elenco. Ma senza dubbio i maghi del codice interpretato (cioè r, python ecc.) Conoscono modi efficienti per farlo senza ricorrere alla codifica nativa.

Answer 2

In r, se usi il Matrix pacchetto e sparseMatrix per la conversione dal Elenco delle coordinate Alla matrice sparsa, è possibile convertirsi nella colonna 3 tramite:

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

Questo ti darà le coordinate e i valori nella matrice sparsa.

A seconda delle posizioni delle voci diverse da zero in A e B, potresti trovare molto meglio lavorare con l'elenco delle coordinate rispetto alla rappresentazione di matrice sparsa (ci sono, a proposito, dozzine di rappresentazioni a matrice spara), mentre puoi prendere Vantaggio diretto delle operazioni vettoriali, piuttosto che fare affidamento sul pacchetto di matrice sparsa per eseguire in modo ottimale. Tendo ad alternarmi tra l'utilizzo del supporto COO o della matrice sparsa in diverse lingue, a seconda di come otterrò le prestazioni più veloci per l'algoritmo di interesse.

---

Aggiornamento 1: non ero consapevole che le tue due matrici, A e B, fossero dense. In quanto tale, la soluzione più semplice per trovare voci diverse da zero in C è semplicemente non sottrarre all'inizio nemmeno - basta confrontare le voci di A e B. Un confronto logico dovrebbe essere più veloce di una sottrazione. Innanzitutto, trova le voci di A e B dove A != B, Quindi sottrai solo quelle voci. Successivamente, devi semplicemente convertirsi dalla vettorializzazione degli indici nella rappresentazione (riga, col). Questo è simile a IND2SUB e sub2ind di Matlab - Dai un'occhiata Questo riferimento R. per i calcoli.

Answer 3

dai un'occhiata a numpy Ha tutto ciò che chiedi e altro ancora!

Vedere questo per supporto a matrice sparsa

Answer 4

Potresti usare c.nonzero() metodo:

>>> 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)

Non è necessario calcolare c matrice per scoprire indici di elementi diversi da zero in c = a - b; potresti fare (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]])

Answer 5

Non l'ho cronometrato, ma il codice più semplice è

all.indices<- which (C>0, arr.ind=T)

Answer 6

Questo codice richiede meno di 0,1s.

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

EDIT: per matrici sparse di qualsiasi dimensione (che si adatta alla memoria).

DATI

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)

CODICE

system.time(tw <- ta[tb][is.na(a)|is.na(b)|(a-b != 0),list(r=r,c=c)])