regex - str_detect - str_replace r

velocidad de gsub vs longitud del patrón

Question

gsub he estado usando gsub ampliamente, y noté que los patrones cortos se ejecutan más rápido que los largos, lo que no es sorprendente. Aquí hay un código totalmente reproducible:

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)

Como ves, estoy buscando un patrón que contenga a rpt[n] veces replicado. La pendiente es positiva, como se esperaba. Sin embargo, noté un pliegue en 300 caracteres con fixed=T y 600 caracteres con fixed=F y luego la pendiente parece ser aproximadamente como antes (vea la gráfica a continuación). Supongo que se debe a la memoria, el tamaño del objeto, etc. También noté que el pattern más largo permitido es de 1463 símbolos, con un tamaño de objeto de 1552 bytes.

¿Alguien puede explicar mejor el problema y por qué con 300 y 600 caracteres?

Agregado: vale la pena mencionar que la mayoría de mis patrones son de 5 a 10 caracteres, lo que me da en mis datos reales (no en la maqueta de inp en el ejemplo anterior) la siguiente sincronización.

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

(Tengo 4k patrones, por lo que el tiempo total de mi módulo es de aproximadamente 200 segundos, que es exactamente de 0,05 x 4000 con gsub y corregido = VERDADERO. Es el método más rápido para mis datos y patrones)

Answer 1

Los pliegues pueden estar relacionados con los bits necesarios para mantener patrones de esa longitud.

Hay otra solución que se escala mucho mejor, use el operador de repetición {} para especificar cuántas repeticiones desea encontrar. Para encontrar más de 255 (8 bits máximo entero) deberá especificar perl = TRUE .

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

Obtengo velocidades de alrededor de 2.1 ms por búsqueda sin penalización por la longitud del patrón. Eso es aproximadamente 8 veces más rápido que fijo = FALSO para longitudes de patrón pequeñas y aproximadamente 60 veces más rápido para longitudes de patrón grandes.