logo标签列表

每个唯一元素出现次数的最快计算方法

performanceraggregate
17
什么是在R中计算向量中每个唯一元素出现次数的最快方法？
到目前为止，我尝试了以下五个函数：
f1 <- function(x)
{
    aggregate(x, by=list(x), FUN=length)
}


f2 <- function(x)
{
    r <- rle(x)
    aggregate(r$lengths, by=list(r$values), FUN=sum)
}


f3 <- function(x)
{
    u <- unique(x)
    data.frame(Group=u, Counts=vapply(u, function(y)sum(x==y), numeric(1)))
}

f4 <- function(x)
{
    r <- rle(x)
    u <- unique(r$values)
    data.frame(Group=u, Counts=vapply(u, function(y)sum(r$lengths[r$values==y]), numeric(1)))
}

f5 <- function(x)
{
    as.data.frame(unclass(rle(sort(x))))[,2:1]
}

有些测试结果并没有按照类别排序，但这并不重要。以下是测试结果（使用的软件包为microbenchmark）：

> x <- sample(1:100, size=1e3, TRUE); microbenchmark(f1(x), f2(x), f3(x), f4(x), f5(x))
Unit: microseconds
  expr      min        lq    median        uq      max neval
 f1(x) 4133.353 4230.3700 4272.5985 4394.1895 7038.420   100
 f2(x) 4464.268 4549.8180 4615.3465 4728.1995 7457.435   100
 f3(x) 1032.064 1063.0080 1091.7670 1135.4525 3824.279   100
 f4(x) 4748.950 4801.3725 4861.2575 4947.3535 7831.308   100
 f5(x)  605.769  696.9615  714.9815  729.5435 3411.817   100
> 
> x <- sample(1:100, size=1e4, TRUE); microbenchmark(f1(x), f2(x), f3(x), f4(x), f5(x))
Unit: milliseconds
  expr       min        lq    median        uq       max neval
 f1(x) 25.057491 25.739892 25.937021 26.321998 27.875918   100
 f2(x) 27.223552 27.718469 28.023355 28.537022 30.584403   100
 f3(x)  5.361635  5.458289  5.537650  5.657967  8.261243   100
 f4(x) 35.341726 35.841922 36.299161 38.012715 70.096613   100
 f5(x)  2.158415  2.248881  2.281826  2.384304  4.793000   100
> 
> x <- sample(1:100, size=1e5, TRUE); microbenchmark(f1(x), f2(x), f3(x), f4(x), f5(x), times=10)
Unit: milliseconds
  expr       min        lq    median        uq       max neval
 f1(x) 236.53630 240.93358 242.88631 244.33994 250.75403    10
 f2(x) 261.03280 263.61096 264.67032 265.81852 297.92244    10
 f3(x)  53.94873  55.59020  59.05662  61.05741  87.23288    10
 f4(x) 385.10217 390.44888 396.40572 399.23762 432.47262    10
 f5(x)  18.31358  18.53492  18.84327  20.22700  20.34385    10
> 
> x <- sample(1:100, size=1e6, TRUE); microbenchmark(f1(x), f2(x), f3(x), f4(x), f5(x), times=3)
Unit: milliseconds
  expr       min        lq    median        uq       max neval
 f1(x) 2559.0462 2568.7480 2578.4498 2693.3116 2808.1734     3
 f2(x) 2833.2622 2881.9241 2930.5860 2946.7877 2962.9895     3
 f3(x)  743.6939  748.3331  752.9723  778.9532  804.9341     3
 f4(x) 4471.8494 4544.6490 4617.4487 4696.2698 4775.0909     3
 f5(x)  243.8903  253.2481  262.6058  269.1038  275.6018     3
> 
> x <- sample(1:1000, size=1e6, TRUE); microbenchmark(f1(x), f2(x), f3(x), f4(x), f5(x), times=3)
Unit: milliseconds
  expr        min         lq     median         uq        max neval
 f1(x)  2614.7104  2634.9312  2655.1520  2701.6216  2748.0912     3
 f2(x)  3038.0353  3116.7499  3195.4645  3197.7423  3200.0202     3
 f3(x)  6488.7268  6508.6495  6528.5722  6836.9738  7145.3754     3
 f4(x) 40244.5038 40653.2633 41062.0229 41200.1973 41338.3717     3
 f5(x)   244.2052   245.0331   245.8609   273.3307   300.8006     3
> x <- sample(1:10000, size=1e6, TRUE); microbenchmark(f1(x), f2(x), f3(x), f4(x), f5(x), times=3)  # SLOW!
Unit: milliseconds
  expr         min          lq      median          uq         max neval
 f1(x)   3279.2146   3300.7527   3322.2908   3338.6000   3354.9091     3
 f2(x)   3563.5244   3578.3302   3593.1360   3597.2246   3601.3132     3
 f3(x)  61303.6299  61928.4064  62553.1830  63089.5225  63625.8621     3
 f4(x) 398792.7769 400346.2250 401899.6732 490921.6791 579943.6850     3
 f5(x)    261.1835    263.7766    266.3697    287.3595    308.3494     3

（最后一个比较非常慢，需要几分钟才能运行。）

