在 R 中匹配 "sub-vectors"

Question

所以 R 有一个很棒的函数 match，可以在向量中查找值（也可以用 %in% 来测试是否存在）。但是如果我想在一个大向量中找到一个短向量怎么办？也就是说，测试给定的向量是否包含（按顺序！）在另一个向量中？如果我想知道给定的向量是否是另一个向量的 prefix/suffix 怎么办？ R中有这样的函数吗？

我想要的示例：

x=c(1,3,4)
y=c(4,1,3,4,5)
z=c(3,1)

v_contains(x,y)  # return TRUE x is contained in y
v_contains(z,y)  # FALSE the values of z are in y, but not in the right order
v_match(x,y)     # returns 2 because x appears in y starting at position 2

有类似的吗？您将如何有效地处理它？

Answer 1

x=c(1,3,4)
y=c(4,1,3,4,5)
z=c(3,1)

# 1. return TRUE x is contained in y

stringr::str_detect(paste(y, collapse = "_"), paste(x, collapse = "_"))

# 2. FALSE the values of z are in y, but not in the right order

all(z %in% y) & stringr::str_detect(paste(y, collapse = "_"), paste(z, collapse = "_"))

# 3. returns 2 because x appears in y starting at position 2

stringr::str_locate(paste(y, collapse = "_"), paste(x, collapse = "_"))[1] - 1

Answer 2

如果 x 和 y 与问题中的一样，那么这里有一些替代方案。

1) rollapply 这将检查 x 是否包含在 y.

中

library(zoo)

any(rollapply(y, length(x), identical, x))
## [1] TRUE

2) embed 稍微复杂一点但仍然是一行并且没有包依赖性。

any(apply(t(embed(y, length(x))) == rev(x), 2, all))
## [1] TRUE

2a) 或这个变体：

any(apply(embed(y, length(x)), 1, identical, rev(x)))
## [1] TRUE

3) strings 把x和y都转换成字符串，用grepl。对该问题的评论已经指出了这种方法的代码。

4) Rcpp 如果速度很重要，那么我们可以用 C++ 编写代码。标准库已经内置了这个。将其放在当前目录中的文件 Search.cpp 中，并从 R 运行 library(Rcpp); sourceCpp("Search.cpp") 中获取。然后 R 代码 Search(x, y) 将调用它。

#include <Rcpp.h>

using namespace Rcpp;
using namespace std;

// [[Rcpp::export]]
bool Search(NumericVector x, NumericVector y) {
  return search(begin(y), end(y), begin(x), end(x)) != end(y);
}

Answer 3

A recent post 发现了 Jonathan Carroll 的这个解决方案。我怀疑 R 中是否存在更快的解决方案。

v_match <- function(needle, haystack, nomatch = 0L) { 
  sieved <- which(haystack == needle[1L]) 
  for (i in seq.int(1L, length(needle) - 1L)) {
    sieved <- sieved[haystack[sieved + i] == needle[i + 1L]]
  }
  sieved
}

v_contains <- function(needle, haystack) {
  sieved <- which(haystack == needle[1L]) 
  for (i in seq.int(1L, length(needle) - 1L)) {
    sieved <- sieved[haystack[sieved + i] == needle[i + 1L]]
  }
  length(sieved) && !anyNA(sieved)
}

测试和基准测试：

library(testthat)
x=c(1,3,4)
y=c(4,1,3,4,5)
z=c(3,1)

expect_true(v_contains(x,y))   # return TRUE x is contained in y
expect_false(v_contains(z,y))  # FALSE the values of z are in y, but not in order
expect_equal(v_match(x,y), 2)  # returns 2 because x appears in y starting at position 2

x <- c(5, 1, 3)
yes <- c(sample(5:1e6), c(5, 1, 3))
no <- c(sample(5:1e6), c(4, 1, 3))
expect_true(v_contains(x, yes))
expect_false(v_contains(x, no))
expect_equal(v_match(x, yes), 1e6 - 3)


v_contains_roll <- function(x, y) {
  any(zoo::rollapply(y, length(x), identical, x))
} 
v_contains_stri <- function(x, y) {
  stringr::str_detect(paste(y, collapse = "_"),
                      paste(x, collapse = "_"))
}

options(digits = 2)
options(scipen = 99)
library(microbenchmark)
gc(0, 1, 1)
#>           used (Mb) gc trigger (Mb) max used (Mb)
#> Ncells  527502   28    1180915   63   527502   28
#> Vcells 3010073   23    8388608   64  3010073   23
microbenchmark(v_contains(x, yes), 
               v_contains(x, no),
               v_contains_stri(x, yes),
               v_contains_stri(x, no),
               v_contains_roll(x, yes),
               v_contains_roll(x, no), 
               times = 2L,
               control = list(order = "block"))
#> Unit: milliseconds
#>                     expr    min     lq   mean median     uq    max neval
#>       v_contains(x, yes)    3.8    3.8    3.8    3.8    3.9    3.9     2
#>        v_contains(x, no)    3.7    3.7    3.7    3.7    3.8    3.8     2
#>  v_contains_stri(x, yes) 1658.4 1658.4 1676.7 1676.7 1695.0 1695.0     2
#>   v_contains_stri(x, no) 1632.3 1632.3 1770.0 1770.0 1907.8 1907.8     2
#>  v_contains_roll(x, yes) 5447.4 5447.4 5666.1 5666.1 5884.7 5884.7     2
#>   v_contains_roll(x, no) 5458.8 5458.8 5521.7 5521.7 5584.6 5584.6     2
#>  cld
#>  a  
#>  a  
#>   b 
#>   b 
#>    c
#>    c

^{由 reprex package (v0.2.0) 创建于 2018-08-18。}

在 R 中匹配 "sub-vectors"

matching "sub-vectors" in R

r

vector

matching