确定元素是否存在于向量中的最有效方法

Question

我有几种算法取决于确定元素是否存在于向量中的效率.在我看来%in%(相当于is.element())应该是最有效的,因为它只返回一个布尔值.在测试了几种方法后,令我惊讶的是,这些方法到目前为止效率最低.以下是我的分析(随着矢量大小的增加,结果变得更糟):

EfficiencyTest <- function(n, Lim) {

    samp1 <- sample(Lim, n)
    set1 <- sample(Lim, Lim)

    print(system.time(for(i in 1:n) {which(set1==samp1[i])}))
    print(system.time(for(i in 1:n) {samp1[i] %in% set1}))
    print(system.time(for(i in 1:n) {is.element(samp1[i], set1)}))
    print(system.time(for(i in 1:n) {match(samp1[i], set1)}))
    a <- system.time(set1 <- sort(set1))
    b <- system.time(for (i in 1:n) {BinVecCheck(samp1[i], set1)})
    print(a+b)
}

> EfficiencyTest(10^3, 10^5)
user  system elapsed 
0.29    0.11    0.40 
user  system elapsed 
19.79    0.39   20.21 
user  system elapsed 
19.89    0.53   20.44 
user  system elapsed 
20.04    0.28   20.33 
user  system elapsed 
0.02    0.00    0.03 

BinVecCheck我写的二进制搜索算法在哪里返回TRUE/ FALSE.请注意,我包含使用最终方法对矢量进行排序所需的时间.这是二进制搜索的代码:

BinVecCheck <- function(tar, vec) {      
    if (tar==vec[1] || tar==vec[length(vec)]) {return(TRUE)}        
    size <- length(vec)
    size2 <- trunc(size/2)
    dist <- (tar - vec[size2])       
    if (dist > 0) {
        lower <- size2 - 1L
        upper <- size
    } else {
        lower <- 1L
        upper <- size2 + 1L
    }        
    while (size2 > 1 && !(dist==0)) {
        size2 <- trunc((upper-lower)/2)
        temp <- lower+size2
        dist <- (tar - vec[temp])
        if (dist > 0) {
            lower <- temp-1L
        } else {
            upper <- temp+1L
        }
    }       
    if (dist==0) {return(TRUE)} else {return(FALSE)}
}

平台信息:

> sessionInfo()
R version 3.2.1 (2015-06-18)
Platform: x86_64-w64-mingw32/x64 (64-bit)
Running under: Windows 7 x64 (build 7601) Service Pack 1

题

是否有更有效的方法来确定元素是否存在于R中的向量中？例如,是否有与Python 集函数等效的R 函数,这大大改进了这种方法？而且,%in%即使与which提供更多信息的函数(不仅确定存在,而且还给出所有真实账户的指数)相比,为什么等等效率如此低效？

Answer 1

我的测试并没有证实你的所有说法,但似乎(？)是由于跨平台的差异(这使问题更加神秘,可能值得继续r-devel@r-project.org,尽管可能不是因为fastmatch下面的解决方案占主导地位无论如何...)

 n <- 10^3; Lim <- 10^5
 set.seed(101)
 samp1 <- sample(Lim,n)
 set1 <- sample(Lim,Lim)
 library("rbenchmark")

 library("fastmatch")
 `%fin%` <- function(x, table) {
     stopifnot(require(fastmatch))
     fmatch(x, table, nomatch = 0L) > 0L
 }
 benchmark(which=sapply(samp1,function(x) which(set1==x)),
           infun=sapply(samp1,function(x) x %in% set1),
           fin= sapply(samp1,function(x) x %fin% set1),
           brc= sapply(samp1,BinVecCheck,vec=sort(set1)),
           replications=20,
    columns = c("test", "replications", "elapsed", "relative"))

##    test replications elapsed relative
## 4   brc           20   0.871    2.329
## 3   fin           20   0.374    1.000
## 2 infun           20   6.480   17.326
## 1 which           20  10.634   28.433

这说%in%快了大约两倍which- 你的BinVecCheck功能要好7倍,但是这里的fastmatch解决方案得到另一个因素2.我不知道专门的Rcpp实现是否可以做得更好......事实上,我即使在运行代码时也能得到不同的答案:

##    user  system elapsed   (which)
##   0.488   0.096   0.586 
##    user  system elapsed   (%in%) 
##   0.184   0.132   0.315 
##    user  system elapsed  (is.element)
##   0.188   0.124   0.313 
##    user  system elapsed  (match)
##   0.148   0.164   0.312 
##    user  system elapsed  (BinVecCheck)
##   0.048   0.008   0.055 

更新:关于r-develPeter Dalgaard通过指向R NEWS条目解释平台差异(这是R版本差异,而不是OS差异):

match(x, table)x感谢Haverty的PR#16491 ,它的速度更快,有时甚至是一个数量级,当长度为1且不可比的时间不变时.

sessionInfo()
## R Under development (unstable) (2015-10-23 r69563)
## Platform: i686-pc-linux-gnu (32-bit)
## Running under: Ubuntu precise (12.04.5 LTS)