如何通过分组加快子集查询速度

Question

我曾使用dplyr进行我的数据处理，但有些计算速度较慢。特别是通过组进行子集操作时，据我所知，当分组数很多时，dplyr 的运算速度较慢。根据这个基准测试，data.table可能更快，因此我开始学习 data.table。

以下是如何使用250k行和约230k个组的真实数据的近似重现方法：我想按id1、id2进行分组，并对每个组中max(datetime)的行进行子集操作。

数据

# random datetime generation function by Dirk Eddelbuettel
# https://dev59.com/62Uq5IYBdhLWcg3wMNYK
rand.datetime <- function(N, st = "2012/01/01", et = "2015/08/05") {
  st <- as.POSIXct(as.Date(st))
  et <- as.POSIXct(as.Date(et))
  dt <- as.numeric(difftime(et,st,unit="sec"))
  ev <- sort(runif(N, 0, dt))
  rt <- st + ev
}

set.seed(42)
# Creating 230000 ids couples
ids <- data.frame(id1 = stringi::stri_rand_strings(23e4, 9, pattern = "[0-9]"), 
                  id2 = stringi::stri_rand_strings(23e4, 9, pattern = "[0-9]"))
# Repeating randomly the ids[1:2000, ] to create groups
ids <- rbind(ids, ids[sample(1:2000, 20000, replace = TRUE), ])
# Adding random datetime variable and dummy variables to reproduce real datas
datas <- transform(ids, 
                   datetime = rand.datetime(25e4), 
                   var1 = sample(LETTERS[1:6], 25e4, rep = TRUE), 
                   var2 = sample(c(1:10, NA), 25e4, rep = TRUE), 
                   var3 = sample(c(1:10, NA), 25e4, rep = TRUE), 
                   var4 = rand.datetime(25e4), 
                   var5 = rand.datetime(25e4))

datas.tbl <- tbl_df(datas)
datas.dt <- data.table(datas, key = c("id1", "id2"))

我在使用data.table时找不到直接按组进行子集操作的方法，因此我提出了这个问题：Filter rows by groups with data.table

他们建议我使用.SD：

datas.dt[, .SD[datetime == max(datetime)], by = c("id1", "id2")]

但是我有两个问题，它可以处理日期但不能处理POSIXct ("Error in UseMethod("as.data.table") : no applicable method for 'as.data.table' applied to an object of class "c('POSIXct', 'POSIXt')""), 而且这很慢。例如，对于日期：

> system.time({
+   datas.dt[, .SD[as.Date(datetime) == max(as.Date(datetime))], by = c("id1", "id2")]
+ })
 utilisateur     système      écoulé 
      207.03        0.00      207.48 

所以我找到了使用data.table更快地实现此操作的其他方法，并保留了日期时间：

函数

f.dplyr <- function(x) x %>% group_by(id1, id2) %>% filter(datetime == max(datetime))
f.dt.i <- function(x) x[x[, .I[datetime == max(datetime)], by = c("id1", "id2")]$V1]
f.dt <- function(x) x[x[, datetime == max(datetime), by = c("id1", "id2")]$V1]

但是我认为data.table会更快，与dplyr相比的时间差异不显著。

微基准测试

mbm <- microbenchmark(
  dplyr = res1 <- f.dplyr(datas.tbl), 
  data.table.I = res2 <- f.dt.i(datas.dt), 
  data.table = res3 <- f.dt(datas.dt), 
  times = 50L)

Unit: seconds
         expr      min       lq     mean   median       uq      max neval
        dplyr 31.84249 32.24055 32.59046 32.61311 32.88703 33.54226    50
 data.table.I 30.02831 30.94621 31.19660 31.17820 31.42888 32.16521    50
   data.table 30.28923 30.84212 31.09749 31.04851 31.40432 31.96351    50

我在使用 data.table 时错过/误用了什么吗？你有什么想法可以加速这个计算吗？

非常感谢您的任何帮助！谢谢

---

编辑：关于微基准测试所使用的系统和软件包版本的一些详细说明。（电脑不是战争机器，12Go i5）

系统

sessionInfo()
R version 3.1.3 (2015-03-09)
Platform: x86_64-w64-mingw32/x64 (64-bit)
Running under: Windows 7 x64 (build 7601) Service Pack 1