显然，胜利者是f5，但我想看看是否可以超越它...

编辑：考虑到@eddi的建议f6，@AdamHyland（修改后）的f8和@dickoa的f9，这里是新结果：

f6 <- function(x)
{
    data.table(x)[, .N, keyby = x]
}

f8 <- function(x)
{
    fac <- factor(x)

    data.frame(x = levels(fac), freq = tabulate(as.integer(fac)))
}

f9 <- plyr::count

结果：

> x <- sample(1:1e4, size=1e6, TRUE); microbenchmark(f5(x), f6(x), f8(x), f9(x), times=10)
Unit: milliseconds
  expr      min        lq   median        uq      max neval
 f5(x) 291.8189 292.69771 293.2349 293.91216 296.3622    10
 f6(x)  96.5717  96.73662  96.8249  99.25542 150.1081    10
 f8(x) 659.3281 663.85092 669.6831 672.43613 699.4790    10
 f9(x) 284.2978 296.41822 301.3535 331.92510 346.5567    10
> x <- sample(1:1e3, size=1e7, TRUE); microbenchmark(f5(x), f6(x), f8(x), f9(x), times=10)
Unit: milliseconds
  expr       min        lq   median       uq      max neval
 f5(x) 3190.2555 3224.4201 3264.415 3359.823 3464.782    10
 f6(x)  980.1287  989.9998 1051.559 1056.484 1085.580    10
 f8(x) 5092.5847 5142.3289 5167.101 5244.400 5348.513    10
 f9(x) 2799.6125 2843.1189 2881.734 2977.116 3081.437    10

所以目前为止，data.table是获胜者！

附言：我不得不修改f8，以允许像c(5,2,2,10)这样的输入，其中并非所有整数从1到max(x)都存在。

也许我错过了一些显而易见的东西，但你只是想完成table所做的事情吗？ - joran
@joran，我刚试了一下，table比f5慢。 - Ferdinand.kraft
1
顺便说一句，如果只运行3次，使用microbenchmark没有太多意义。 - Michele
3
@Michele，为什么不呢？我使用了3次运行，因为它非常慢。我应该使用system.time吗？ - Ferdinand.kraft
1
此外，不要对 f5 过于兴奋，它在因数上根本无法运行！这可能对您来说并非必需，但重要的是要记住，构建此类快速版本会破坏许多其他您可能希望正常工作的东西... - joran
显示剩余4条评论
2个回答
14

只要符合初始条件，几乎没有什么能够超越 tabulate()。

x <- sample(1:100, size=1e7, TRUE)
system.time(tabulate(x))
#  user  system elapsed 
# 0.071   0.000   0.072

@dickoa在评论中补充了一些有关如何获得适当输出的注释，但是使用tabulate作为工具函数是最好的选择。

@dickoa在评论中添加了一些有关如何获取所需输出的说明，但是将tabulate作为工具函数是最佳选择。

我以前从未使用过tabulate，所以可能我错过了什么，但是这个输出与OP中的任何函数都不同，因此我认为这不是一个公平的比较（在这一点上）。 - eddi
3
你可以尝试这样做：f8 <- function(x) data.frame(x = sort(unique(x)), freq = tabulate(x))1，它的速度比其他给出的解决方案都要快。此外，我们有 all.equal(f5(x), f8(x), check.attributes = FALSE) 等于 TRUE。 - dickoa
2
@eddi tabulate并没有将结果过滤为仅出现在向量中的整数，我想这就是原因。 - joran
@joran，+ 它只考虑从1到N（N = max(x)）的数字。 - Arun
@Ferdinand.kraft 我认为在那一点上它比data.table更慢了，因为纯tabulate(factor(x))似乎已经与data.table差不多了，但如果有人编写正确的函数进行比较将会很有趣；实际上对于x=sample(1:100, 1e6, T)，tabulate(factor(x))明显较慢。 - eddi
显示剩余2条评论
14

这比tabulate稍微慢一些，但更加通用（它可以处理字符、因子，基本上无论你想要处理什么类型的数据都可以），而且更易于阅读/维护/扩展。

library(data.table)

f6 = function(x) {
  data.table(x)[, .N, keyby = x]
}

x <- sample(1:1000, size=1e7, TRUE)
system.time(f6(x))
#   user  system elapsed 
#   0.80    0.07    0.86 

system.time(f8(x)) # tabulate + dickoa's conversion to data.frame
#   user  system elapsed 
#   0.56    0.04    0.60

更新：截至data.table版本1.9.3，data.table版本实际上比tabulate+data.frame转换快大约2倍。

1
在1e7个向量上，它需要0.97秒。使用“data.table”对向量/矩阵进行操作很难被击败。 - Arun
1
如果你使用普通的 by 而不是 keyby，速度会更快。 - mnel
是的，我正在尝试匹配 f1。 - eddi
1
由于某种原因，data.table 认为 Inf（和 -Inf）与另一个 Inf（或 -Inf）不同。也就是说，如果你有 y <- data.table(a=c(Inf, Inf, -Inf, -Inf))，那么 y[, .N, by=a] 将会给你所有的 1。而 table 则可以正确地处理这个问题。 - Arun
@Arun，你应该提交一个错误报告。 - eddi
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接