r - R中%in%的时间复杂度；有没有办法让它像 Python 中的集合一样 O(1)？

Question

%in% R 中的运算符检查是否有其他内容，这很明显。但我对性能很好奇。在 Python 中，搜索一个项目集合或字典键是 O(1)，因为我认为集合是哈希表。但是在 Python 中搜索列表中的项目可能是 O(n) 和一个长度为 n 的列表，因为它将逐个元素搜索。那么如何%in%在幕后为 R 中的不同数据类型工作？与向量相反，在 R 中的因子 dtype 中搜索某些内容似乎需要 5 倍的时间，但似乎是 %in%线性搜索向量。起初我认为一个因子数据类型可能就像 Python 中的一个集合，因为它们都将某些东西减少到它的唯一值，但根本不是:https://www.tutorialspoint.com/r/r_data_types.htm .这是一些示例代码，因此您可以了解我对运行时的含义:

library(microbenchmark)
s <- seq(5000)
microbenchmark(1 %in% s, times = 100000)
# searching for a term further in the list takes longer
microbenchmark(4999 %in% s, times = 100000)
s <- as.factor(s)
# searching for something in a factor takes way longer than a vector
# I think because everything is converted to a character dtype
microbenchmark(4999 %in% s, times = 100000)

我的主要问题是:有没有办法在 R 中制作 %in% O(1) ？一个相关的问题:Python 中的 set() 数据类型是否有等价的(在 R 中)？

Answer 1

正如我们在评论中所讨论的那样，R 中有一个固有的类似集合的机制，尽管它确实有点骇人听闻，而且可能并不完全符合预期。 (这个 hack 的一些限制记录在 hashmap 包中。)

R 中的环境是内部散列的。这可用于存储具有随机访问(读取和写入)的任意对象。为了检查一些基准，我将生成几种类型的向量来证实您最初的关注并展示使用环境可以带来的改进。

我们将首先生成一些类似的数据，以各种方式排序以突出您提出的问题:

library(microbenchmark)
set.seed(2)
s1 <- seq(5000)
s2 <- rev(s1) # to highlight the bias you highlighted, since the vector is sorted
s3 <- sample(s1) # to shake things up a little
s4 <- as.character(s3) # comparison with character-based named in 'l' and 'e'

l <- list()
e <- new.env(parent = emptyenv())
for (i in s4) {
  assign(i, TRUE, envir = e)
  l[[i]] <- TRUE
}
head(names(l)) # unordered
# [1] "925"  "3512" "2866" "840"  "4716" "4713"

list 在其对象中确实具有序数，这支持其对象未被散列的假设:

which(names(l) == "1")
# [1] 2291

环境没有这个:

e[[1]]
# Error in e[[1]] : wrong arguments for subsetting an environment

一些快速的成员资格测试:我使用了一个逻辑值，尽管这完全是任意的。除了 NULL 之外的任何东西都足以满足我们的需求。我们将使用一个简单的 !is.null(e[[...]]) 来测试特定的成员资格:

!is.null(e[["1"]])
# [1] TRUE
!is.null(e[["10000"]])
# [1] FALSE
!is.null(l[["1"]])
# [1] TRUE
!is.null(l[["10000"]])
# [1] FALSE

microbenchmark(
  vec1 =  1  %in% s1,
  vec2 =  1  %in% s2,
  vec3 =  1  %in% s3,
  vec4 = "1" %in% s4,
  lst = is.null(l[["1"]]),
  env = is.null(e[["1"]]),
  times = 1000
)
# Warning in microbenchmark(vec1 = 1 %in% s1, vec2 = 1 %in% s2, vec3 = 1 %in%  :
#   Could not measure a positive execution time for 6 evaluations.
# Unit: nanoseconds
#  expr   min    lq     mean median    uq     max neval
#  vec1  5835  6929 12493.25   7294  9482 3214588  1000
#  vec2  9117  9847 16660.73  10212 12764 4081050  1000
#  vec3  7294  8388 19983.63   8752 10576 3274759  1000
#  vec4 11670 12400 15423.03  12764 14223   74394  1000
#   lst 20787 21517 24561.72  21881 22975  143317  1000
#   env     0     1   461.25    365   366   18235  1000

毫不奇怪， list 表现不佳，尽管它似乎比向量表现得更好(在 max 情况下，相对无意义)。同样不足为奇的是，根据我们声称环境使用内部 has 的说法，它表现得非常好。是 O(1) 吗？

microbenchmark(
     samp5 = sapply(as.character(sample(5000, size =    5)), function(a) is.null(e[[a]])),
    samp50 = sapply(as.character(sample(5000, size =   50)), function(a) is.null(e[[a]])),
   samp500 = sapply(as.character(sample(5000, size =  500)), function(a) is.null(e[[a]])),
  samp5000 = sapply(as.character(sample(5000, size = 5000)), function(a) is.null(e[[a]]))
)
# Unit: microseconds
#      expr      min         lq        mean     median         uq       max neval
#     samp5   25.893    32.4565    49.58154    40.4795    58.3485   169.573   100
#    samp50  108.309   119.4310   156.45244   135.8410   167.3850   681.938   100
#   samp500  935.750  1023.2715  1265.29732  1073.9610  1172.6055  6841.985   100
#  samp5000 9410.008 10337.5520 11137.82968 10650.0765 11280.0485 15455.548   100

第一个 samp5 似乎需要更长的时间。这并不奇怪，因为存在与 sapply 、采样和其他事情相关的开销。然而，剩余的行似乎随着样本数量的增加而扩展得很好。这表明对于一些基本的集合操作确实是 O(1)。

注意:我不得不使用整个 sapply(...) 技巧，因为与向量和列表不同，R 的环境不允许使用向量进行子集化。

e[[c("1")]]
# [1] TRUE
e[[c("1","10")]]
# Error in e[[c("1", "10")]] : 
#   wrong arguments for subsetting an environment

这是 hashmap 提出(并修复)的声明之一。

加分:为了便于将环境作为一个集合使用，您可以使用简单的加法器和删除器:

newset <- function() new.env(parent = emptyenv())
setadd <- function(set, n) set[[n]] <- TRUE
setdel <- function(set, n) set[[n]] <- NULL
setcontains <- function(set, n) !is.null(set[[n]])
setmembers <- function(set) names(set)

e <- newset()
setcontains(e, "a")
# [1] FALSE
setadd(e, "a")
setcontains(e, "a")
# [1] TRUE
setmembers(e)
# [1] "a"
setdel(e, "a")
setcontains(e, "a")
# [1] FALSE

(这里有一篇由 Jeffrey Horner 撰写的类似但更广泛的博客文章: http://jeffreyhorner.tumblr.com/post/114524915928/hash-table-performance-in-r-part-i 。)