Как ускорить подмножество по группам

Раньше я использовал данные dortr, но некоторые из них были "медленными". В частности, подмножество по группам, я читал, что dplyr медленный, когда есть много групп и на основе этот тест data.table может быть быстрее поэтому я начал изучать data.table.

Вот как воспроизвести что-то близкое к моим реальным данным с 250 тыс. строк и около 230 тыс. групп. Я хотел бы сгруппировать по id1, id2 и подмножество строк с max(datetime) для каждой группы.

Данные

# random datetime generation function by Dirk Eddelbuettel
# https://stackoverflow.com/info/14720983/efficiently-generate-a-random-sample-of-times-and-dates-between-two-dates
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, поэтому я задал этот вопрос: Фильтровать строки по группам с помощью data.table

Мы предлагаем мне использовать .SD:

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

Но у меня две проблемы: она работает с датой, но не с POSIXct ( "Ошибка в UseMethod (" as.data.table "): не применимый метод для" as.data.table ", примененный к объекту класса" 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 не является значимой.

Microbenchmark

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’

Ответ 1

Отличный вопрос!

Я предполагаю, что df и dt будут именами объектов для легкой/быстрой печати.

df = datas.tbl
dt = datas.dt

Сравнение при оптимизации уровня -O3:

Во-первых, здесь время в моей системе на текущей версии CRAN dplyr и версии версии data.table. Версия devel 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 соответственно). И я заметил, что производительность data.table намного лучше, чем в других пакетах, которые я сравнивал с помощью -O3.

Сравнение скорости группировки

Во-вторых, важно понять причину такой медлительности. Сначала сравните время, чтобы просто сгруппировать.

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 строк, размер ваших данных составляет около ~ 38 МБ. При таком размере вряд ли заметна разница в скорости группировки.

data.table здесь >100x быстрее, это явно не причина такой медленности...

Почему это медленно?

И какая причина? Включите опцию 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() и нет вызова eval() для каждой из 230K групп.

Итак, почему не datetime == max(datetime) мгновенный? Потому что более сложно разобрать такие выражения и оптимизировать внутренне, и мы еще не дошли до него.

Обход

Итак, теперь, когда мы знаем проблему и способ обойти ее, давайте ее использовать.

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

Это занимает около 0,14 секунды на моем Mac.

Обратите внимание, что это происходит только быстро, потому что выражение оптимизируется до gmax(). Сравните это с:

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

Я согласен оптимизировать более сложные выражения, чтобы избежать штрафа eval(), было бы идеальным решением, но мы еще не находимся.

Ответ 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

Добавление

Аргумент

setkey лишний, если вы используете версию devel data.table (Спасибо @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')]
})