R语言 查找一个向量的匹配元素在另一个向量中的位置

dpiehjr4  于 2023-03-20  发布在  其他
关注(0)|答案(6)|浏览(293)

我有两个很长的向量:

a <- sample(1e+08L, size = 1e+09L, replace = TRUE)
b <- sample(1e+08L, size = 1e+09L, replace = TRUE)

我想生成一个长度为length(a)的整数向量r,使得r[i]a[i]b中的索引。
我试过pmatch(a, b)但是很慢。有没有更有效的方法?
小示例的预期输出:

a <- c(1, 3, 5, 7, 8)
b <- c(3, 1, 7, 8, 5)
f(a, b)
## [1] 2 1 5 3 4
wf82jlnq

wf82jlnq1#

您的问题提到了pmatch,它执行字符向量的部分匹配,但您似乎需要match,它执行整数和其他向量的精确匹配。
match更快,但比match更快的是fastmatch::fmatch

match(b, a)
fastmatch::fmatch(b, a)

在基准测试中添加:
x一个一个一个一个x一个一个二个x

omjgkv6w

omjgkv6w2#

基准:

library(fastmatch)   #fmatch
library(data.table)  #merge
library(collections) #hash

Rcpp::cppFunction('IntegerVector matchC(NumericVector x, NumericVector table) {
  IntegerVector out(x.size(), NA_INTEGER);
  for(int i = 0; i < x.size(); i++) {
    for(int j = 0; j < table.size(); j++) {
      if(x[i] == table[j]) {
        out[i] = j + 1;
        break;
      }
    }
  }
  return out;
}')
    
set.seed(1); a <- sample(1e5, 1e5); b <- sample(1e5, 1e4)
    
bench::mark(
  match = { match(a, b) },
  fmatch = { fmatch(a, b) },
  zx8754.merge = {
    merge(data.table(x = a, rnA = seq_along(a), key = "x"),
          data.table(x = b, rnB = seq_along(b), key = "x"),
          all.x = TRUE)[order(rnA), rnB] },
  sotos.Rcpp = { matchC(a, b) },
  user2974951.hash = {
    h = dict(seq_along(b), b)
    sapply(a, h$get, default = NA)},
  "jblood94.[" = `[<-`(NA_integer_, b, seq_along(b))[a]
)

结果

expression            min   median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc
  <bch:expr>       <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int> <dbl>
1 match              4.44ms    4.7ms   210.      951.3KB     3.96   106     2
2 fmatch             1.45ms   1.47ms   672.     393.34KB     3.99   337     2
3 zx8754.merge       7.77ms   8.38ms   115.       8.05MB    13.9     58     7
4 sotos.Rcpp          2.78s    2.78s     0.360    1.22MB     0        1     0
5 user2974951.hash 236.46ms 238.72ms     4.20     3.44MB    19.6      3    14
6 jblood94.[       418.16µs 422.64µs  2082.     800.85KB    34.0   1041    17
pn9klfpd

pn9klfpd3#

或者,你可以创建一个哈希表(由于某种原因,它不存在于基R中),然后你可以在O(1)时间内查找b中每个元素的索引。

> library(collections)
> h=dict(seq_along(b),b)
> sapply(a,h$get,default=NA)
[1] 2 1 5 3 4
qlzsbp2j

qlzsbp2j4#

转换为 * 数据.表 * 并 * 合并 *:

library(data.table)

merge(data.table(x = a, rnA = seq_along(a), key = "x"),
      data.table(x = b, rnB = seq_along(b), key = "x"),
      all.x = TRUE)[order(rnA), rnB]
# [1] 2 1 5 3 4
ttygqcqt

ttygqcqt5#

根据GKi的评论更新。
如果ab都是整数向量,并且length(b) ~ max(b),索引将更快:

library(fastmatch)   #fmatch

intmatch1 <- function(a, b, maxb = max(b)) {
  B <- rep(NA_integer_, maxb)
  B[b] <- seq_along(b)
  B[a]
}

intmatch2 <- function(a, b) {
  `[<-`(NA_integer_, b, seq_along(b))[a]
}

set.seed(1); a <- sample(1e5); b <- sample(1e5, 1e4)

microbenchmark::microbenchmark(
  match = match(a, b),
  fmatch = fmatch(a, b),
  intmatch1.1 = intmatch1(a, b),
  intmatch1.2 = intmatch1(a, b, 1e5),
  intmatch2 = intmatch2(a, b),
  check = "identical")
#> Unit: microseconds
#>         expr      min       lq      mean    median       uq      max neval
#>        match 2543.101 2593.901 2800.5480 2646.7020 2732.801 7627.601   100
#>       fmatch 1107.801 1181.551 1272.0101 1201.4510 1261.601 5928.401   100
#>  intmatch1.1  316.401  375.451  418.3490  402.3005  424.351  658.001   100
#>  intmatch1.2  327.000  386.851  522.8529  401.7505  456.901 5670.001   100
#>    intmatch2  277.402  347.051  424.7270  359.6010  382.902 5026.601   100
whhtz7ly

whhtz7ly6#

如果目标只是match(),那么我们可以用途:

cppFunction('IntegerVector matchC(NumericVector x, NumericVector table) {
  IntegerVector out(x.size(), NA_INTEGER);
  for(int i = 0; i < x.size(); i++) {
    for(int j = 0; j < table.size(); j++) {
      if(x[i] == table[j]) {
        out[i] = j + 1;
        break;
      }
    }
  }
  return out;
}')

相关问题