r - 字符串向量中的高效模式检测

Question

我正在寻找最有效的解决方案来解决 this question 中提出的问题:假设您有一个字符串向量 v:

set.seed(314159)
library(stringi)
library(stringr)

v <- stringi::stri_rand_strings(10000, 4, pattern = "[A-Z]")

head(v)
#> [1] "FQGK" "YNQH" "IMNJ" "WUFU" "BBAR" "BZUH"

我想有效返回一个逻辑，表示给定模式(例如“FOO”)是否与v中的任何字符串匹配。预期函数的工作原理如下:

detect("FOO")
#> FALSE
detect("BAR")
#> TRUE

有多种方法可以使用基本 grep 函数或使用 stringr::str_detect 来执行此操作，但这些方法都首先需要在 的每个元素上匹配正则表达式v，在我的示例中进行了多达 9,999 次不必要的测试。有效的解决方案是在找到单个匹配项后停止评估。

对于每个解决方案 detect.#，我通过将其应用于所有三个字母组合 c 来对其进行基准测试:

c <- combn(LETTERS,3, FUN = function(x){paste(x, collapse = '')})
head(c)
#> [1] "ABC" "ABD" "ABE" "ABF" "ABG" "ABH"

可能的解决方案

我想出了一些可能的解决方案。首先，循环 v 以便在找到匹配项后不会进行不必要的模式匹配。正如您将看到的，这是一个糟糕的想法，开销很大:

detect.1 <- function(pattern){
  for (i in 1:length(v)){
    if (length(grep(pattern, v[i]))){return(TRUE)}
  }
  return(FALSE)
}

接下来，我们可以使用 any() 和 grepl() 或 stringr::str_detect() 的组合，但随后我们就这样做了不必要的匹配测试:

#str_detect() from stringr
detect.2 <- function(pattern){
  any(str_detect(v, pattern) )
}

# any() and grepl()
detect.3 <- function(pattern){
  any(grepl(pattern, v))
}

最后，如果我们知道某个字符从未出现在 pattern 中，我们可以将 v 折叠成单个字符串，其中各个组件由该字符分隔。那么单个 grep 就足够了:

#collapse to long string
v_pasted <- paste(v, collapse = '_')
detect.4 <- function(pattern){
  isTRUE(as.logical(grep(pattern, v_pasted)))
}

基准

(更新为使用 bench::mark())

det1 <- expression(data.frame(c, "inV" = I(lapply(c, FUN = detect.1))))
det2 <- expression(data.frame(c, "inV" = I(lapply(c, FUN = detect.2))))
det3 <- expression(data.frame(c, "inV" = I(lapply(c, FUN = detect.3))))
det4 <- expression({
  v_pasted <- paste(v, collapse = '_')
  data.frame(c, "inV" = I(lapply(c, FUN = detect.4)))
})

bench::mark(
  eval(det1),
  eval(det2),
  eval(det3),
  eval(det4),
  iterations = 5,
  relative = TRUE
)
#> Warning: Some expressions had a GC in every iteration; so filtering is
#> disabled.
#> # A tibble: 4 x 10
#>   expression   min  mean median   max `itr/sec` mem_alloc  n_gc n_itr
#>   <chr>      <dbl> <dbl>  <dbl> <dbl>     <dbl>     <dbl> <dbl> <dbl>
#> 1 eval(det1) 76.9  77.0   76.8  77.2        1        1      Inf     1
#> 2 eval(det2)  4.02  4.03   4.04  4.05      19.1    735.     Inf     1
#> 3 eval(det3)  2.77  2.79   2.79  2.80      27.6    735.     Inf     1
#> 4 eval(det4)  1     1      1     1         77.0      1.22   NaN     1

grepl 明显比 str_detect 快。粘贴方法速度最快，但要求您具有不会出现在可能的搜索模式中的分隔字符。我缺少一些更快的替代方案吗？

Answer 1

stringi 包中的这个函数应该更快:

any(stri_detect_fixed(v, pattern, max_count = 1))

长凳:

require(stringi)
detect.m <- function(pattern){
  any(stri_detect_fixed(v, pattern, max_count = 1))
}

detm <- expression(data.frame(c, "inV" = I(lapply(c, FUN = detect.m))))
r <- bench::mark(
  # eval(det1),
  eval(det2),
  eval(det3),
  eval(det4),
  eval(detm),
  iterations = 5,
  relative = TRUE
)
r[, 1:10]
#   expression   min  mean median   max `itr/sec` mem_alloc  n_gc n_itr total_time
#    <chr>      <dbl> <dbl>  <dbl> <dbl>     <dbl>     <dbl> <dbl> <dbl>      <dbl>
# 1 eval(det2)  4.83  5.39   5.02  5.94      1         600.     9     1       5.39
# 2 eval(det3)  3.85  3.69   3.80  3.31      1.46      600.    10     1       3.69
# 3 eval(det4)  1.35  1.32   1.36  1.20      4.08        1      1     1       1.32
# 4 eval(detm)  1     1      1     1         5.39      600.     9     1       1   

更大的基准

# lets create larger test case for better comparison:

a <- expand.grid(lapply(1:5, function(x) LETTERS))
a <- do.call(paste0, a)
f10 <- a[10] # lets search for 10th element
last <- a[length(a)] # and last
length(a)
length(unique(a))

v <- a

detm <- function(pattern){
  any(stri_detect_fixed(v, pattern, max_count = 1))
}

det4 <- function(pattern){
  # should include paste
  v_pasted <- paste(v, collapse = '_')
  # isTRUE(as.logical(grep(pattern, v_pasted)))
  isTRUE(grepl(pattern, v_pasted, fixed = T)) # faster
}

system.time(detm(last)) # 0.74
system.time(detm(f10)) #  0.33

system.time(det4(last)) # 3.38
system.time(det4(f10)) #  3.08