为什么在大型稀疏矩阵上提取 R 行比将其分成较小的块然后提取时慢？

Question

我正在使用 class“dgCMatrix”的 19089 x 9432 稀疏矩阵（我们称之为 M），我必须提取每一行以对其执行一些计算。我用一个循环来做到这一点，所以在每次迭代中我都必须做类似 currentrow <- M[i,] 的事情来应用循环体。计算非常耗时，所以我想尽可能优化它，我意识到如果我先将矩阵分成小块（M[1:100,]、M[101:200,] 等），然后我在每个较小的矩阵上做一个循环（因此在每次迭代时调用 currentrow <- current_smallM[i,]），循环要快得多。

这是我运行重现的代码示例：

library(Matrix)

N = 10000
M = 5000

# Creation of the large matrix (of class dgCMatrix)
largeMatrix <- Matrix(rnorm(N*M,mean=0,sd=1), byrow = TRUE, nrow = N, sparse = TRUE)


# We take into account the time for the creation of the smaller matrix, and then calculate the time to allocate the 200 rows to a variable
start.time = Sys.time()
smallMatrix = largeMatrix[100:200,]
for (i in 1:100){
    test <- smallMatrix[i,]
}
end.time = Sys.time()
print(end.time - start.time) # 0.47 secs


# Same allocations but working on the large matrix
start.time = Sys.time()
for (i in 100:200){
    test <- largeMatrix[i,]
}
end.time = Sys.time()
print(end.time - start.time) # 18.44 secs

可以看出时差真的很大...所以我很纳闷:

为什么会这样？
有没有比将矩阵分成更小的部分更有效的存储数据的方法？

有趣的是，我用 matrix 对象（使用 largeMatrix <- matrix( rnorm(N*M,mean=0,sd=1), N, M)）测试了相同的代码，结果完全不同：分割矩阵为 0.06 秒，大矩阵为 0.04 秒，所以我真的很想知道稀疏表示有什么不同。

注意：我发现了一个非常相似的问题但它使用的是不同的语言，并且（我认为）该解决方案不适用于此处，因为它是由于隐式类型转换，而此处我只是提取一行。

感谢您的帮助！

Answer 1

dgCMatrix is a compressed sparse column format。它有一个 indptr 数组，其中有 X 个条目，其中 X 是矩阵中的列数，还有一个 index 数组，用于标识每个非零值的位置，它有 N 个条目，其中 N 是数组中非零值的数量。

这意味着每次你想按行切片它需要遍历整个index数组并寻找范围内的值你想切片。使用此 smallMatrix = largeMatrix[100:200,] 将数组切片为更小的数组，其中 index 数组要小得多，因此可以更快地遍历。

您真正的问题是您试图从数据结构中获取行，该数据结构使您对行的切片效率非常低，对列的切片效率非常高。

为什么在大型稀疏矩阵上提取 R 行比将其分成较小的块然后提取时慢？

Why is R row extraction slower on large sparse Matrix than when dividing it into smaller pieces and then extracting?

time

loops

r

extract

sparse-matrix