我有一个长度可变的向量列表,例如:
q <- list(c(1,3,5), c(2,4), c(1,3,5), c(2,5), c(7), c(2,5))
我需要为列表中的每个向量计算出现次数,例如(任何其他适当的数据结构可接受):
list(list(c(1,3,5), 2), list(c(2,4), 1), list(c(2,5), 2), list(c(7), 1))
有没有一种高效的方法来做到这一点?实际列表有成千上万个项目,因此二次行为是不可行的。
我有一个长度可变的向量列表,例如:
q <- list(c(1,3,5), c(2,4), c(1,3,5), c(2,5), c(7), c(2,5))
我需要为列表中的每个向量计算出现次数,例如(任何其他适当的数据结构可接受):
list(list(c(1,3,5), 2), list(c(2,4), 1), list(c(2,5), 2), list(c(7), 1))
有没有一种高效的方法来做到这一点?实际列表有成千上万个项目,因此二次行为是不可行的。
match
和 unique
也接受并处理"list"(列表)类型(?match
对于 "list" 类型会提示其速度慢)。因此,对于:
match(q, unique(q))
#[1] 1 2 1 3 4 3
每个元素都映射到一个整数。然后:
tabulate(match(q, unique(q)))
#[1] 2 1 2 1
并找到一种结构来呈现结果:
as.data.frame(cbind(vec = unique(q), n = tabulate(match(q, unique(q)))))
# vec n
#1 1, 3, 5 2
#2 2, 4 1
#3 2, 5 2
#4 7 1
与使用match(x, unique(x))
方法相反,我们可以使用deparse
映射每个元素到单一值:
table(sapply(q, deparse))
#
# 7 c(1, 3, 5) c(2, 4) c(2, 5)
# 1 2 1 2
同时,由于这是一个包含独特整数的情况,并且假设在一个小范围内,我们可以在将每个元素转换为二进制表示后将每个元素映射到单个整数:
n = max(unlist(q))
pow2 = 2 ^ (0:(n - 1))
sapply(q, function(x) tabulate(x, nbins = n)) # 'binary' form
sapply(q, function(x) sum(tabulate(x, nbins = n) * pow2))
#[1] 21 10 21 18 64 18
然后像以前一样 制表
。
仅为比较上述替代方案:
f1 = function(x)
{
ux = unique(x)
i = match(x, ux)
cbind(vec = ux, n = tabulate(i))
}
f2 = function(x)
{
xc = sapply(x, deparse)
i = match(xc, unique(xc))
cbind(vec = x[!duplicated(i)], n = tabulate(i))
}
f3 = function(x)
{
n = max(unlist(x))
pow2 = 2 ^ (0:(n - 1))
v = sapply(x, function(X) sum(tabulate(X, nbins = n) * pow2))
i = match(v, unique(v))
cbind(vec = x[!duplicated(v)], n = tabulate(i))
}
q2 = rep_len(q, 1e3)
all.equal(f1(q2), f2(q2))
#[1] TRUE
all.equal(f2(q2), f3(q2))
#[1] TRUE
microbenchmark::microbenchmark(f1(q2), f2(q2), f3(q2))
#Unit: milliseconds
# expr min lq mean median uq max neval cld
# f1(q2) 7.980041 8.161524 10.525946 8.291678 8.848133 178.96333 100 b
# f2(q2) 24.407143 24.964991 27.311056 25.514834 27.538643 45.25388 100 c
# f3(q2) 3.951567 4.127482 4.688778 4.261985 4.518463 10.25980 100 a
另一个有趣的替代方案基于排序。R > 3.3.0具有一个基于data.table构建的“分组”函数,该函数可以与排序一起使用,并提供一些属性以进行进一步操作:
使所有元素长度相等并“转置”(这可能是本例中最慢的操作,尽管我不确定如何以其他方式提供grouping
):
n = max(lengths(q))
qq = .mapply(c, lapply(q, "[", seq_len(n)), NULL)
gr = do.call(grouping, qq)
e = attr(gr, "ends")
i = rep(seq_along(e), c(e[1], diff(e)))[order(gr)]
i
#[1] 1 2 1 3 4 3
然后,按照之前的方式制表。
继续进行比较:
f4 = function(x)
{
n = max(lengths(x))
x2 = .mapply(c, lapply(x, "[", seq_len(n)), NULL)
gr = do.call(grouping, x2)
e = attr(gr, "ends")
i = rep(seq_along(e), c(e[1], diff(e)))[order(gr)]
cbind(vec = x[!duplicated(i)], n = tabulate(i))
}
all.equal(f3(q2), f4(q2))
#[1] TRUE
microbenchmark::microbenchmark(f1(q2), f2(q2), f3(q2), f4(q2))
#Unit: milliseconds
# expr min lq mean median uq max neval cld
# f1(q2) 7.956377 8.048250 8.792181 8.131771 8.270101 21.944331 100 b
# f2(q2) 24.228966 24.618728 28.043548 25.031807 26.188219 195.456203 100 c
# f3(q2) 3.963746 4.103295 4.801138 4.179508 4.360991 35.105431 100 a
# f4(q2) 2.874151 2.985512 3.219568 3.066248 3.186657 7.763236 100 a
q
的元素长度很小以适应f3
,但是由于指数较大的缘故,f3
和由于mapply
的缘故 f4
将在性能上受到影响,如果使用了更大元素的“list”。一种方法是将每个向量粘贴在一起,然后解开并制表,即:
table(unlist(lapply(q, paste, collapse = ',')))
#1,3,5 2,4 2,5 7
# 2 1 2 1
sapply
来替换lapply
+ unlist
,即table(sapply(q, paste, collapse = ","))
。 - talatlapply
函数... - Sotos