gsub速度与模式长度

Question

我最近一直在gsub广泛使用,我注意到短模式比长模式运行得更快,这并不奇怪.这是一个完全可重现的代码:

library(microbenchmark)
set.seed(12345)
n = 0
rpt = seq(20, 1461, 20)
msecFF = numeric(length(rpt))
msecFT = numeric(length(rpt))
inp = rep("aaaaaaaaaa",15000)

for (i in rpt) {
  n = n + 1
  print(n)
  patt = paste(rep("a", rpt[n]), collapse = "")
  #time = microbenchmark(func(count[1:10000,12], patt, "b"), times = 10)
  timeFF = microbenchmark(gsub(patt, "b", inp, fixed=F), times = 10)
  msecFF[n] = mean(timeFF$time)/1000000.

  timeFT = microbenchmark(gsub(patt, "b", inp, fixed=T), times = 10)
  msecFT[n] = mean(timeFT$time)/1000000.
}

library(ggplot2)
library(grid)
library(gridExtra)

axis(1,at=seq(0,1000,200),labels=T)

p1 = qplot(rpt, msecFT, xlab="pattern length, characters", ylab="time, msec",main="fixed = TRUE" )
p2 = qplot(rpt, msecFF, xlab="pattern length, characters", ylab="time, msec",main="fixed = FALSE")
grid.arrange(p1, p2, nrow = 2)

如您所见,我正在寻找包含a复制rpt[n]时间的模式.正如预期的那样,斜率是正的.但是,我注意到300个字符fixed=T和600个字符的扭结,fixed=F然后斜率似乎与之前大致相同(见下图).我想,这是由于内存,对象大小等原因.我还注意到最长允许的pattern是1463个符号,对象大小为1552个字节.

有人可以更好地解释纠结以及300和600字符的原因吗？

补充:值得一提的是,我的大多数模式都是5到10个字符长,这使我得到了我的真实数据(不是inp上面例子中的模型)以下时间.

gsub, fixed = TRUE: ~50 msec per one pattern
gsub, fixed = FALSE: ~190 msec per one pattern
stringi, fixed = FALSE: ~55 msec per one pattern
gsub, fixed = FALSE, perl = TRUE: ~95 msec per one pattern

(我有4k模式,所以模块的总时间大约是200秒,gsub和fixed = TRUE正好是0.05 x 4000.这是我数据和模式的最快方法)

Answer 1

这些扭结可能与保存该长度模式所需的位有关。

还有另一种解决方案可以更好地扩展，使用重复运算符{}来指定要查找的重复次数。为了找到超过 255（最大 8 位整数）的值，您必须指定perl = TRUE.

patt2 <- paste0('a{',rpt[n],'}')
timeRF <- microbenchmark(gsub(patt2, "b", inp, perl = T), times = 10)

每次搜索的速度约为 2.1 毫秒，并且不会因模式长度而受到影响。对于小图案长度，这比“fixed = FALSE”快大约 8 倍，对于大图案长度，大约快 60 倍。