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

Question

Я использовал для достижения своих данных перебор с dplyr, но некоторые из вычислений являются «медленными». В частности, подмножество по группам, я читал, что dplyr медленный, когда есть много групп, и на основе данных this benchmark.table может быть быстрее, поэтому я начал изучать data.table.

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

Datas

# random datetime generation function by Dirk Eddelbuettel 
# https://stackoverflow.com/questions/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 поэтому я задал этот вопрос: Filter rows by groups with 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 

Так что я нашел другой путь гораздо быстрее, чтобы достичь этого (и сохраняя DateTimes) с 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] 

Но тогда я думал, что данные. таблица будет намного быстрее, разница во времени с 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’ 

Answer 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.

скорость Группировка сравнение

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

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 «S является >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() наказания было бы идеальным решением, но мы не там еще.

Answer 2

Как насчет обобщения данных.стол и 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 version в 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')] 
})