根据一组子字符串高效过滤字符串

Question

我的一般问题是如何根据任意一组可能的子字符串过滤任意一组字符串。

我的特殊问题是我有一长串包含 UUID 的文件名，并且我有一个我想从中过滤掉的其他 UUID 的列表。我的数据集在长度和最终匹配的比例方面可能有所不同，从 n = 10 到 1,000,000，命中率从 0% 到 100%。我不认为匹配率是我方法性能的一个重要因素，但我知道大小确实很重要。

我天真的做法如下。本质上，我从一个 UUID 向量中将它们与

|

连接在一起，以制作一个长正则表达式，并针对它测试原始数据的每个成员。这对于小数据来说非常快，但很快就会失控。

设置：

# create a master population to choose from
uuid_list <- uuid::UUIDgenerate(n = 1e5)

filter_from_string <- function(n) {
  
  # choose a representative population
  uuid_population <- sample(uuid_list, n)
  
  # generate the longer strings
  data_strings <- 
    paste0(
      "Here_are_some_strings_with_associated_UUIDs_",
      uuid_population,
      "_and_additional_metadata.json"
    )
  
  # generate a small sample to check against
  uuid_sample <- sample(uuid_population, n/10)
  
  # check against a single long regex that looks like:
  #   "uuid1|uuid2|uuid3|..."
  filter_index <- 
    stringr::str_detect(
      data_strings,
      paste(uuid_sample, collapse = "|")
    )
  
  data_strings[!filter_index]
}

测试：

x <- 
  microbenchmark::microbenchmark(
    "n=10" = filter_from_string(10),
    "n=100" = filter_from_string(100),
    "n=1000" = filter_from_string(1000),
    "n=10000" = filter_from_string(10000),
    times = 10
  )
#> Warning in microbenchmark::microbenchmark(`n=10` = filter_from_string(10), :
#> less accurate nanosecond times to avoid potential integer overflows

# milliseconds
summary(x, "ms")[c("expr", "mean", "median")]
#>      expr         mean       median
#> 1    n=10    0.4201393    0.0713195
#> 2   n=100    1.4376527    0.4230585
#> 3  n=1000   25.4073679   25.8098075
#> 4 n=10000 2340.1810916 2313.1806605

# relative time
summary(x, "relative")[c("expr", "mean", "median")]
#>      expr        mean       median
#> 1    n=10    1.000000     1.000000
#> 2   n=100    3.421848     5.931877
#> 3  n=1000   60.473676   361.889911
#> 4 n=10000 5570.012354 32434.056051

^{创建于 2023-05-03 与 reprex v2.0.2}

如您所见，性能比每步的 10 倍长得多。

我有一个关于如何在我的特定用例中加速它的修复程序。我可以从字符串中提取 UUID，因为它是已知模式，然后对样本进行完全相等匹配。我会在下面的答案中发布这个，但是我很好奇当没有明显的模式可以使用时该怎么办，而是任何字符串和可能的子字符串。

Answer 1

对于这个具有良好行为模式的特定用例，您可以从较长的名称中提取出目标子字符串，然后对样本进行精确相等匹配。

设置：

# create a master population to choose from
uuid_list <- uuid::UUIDgenerate(n = 1e5)

filter_from_string_extract <- function(n) {
  
  # choose a representative population
  uuid_population <- sample(uuid_list, n)
  
  # generate the longer strings
  data_strings <- paste0(
        "Here_are_some_strings_with_associated_UUIDs_",
        uuid_population,
        "_and_additional_metadata.json"
      )
  
  # pre-extract just the UUID into a new vector
  data_uuids <- 
    stringr::str_extract(
      data_strings,
      "[a-f0-9]{8}-[a-f0-9]{4}-[a-f0-9]{4}-[a-f0-9]{4}-[a-f0-9]{12}"
    )
  
  # generate a small sample to check against
  uuid_sample <- sample(uuid_population, n/10)
  
  # filter on exact match of the UUID instead of regex pattern
  data_strings[!(data_uuids %in% uuid_sample)]
}

测试：

y <- 
  microbenchmark::microbenchmark(
    "n=10" = filter_from_string_extract(10),
    "n=100" = filter_from_string_extract(100),
    "n=1000" = filter_from_string_extract(1000),
    "n=10000" = filter_from_string_extract(10000),
    "n=100000" = filter_from_string_extract(100000),
    times = 10
  )
#> Warning in microbenchmark::microbenchmark(`n=10` =
#> filter_from_string_extract(10), : less accurate nanosecond times to avoid
#> potential integer overflows

# milliseconds
summary(y, "ms")[c("expr", "mean", "median")]
#>       expr        mean      median
#> 1     n=10   0.0994824   0.0759730
#> 2    n=100   0.2499114   0.2374515
#> 3   n=1000   1.8917400   1.8155005
#> 4  n=10000  18.4703319  17.4055865
#> 5 n=100000 204.7527167 199.9893490

# relative time
summary(y, "relative")[c("expr", "mean", "median")]
#>       expr        mean      median
#> 1     n=10    1.000000    1.000000
#> 2    n=100    2.512117    3.125472
#> 3   n=1000   19.015826   23.896654
#> 4  n=10000  185.664318  229.102267
#> 5 n=100000 2058.180308 2632.373988

^{创建于 2023-05-03 与 reprex v2.0.2}

即使再提高一个数量级，也有可接受的性能，并且它似乎与

n

成线性关系。