regex - gsub 速度 VS パターン長

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]。傾きは予想通り正です。fixed=Tただし、300 文字と 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 倍高速です。