r - R 中最大子数组和的最快实现

Question

亲爱的社区成员，
我在我的工具中经常使用最大子阵列总和函数(Kadane 算法)。这是一个瓶颈。
你能告诉我是否可以使用一些内部 R 技巧来提高性能吗？它在 C++ 中运行得更快 - 但我真的不想将 C++ 代码添加到我的基于 R 的工具中......

maxSubArraySum <- function(x){
  bestSoFar = 0
  bestNow = 0
  bestStartIndexSoFar = -1
  bestStopIndexSoFar = -1
  bestStartIndexNow = -1
  for (i in 1:length(x)) {
    value = bestNow + x[i]
    if (value > 0) {
      if (bestNow == 0) {
        bestStartIndexNow = i
      }
      bestNow = value
    }
    else
      bestNow = 0
    
    if (bestNow > bestSoFar) {
      bestSoFar = bestNow
      bestStopIndexSoFar = i
      bestStartIndexSoFar = bestStartIndexNow
    }
  }
  return(c(bestSoFar, bestStartIndexSoFar, bestStopIndexSoFar))
}

Answer 1

如果您不想使用 Rcpp，这里有一个更快的纯 R 向量化实现:

fast_maxSubArraySum <- function(x) {
    csum = cumsum(x)
    cmin = cummin(csum)
    gaps = csum - cmin
    endPos = which.max(gaps)
    integralMax = gaps[endPos]
    startPos = which.min(cmin[1:endPos])+1
    integralMin = gaps[startPos-1]
    gap = integralMax - integralMin
    if(cmin[startPos] > 0) {
        startPos = 1
        gap = csum[endPos]
    }
    return(c(gap, startPos, endPos))
}

此版本比 maxSubArraySum 快 10 倍以上在我的机器上。
请注意，同样的策略也可用于编写更快的 C++ 版本。