logo标签列表

统计列表中向量出现的次数

r
11

我有一个长度可变的向量列表，例如：

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))

有没有一种高效的方法来做到这一点？实际列表有成千上万个项目，因此二次行为是不可行的。

1
你可以使用哈希函数，然后根据哈希值将所需列表分类，这样可以大大降低平均复杂度。 - Martin Nyolt
7
"match"和"unique"也适用于"list" -- 执行"match(q, unique(q))"，然后制表统计出现次数。 - alexis_laz
2个回答
18

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”。
7

一种方法是将每个向量粘贴在一起，然后解开并制表，即：

table(unlist(lapply(q, paste, collapse = ',')))

#1,3,5   2,4   2,5     7 
#    2     1     2     1
3
不错的替代方法——你也可以使用sapply来替换lapply + unlist，即table(sapply(q, paste, collapse = ","))。 - talat
@docendodiscimus 是真的。每当我看到列表时，我总是不自觉地使用 lapply 函数... - Sotos
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接