2

提出这个问题的最清楚的方法可能是分阶段发展它......

Q1：一般情况

考虑cumsum(x)[i]可以将（对于所有 i）定义为sum(x[1:i])。

还要考虑定义的泛化cumsum2D(A)[i,j]（对于所有 i,j）为sum(A[1:i,1:j])。这类似于将积分推广到二维的方式。

> # Example
> A
     [,1] [,2] [,3]
[1,]    0    1    0
[2,]    0    0    1
[3,]    0    1    0
> cumsum2D(A)
     [,1] [,2] [,3]
[1,]    0    1    1
[2,]    0    1    2
[3,]    0    2    3

让 Q1 成为问题：假设很大cumsum2D(A)，在 R中计算最快/最好的方法是什么？这个问题在这里A提出和回答。

Q2：稀疏案例

请注意，任何矩阵A都可以表示为D列出其非零元素的数据框（称为它）。D$val包含A[A!=0]whileD$i并D$j包含相应的下标。如果A是稀疏nrow(D)则小。

让cumsum2Dsparse(D)等于cumsum2D(A)。

# Example
> D
  i j val
1 1 2   1
2 2 3   1
3 3 2   1
> cumsum2Dsparse(D)
     [,1] [,2] [,3]
[1,]    0    1    1
[2,]    0    1    2
[3,]    0    2    3

cumsum2Dsparse(D)让 Q2 成为问题：假设D表示一个稀疏矩阵，最快/最好的计算方法是什么？

Q3：特殊稀疏情况

现在假设 的每一行和每一列A仅包含 1 个非零元素。（或等效地，假设D$i和分别是和D$j的排列。）1:nrow(A)1:ncol(A)

给定这个约束，让 Q3 是 Q2。

Qk

如前所述，Q1之前已在 SO 上得到回答。

Q2 是 Q1 的稀疏版本。

我将 Q3 包括在内，因为它可能比 Q2 有更快的解决方案，但如果您觉得它过于具体/不可重用，请忽略它。

编辑：供参考：

  • 为了与 Q3 的稀疏性保持一致，
    让 N = 列数 = 行数 = 非零元素的数量。
  • 对于基准测试，使用数据
    D <- data.frame(i=1:10000,j=((1:10000)*3333)%%10000,val=1)
4

0 回答 0