CODEWITHSUNDEEP
rmatrixsparse-matrix
The_Anomaly
The_Anomaly

Reputation: 2505

Replicate row indices of non-zero entries in a sparse matrix by values of those entries

Given a large sparse matrix of integers, I would like to have a list where each element of the list is a vector containing the indices of the non-zero elements in the corresponding row, replicated by the number times specified by the element. The matrix is large, and so I need a scalable solution.

Here is an example with working code that is very slow.

sparse_matrix <- matrix(c(1, 0, 0, 0, 2, 0, 1, 5, 0, 0, 0, 0), nrow = 2)
#       [,1] [,2] [,3] [,4] [,5] [,6]
#[1,]    1    0    2    1    0    0
#[2,]    0    0    0    5    0    0


# A very slow attempt that gives the right answer
lapply(seq_len(nrow(sparse_matrix)), function(r) {
  rep(seq_len(ncol(sparse_matrix)), sparse_matrix[r,])
}     )

#[[1]]
#[1] 1 3 3 4
#
#[[2]]
#[1] 4 4 4 4 4

EDIT: I realize I misspecified my question in the original post -- apologies. Please refer to the above example.

EDIT 2: Timing the two solutions for one use case:

sparse_matrix <- rsparsematrix (1E4,1E3, 0.01,rand.x = function(n) 1 + round(abs(rnorm(n))))
sparse_matrix <- as.matrix(sparse_matrix)

# 李哲源
ptm <- proc.time()
spM <- as(sparse_matrix, "dgRMatrix")
RowNumber <- rep(1:nrow(spM), diff(spM@p))
ColInd <- split(spM@j + 1, RowNumber)
nze <- split(spM@x, RowNumber)
output <- mapply(rep, ColInd, nze)  
print(proc.time() - ptm)
# 0.232 seconds

#akrun
ptm <- proc.time()
v1 <- c(col(sparse_matrix) * !! sparse_matrix)
v1 <-  setNames(v1, t(row(sparse_matrix)))
output <- rep(v1, sparse_matrix)
print(proc.time() - ptm)
# 1.8 seconds

Upvotes: 2

Views: 408

Answers (2)

Zheyuan Li
Zheyuan Li

Reputation: 73405

Are you familiar with compressed row storage for a sparse matrix? The index you want is just a key component in such storage. R package Matrix has its "dgRMatrix" class for this.

library(Matrix)
spM <- as(sparse_matrix, "dgRMatrix")
## which row do those non-zero entries lie?
RowNumber <- rep(1:nrow(spM), diff(spM@p))
## position index of those entries on each row, i.e., column index
ColInd <- split(spM@j + 1, RowNumber)
## none-zero-element on each row
nze <- split(spM@x, RowNumber)
## expand position index by matrix value
mapply(rep, ColInd, nze)

#$`1`
#[1] 1 3 3 4

#$`2`
#[1] 4 4 4 4 4

If the matrix is stored as a "dgCMatrix", can it be converted to "dgRMatrix"? In that case, the first line gives: no method or default for coercing 'dgCMatrix' to dgRMatrix'

This is no coercing method from "dgCMatrix" to "dgRMatrix". The sparse_matrix is as the dense matrix as in your post. So the coercing behind that as is from "matrix" to "dgRMatrix".

However, if you already have it as a "dgCMatrix", then you can first transpose it then do something similar on this "dgCMatrix". See below.

spM <- as(sparse_matrix, "dgCMatrix")
## transpose
spM <- t(spM)
## which column do those non-zero entries lie?
ColNumber <- rep(1:ncol(spM), diff(spM@p))
## position index of those entries on each column, i.e., row index
RowInd <- split(spM@i + 1, ColNumber)
## none-zero-element on each column
nze <- split(spM@x, ColNumber)
## expand position index by matrix value
mapply(rep, RowInd, nze)

#$`1`
#[1] 1 3 3 4

#$`2`
#[1] 4 4 4 4 4

Thanks to user20650 for his (big) improvement.

For the 1st case with "dgRMatrix",

spM <- as(sparse_matrix, "dgRMatrix")
RowNumber <- rep(1:nrow(spM), diff(spM@p))
split(rep(spM@j + 1, spM@x), rep(RowNumber, spM@x))

For the 2nd case with "dgCMatrix"

spM <- as(sparse_matrix, "dgCMatrix")
ColInd <- rep(1:ncol(spM), diff(spM@p))
split(rep(ColInd, spM@x), rep(spM@i, spM@x))

Upvotes: 4

akrun
akrun

Reputation: 887901

We can use which with arr.ind as TRUE to get the row and column index in a matrix

which(sparse_matrix !=0, arr.ind = TRUE)

For the second case

rep(col(sparse_matrix) * !! sparse_matrix, sparse_matrix)

gives a vector, but if we need an indentifier, then create a named vector

v1 <- c(col(sparse_matrix) * !! sparse_matrix)
v1 <-  setNames(v1, t(row(sparse_matrix)))
rep(v1, sparse_matrix)
#1 1 1 2 2 2 2 2 2 
#1 3 3 4 4 4 4 4 4

Upvotes: 2

Related Questions