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++版本。