locale:
  [1] LC_COLLATE=French_France.1252  LC_CTYPE=French_France.1252   
[3] LC_MONETARY=French_France.1252 LC_NUMERIC=C                  
[5] LC_TIME=French_France.1252    

attached base packages:
  [1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
  [1] readr_0.1.0          ggplot2_1.0.1        microbenchmark_1.4-2
[4] data.table_1.9.4     dplyr_0.4.1          plyr_1.8.2          

loaded via a namespace (and not attached):
  [1] assertthat_0.1   chron_2.3-45     colorspace_1.2-6 DBI_0.3.1       
[5] digest_0.6.8     grid_3.1.3       gtable_0.1.2     lazyeval_0.1.10 
[9] magrittr_1.5     MASS_7.3-39      munsell_0.4.2    parallel_3.1.3  
[13] proto_0.3-10     Rcpp_0.11.5      reshape2_1.4.1   scales_0.2.4    
[17] stringi_0.4-1    stringr_0.6.2    tools_3.1.3 

> packageVersion("data.table")
[1] ‘1.9.4’
> packageVersion("dplyr")
[1] ‘0.4.1’

- Julien Navarre

---

你想获取所有等于最大值的数值，还是只想获取像 which.max 返回的第一个值？另外，datas.dt[, .SD[as.Date(datetime) == max(as.Date(datetime))], by = c("id1", "id2")] 是一种不好的做法。在子集化之前，你应该将 date 转换为 IDate 类型。 - David Arenburg

只是为了好玩，你能在比较中加入 x %>% group_by(id1, id2) %>% slice(which(datetime == max(datetime))) 吗？ - talat

此外，datas.dt[, datetime := as.IDate(datetime)] ; system.time(datas.dt[datas.dt[, .I[datetime == max(datetime)], by = c("id1", "id2")]$V1]) 只需要 5 秒钟就能运行完毕，而使用 .SD 则需要 200 秒钟，因此我很难相信你的基准测试结果。 - David Arenburg

@DavidArenburg，恭喜你，虽然那不是我想要的比较..无论如何，我只是出于好奇而问。 - talat

@docendodiscimus，我并没有吹嘘什么，所以不确定你在为什么事情祝贺我。OP正在寻找一个data.table的解决方案，因为他认为它比dplyr更快-这就是为什么我会将你的提议与data.table进行比较，以防他的假设是错误的。 - David Arenburg

Answer 1

好问题！

我将假设df和dt是对象的名称，以便更轻松、更快速地输入。

df = datas.tbl
dt = datas.dt

在-O3级别优化比较：

首先，这是在我的系统上对当前CRAN版本的 dplyr 和 data.table 的开发版本进行测试的时间。开发版本的 dplyr 似乎存在性能退化问题（正在由 Romain 进行修复）。

system.time(df %>% group_by(id1, id2) %>% filter(datetime == max(datetime)))
#  25.291   0.128  25.610 

system.time(dt[dt[, .I[datetime == max(datetime)], by = c("id1", "id2")]$V1])
#  17.191   0.075  17.349 

我运行了这个程序多次，但好像没有变化。不过，我使用-O3优化标志编译了所有软件包(通过适当设置~/.R/Makevars)。我观察到与其他软件包相比，在-O3下，data.table 的性能要好得多。

分组速度比较

其次，重要的是要了解这种缓慢的原因。首先让我们比较一下只进行分组所需的时间。

system.time(group_by(df, id1, id2))
#   0.303   0.007   0.311 
system.time(data.table:::forderv(dt, by = c("id1", "id2"), retGrp = TRUE))
#   0.002   0.000   0.002 

尽管您的数据总共有250,000行，但其大小约为~38MB。在这种大小下，分组速度的差异不太可能明显。

data.table在此处的分组速度比普通方法快>100倍，很明显这不是速度缓慢的原因……

为什么速度慢？

那么是什么原因导致了速度缓慢？让我们打开datatable.verbose选项再次检查：

options(datatable.verbose = TRUE)
dt[dt[, .I[datetime == max(datetime)], by = c("id1", "id2")]$V1]
# Detected that j uses these columns: datetime 
# Finding groups (bysameorder=TRUE) ... done in 0.002secs. bysameorder=TRUE and o__ is length 0
# lapply optimization is on, j unchanged as '.I[datetime == max(datetime)]'
# GForce is on, left j unchanged
# Old mean optimization is on, left j unchanged.
# Starting dogroups ... 
#   memcpy contiguous groups took 0.097s for 230000 groups
#   eval(j) took 17.129s for 230000 calls
# done dogroups in 17.597 secs

所以eval(j)单独占用了约97％的时间！我们在j中提供的表达式将对每个组进行求值。由于您有230,000个组，并且在eval()调用中存在惩罚，因此总和增加了。

避免eval()惩罚

由于我们意识到这种惩罚，因此我们已经开始实施一些常用函数的内部版本：sum，mean，min，max。这将/应该扩展到尽可能多的其他函数（当我们有时间时）。

因此，让我们先尝试计算仅获取max(datetime)所需的时间：

dt.agg = dt[, .(datetime = max(datetime)), by = .(id1, id2)]
# Detected that j uses these columns: datetime 
# Finding groups (bysameorder=TRUE) ... done in 0.002secs. bysameorder=TRUE and o__ is length 0
# lapply optimization is on, j unchanged as 'list(max(datetime))'
# GForce optimized j to 'list(gmax(datetime))'

而且它是即时的。为什么呢？因为max()会在内部被优化为gmax()，并且对于这230K个组没有eval()调用。

那么为什么datetime == max(datetime)不是即时的呢？因为解析这样的表达式并进行内部优化更加复杂，并且我们还没有解决它。

解决方法

既然现在我们知道了问题所在，以及一个绕开它的方法，那么让我们来使用它吧。

dt.agg = dt[, .(datetime = max(datetime)), by = .(id1, id2)]
dt[dt.agg, on = c("id1", "id2", "datetime")] # v1.9.5+

在我的 Mac 上，这需要大约 0.14 秒的时间。

请注意，这之所以很快，是因为该表达式被优化为 gmax()。与以下代码进行比较：

dt[, .(datetime = base::max(datetime)), by = .(id1, id2)]

我同意优化更复杂的表达式以避免使用eval()带来的惩罚是理想的解决方案，但我们还没有做到。

- Arun

---

感谢您这个启发性的回答。您不仅给了我将执行时间除以100的解决方案，还帮助我深入理解了计算中的瓶颈！非常感谢。 - Julien Navarre

Answer 2

如何对 data.table 进行汇总并 join 原始数据呢？

system.time({
  datas1 <- datas.dt[, list(datetime=max(datetime)), by = c("id1", "id2")] #summarize the data
  setkey(datas1, id1, id2, datetime)
  setkey(datas.dt, id1, id2, datetime)
  datas2 <- datas.dt[datas1]
})
#  user  system elapsed 
# 0.083   0.000   0.084 

正确过滤数据的方法

system.time(dat1 <- datas.dt[datas.dt[, .I[datetime == max(datetime)], by = c("id1", "id2")]$V1])
#   user  system elapsed 
# 23.226   0.000  23.256 
all.equal(dat1, datas2)
# [1] TRUE

补充说明

如果您正在使用data.table的开发版本，则setkey参数是多余的（感谢@akrun指出）。

system.time({
  datas1 <- datas.dt[, list(datetime=max(datetime)), by = c("id1", "id2")] #summarize the data
  datas2 <- datas.dt[datas1, on=c('id1', 'id2', 'datetime')]
})

- Khashaa

---

在开发版本中，您不需要使用 setkey。datas.dt[datas1, on=c('id1', 'id2')] 应该可以工作，尽管没有进行时间测试。 - akrun

@akrun，谢谢。我对data.table的细节一无所知。 - Khashaa

你应该保留两个版本，因为你的编辑只适用于开发版本。 - David Arenburg

@akrun，是的，这是一个未解决的问题在GH上。这是我认为我们应该保留两个选项的另一个原因。顺便说一下，很好的解决方案Kashaa，你可能重新定义了这些任务的规范解决方案，而不是这个。 - David Arenburg

@Khashaa 看看这个答案。我认为我已经解释得很清楚了。虽然根据Arun的精彩回答，我开始怀疑这个解决方案是否适用于所有函数，而不仅仅是sum、mean、min和max。 - David Arenburg