R: 坏循环代码，提高速度？

Question

我创建了一些基本代码来实现我的需要，但它是糟糕的代码，速度非常慢。目的是从 SE 列中取出一行，如果它与 SC 列匹配，则为它所属的每 5 分钟括号将计数器加 1。

我写的代码是

for (i in 1:(nrow(SC)))
  for(j in 1:(nrow(SE)))
    for (k in 0:5)
      if ( (SE[j,3]==SC[i,1]) & 
        (as.POSIXlt(SE[j,1])>as.POSIXlt(SC[i,4]) +k*5*60)&
        (as.POSIXlt(SE[j,1])<=as.POSIXlt(SC[i,4])+ (k+1)*5*60 ) &
        (SE[j,2]==1) )
      { SC[i,6+k]=SC[i,6+k]+1 }

也就是说检查 SC 的每个单元格以查看条件是否相同（房间号相同，时间范围内的时间等）。

这是非常低效的，因为三重循环在 R 中需要永远。正在寻找替换循环的方法，也许是向量或应用？

> SE
            UTC         pin  Room
 1  2014-12-22 10:14:34   1 Alpha
 4  2014-12-22 10:15:27   1 Alpha
 5  2014-12-22 10:16:00   1 Alpha
 8  2014-12-22 10:18:10   1 Alpha
 12 2014-12-22 10:19:06   1 Alpha
 13 2014-12-22 10:20:00   1 Alpha
 14 2014-12-22 10:08:34   1  Beta
 17 2014-12-22 10:15:29   1  Beta
 18 2014-12-22 10:16:00   1  Beta
 19 2014-12-22 10:17:00   1  Beta
 22 2014-12-22 10:18:10   1  Beta
 24 2014-12-22 10:19:00   1  Beta
 26 2014-12-22 10:19:11   1  Beta
 28 2014-12-22 10:09:34   1 Gamma
 29 2014-12-22 10:39:11   1 Gamma


 > SC
    Room Capacity Video.Conference                  ST                  ET 
 1 Alpha       16                1 2014-12-22 10:00:00 2014-12-22 10:30:00
 2 Alpha       16                1 2014-12-22 10:30:00 2014-12-22 11:00:00
 3  Beta       16                1 2014-12-22 10:00:00 2014-12-22 10:30:00
 4  Beta       16                1 2014-12-22 10:30:00 2014-12-22 11:00:00
 5 Gamma       10                0 2014-12-22 10:00:00 2014-12-22 10:30:00
 6 Gamma       10                0 2014-12-22 10:30:00 2014-12-22 11:00:00


>Desired #This is the intended output
 X  Room Capacity Vid                  ST              ET        X0.to.5.min  X5.to.10.min  X10.to.15.min  X15.to.20.min  X20.to.25.min  X25.to.30.min 
 1  Alpha       16   1 2014-12-22 10:00:00 2014-12-22 10:30:00           0            0             1             5             0            0           
 2  Alpha       16   1 2014-12-22 10:30:00 2014-12-22 11:00:00           0            0             0             0             0            0           
 3   Beta       16   1 2014-12-22 10:00:00 2014-12-22 10:30:00           0            1             0             6             0            0           
 4   Beta       16   1 2014-12-22 10:30:00 2014-12-22 11:00:00           0            0             0             0             0            0           
 5  Gamma       10   0 2014-12-22 10:00:00 2014-12-22 10:30:00           0            1             0             0             0            0          
 6  Gamma       10   0 2014-12-22 10:30:00 2014-12-22 11:00:00           0            1             0             0             0            0

Answer 1

您可以减少 for 循环中的函数调用次数（尤其是 as.POSIXlt 调用），这应该会有所帮助。此外，&& 运算符可能运行得更快，因为在第一个条件为 false 之后不会对后续比较进行评估。

posix.SE  <- as.POSIXlt(SE[,1])
posix.SC  <- as.POSIXlt(SC[,4])

for (i in 1:(nrow(SC)))
for(j in 1:(nrow(SE)))
for (k in (0:5))
if ( (SE[j,3]==SC[i,1]) &&
    (posix.SE[j]>posix.SC[i] + k*300)&&
    (posix.SE[j]<=posix.SC[i]+ (k+1)*300 ) &&
    (SE[j,2]==1) ) {

    SC[i,6+k]=SC[i,6+k]+1 

}

您还可以通过以下方式减少 if 子句中第一个条件的计算次数：

for(val in unique(SE[,3]))
    for(i in which(SC[,1] == val))
    for(j in which(SE[,3] == val))
    for (k in (0:5))
    if ((posix.SE[j]>posix.SC[i] + k*300)&&
        (posix.SE[j]<=posix.SC[i]+ (k+1)*300 ) &&
        (SE[j,2]==1) ) {

        SC[i,6+k]=SC[i,6+k]+1 

    }

使用 'outer' 可能比

更有效

for(val in unique(SC[,1])){
    # index the relevent rows for each value in SC[,1]
    index.SC  <-  which(SC[,1] == val)
    index.SE  <-  which(SE[,3] == val & SE[,2]==1)
    MX <- outer(posix.SE[index.SE], posix.SC[index.SC],`-`)
    for (k in (0:5))
        SC[indxe.SC,6+k]  <-  apply((MX > k*300)& (MX <= (k+1)*300 ),2,sum)
}

[如果 SC[1] 是您要在 for 循环中使用 'levels(SC[1]) 而不是 unique(SC[1]) 的一个因素...]

Answer 2

你的算法目前是运行 O(n^2) 如果你对 SE 和 SC 列的属性一无所知，这是你能做的最好的。如果任一列中的数据具有某些特定属性，那么您可以进行一些优化。例如

SE 中的条目是否唯一？如果是这样，那么您可以删除匹配项 SC 所以他们不会再次检查。

SE 或 SC 中的条目是否已排序？如果是这样，那么你可以使用比较短路 SC 中的搜索（例如：如果 SC 被排序按递增顺序，然后在检查匹配项时是否是我所在的行比较大于我正在寻找的然后我保释因为不会再有匹配项了）

Answer 3

进一步采纳@jthorpe 的建议，在可能的情况下进行矢量化并提取通用计算

step <- 5 * 60
se <- as.POSIXlt(SE[,1]) / step
sc <- as.POSIXlt(SC[,4]) / step
k <- 0:5

更新 data.frame 成本很高，因此创建一个矩阵来包含答案

ans <- as.matrix(SC[, 6 + 0:5])

重新安排循环，以便可以向量化第一个和最后一个测试标准的计算

for (j in seq_along(se)[SE[,2] == 1])
    for (i in seq_along(sc)[SE[j, 3] == SC[,1]])

并对最内层循环进行矢量化

    {
        d <- se[j] - sc[i]
        idx <- k[(d > k) & (d <= (k + 1))] + 1
        ans[i, idx] <- ans[i, idx] + 1
    }

正如@hhafez 指出的那样，这仍然是一个二次时间算法，使用您的数据的属性可能还有很大的改进空间。

R: 坏循环代码，提高速度？

R: Bad loop code, improve the speed?

performance

for-loop

r