R中%in%的时间复杂度；有没有办法让它像 Python 中的集合一样 O(1)？
Time complexity of %in% in R; is there a way to make it O(1) like with sets in Python?
R 中的 %in% 运算符检查是否有东西在其他东西中，有点明显。但我对性能很好奇。在 Python 中，搜索一个集合或字典键的项是 O(1)，因为集合是散列 table，我认为。但是在 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 中）
正如我们在评论中所讨论的那样，是 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) 在这里有一篇类似但更广泛的博客 post：http://jeffreyhorner.tumblr.com/post/114524915928/hash-table-performance-in-r-part-i。）
R 中的 %in% 运算符检查是否有东西在其他东西中，有点明显。但我对性能很好奇。在 Python 中，搜索一个集合或字典键的项是 O(1)，因为集合是散列 table，我认为。但是在 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 中）正如我们在评论中所讨论的那样，是 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) 在这里有一篇类似但更广泛的博客 post：http://jeffreyhorner.tumblr.com/post/114524915928/hash-table-performance-in-r-part-i。）