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

Question

我正在使用“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 是一种压缩稀疏列格式。它有一个indptr包含 X 个条目的数组，其中 X 是矩阵中的列数，以及一个index标识每个非零值位置的数组，该数组有 N 个条目，其中 N 是数组中非零值的数量。

这意味着每次您想要按行对其进行切片时，它都需要遍历整个index数组并查找在您想要切片的范围内的值。使用此方法smallMatrix = largeMatrix[100:200,]将数组分割成一个更小的数组，其中index数组要小得多，因此可以更快地遍历。

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