Производительность групповых операций с data.table

Начну с описания задачи, которую я выполняю. Мне приходится неоднократно вычислять сгруппированную сумму, обычно от 5 до 10 раз. Значения в столбце, по которому я выполняю сгруппированную сумму, изменяются с каждой итерацией, а столбцы, по которым я группирую, - нет. Ниже приведен пример таблицы, в которой w, x и y вместе составляют группу, а z — это столбец, значения которого будут суммироваться.

DT <- data.table(w = sample(1:10, size  = 1000000, replace = TRUE), 
                 x = sample(1:100, size  = 1000000, replace = TRUE), 
                 y = sample(1:1000, size  = 1000000, replace = TRUE),
                 z = runif(n = 1000000, min = 0, max = 1))

setkey(DT, w, x, y)

Мое первоначальное решение было, я думаю, самым очевидным:

DT[, Group_Total := sum(z), keyby = list(w, x, y)]

microbenchmark(DT[, Group_Total := sum(z), keyby = list(w, x, y)])
Unit: milliseconds
min       lq        mean      median    uq        max  neval
447.8674  467.3366  481.1989  479.3057  490.5499  691  100

Я обнаружил, что это решение не так быстро, как я надеялся, тем более, что мне пришлось выполнять это вычисление несколько раз. Однако, насколько я мог судить, в data.table не было метода, обеспечивающего лучшую производительность, чем этот. Недавно я начал экспериментировать с Rccp и написал следующую функцию для выполнения групповой суммы:

cppFunction('NumericVector Group_Total(NumericVector Grouping, NumericVector x) {
                          
                          int n = Grouping.size();
                          NumericVector out(n);
                          
                          int curr_start_index = 0;
                          double grp_total = x[0];
                          
                          for(int i = 1; i < (n-1); ++i) {
                          
                            if(Grouping[i] == 1) {
                            
                              for(int j = curr_start_index; j < i; ++j) {
                              
                                out[j] = grp_total;  
                              
                              }
                              
                              curr_start_index = i;
                              grp_total = x[i];
                              
                            } else {
                              
                                grp_total = grp_total + x[i];
                              
                              } 
                              
                            }
                            
                          if(Grouping[(n-1)] == 1) {
                              
                              for(int j = curr_start_index; j < (n-1); ++j) {
                              
                                out[j] = grp_total;  
                              
                              }
                              
                              out[(n-1)] = x[(n-1)];
                                
                            } else {
                              
                                grp_total = grp_total + x[(n-1)];
                                
                                for(int j = curr_start_index; j < n; ++j) {
                                  
                                  out[j] = grp_total;  
                              
                                }
                              
                            }
                              
                        return out;
              }')

Чтобы использовать эту функцию, я вычисляю столбец индекса внутри группы после того, как данные упорядочены:

DT[, Within_Group_Index := 1][, Within_Group_Index := cumsum(Within_Group_Index), keyby = list(w, x, y)]

Поскольку мне нужно вычислить этот столбец только один раз, добавленное время не имеет значения. После создания этого столбца сгруппированную сумму можно рассчитать с помощью:

DT[, Group_Total := Group_Total(Within_Group_Index, z)]

microbenchmark(DT[, Group_Total := Group_Total(Within_Group_Index, z)])
Unit: milliseconds
min     lq      mean      median  uq      max       neval
5.3286  6.9879  9.078267  7.4814  8.0171  161.6406  100

Это быстрее со значительным отрывом, и теперь мы подходим к моему вопросу: почему? Насколько я понимаю, сгруппированные операции очень эффективны в data.table. Есть ли что-то, что я могу сделать, чтобы ускорить сгруппированную операцию data.table, или это пример фундаментального компромисса скорости и гибкости, т.е. гибкость сгруппированных операций data.table достигается за счет скорости при рассмотрении конкретного использования случаи?

3 метода стилизации элементов HTML
3 метода стилизации элементов HTML
Когда дело доходит до применения какого-либо стиля к нашему HTML, существует три подхода: встроенный, внутренний и внешний. Предпочтительным обычно...
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
5
0
94
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Я думаю, что ваше подозрение верно. Относительно того, почему, мы могли бы сделать обоснованное предположение.

Обновлено: приведенная ниже информация игнорирует то, что data.table делает с оптимизацией GForce, функции, поддерживаемые GForce, вероятно, избегают копий данных, подобных вашему коду C++, но, как упоминал Фрэнк, := не пытался обнаружить оптимизированные для GForce выражения до версии 1.14.3, и addrs ниже, конечно, не оптимизировано GForce.

Написанный вами код C++ ничего не изменяет в своих данных вход, он должен только выделить out. Как вы правильно сказали, data.table стремится быть более гибким, и должен поддерживать любой допустимый код R, предоставленный пользователями. Это заставляет меня думать, что, для групповых операций, ему пришлось бы выделять новые векторы R для каждого подмножества z в соответствии с групповыми индексами, эффективное копирование некоторых входных данных несколько раз.

Я хотел попытаться подтвердить свое предположение, поэтому я написал код C++ для просмотра адресов памяти:

set.seed(31L)
DT <- data.table(w = sample(1:3, size  = 20, replace = TRUE), 
                 x = sample(1:3, size  = 20, replace = TRUE), 
                 y = sample(1:3, size  = 20, replace = TRUE),
                 z = runif(n = 20, min = 0, max = 1))

setkey(DT, w, x, y)

cppFunction(plugins = "cpp11", includes = "#include <sstream>", '
    StringVector addrs(NumericVector z, IntegerVector indices, IntegerVector group_ids) {
        StringVector ans(indices.size());
        for (auto i = 0; i < indices.size(); ++i) {
            std::ostringstream oss;
            oss << "Group" << group_ids[i] << " " << &z[indices[i]];
            ans[i] = oss.str();
        }
        return ans;
    }
')

idx <- DT[, .(indices = .I[1L] - 1L, group_ids = .GRP), keyby = list(w, x, y)]

DT[, list(addrs(z, idx$indices, idx$group_ids))]
#                         V1
#  1:  Group1 0x55b7733361f8
#  2:  Group2 0x55b773336200
#  3:  Group3 0x55b773336210
#  4:  Group4 0x55b773336220
#  5:  Group5 0x55b773336228
#  6:  Group6 0x55b773336230
#  7:  Group7 0x55b773336238
#  8:  Group8 0x55b773336248
#  9:  Group9 0x55b773336250
# 10: Group10 0x55b773336258
# 11: Group11 0x55b773336260
# 12: Group12 0x55b773336270
# 13: Group13 0x55b773336280
# 14: Group14 0x55b773336288
# 15: Group15 0x55b773336290

Как и ожидалось здесь, если мы посмотрим на z в целом, копирование не происходит и адреса разных элементов близки друг к другу, например 0x55b773336200 = 0x55b7733361f8 + 0x8. Вы можете выполнить последнюю строку из предыдущего кода несколько раз, и она всегда будет показывать одни и те же адреса.

Чего я частично не ожидал, так это:

DT[, list(addrs(z, 0L, .GRP)), keyby = list(w, x, y)]
#     w x y                     V1
#  1: 1 1 2  Group1 0x55b771b03440
#  2: 1 1 3  Group2 0x55b771b03440
#  3: 1 2 1  Group3 0x55b771b03440
#  4: 1 2 2  Group4 0x55b771b03440
#  5: 1 3 2  Group5 0x55b771b03440
#  6: 1 3 3  Group6 0x55b771b03440
#  7: 2 1 1  Group7 0x55b771b03440
#  8: 2 2 1  Group8 0x55b771b03440
#  9: 2 2 2  Group9 0x55b771b03440
# 10: 2 2 3 Group10 0x55b771b03440
# 11: 2 3 1 Group11 0x55b771b03440
# 12: 3 2 1 Group12 0x55b771b03440
# 13: 3 2 2 Group13 0x55b771b03440
# 14: 3 2 3 Group14 0x55b771b03440
# 15: 3 3 3 Group15 0x55b771b03440

С одной стороны, адрес в памяти изменился, значит что-то скопировано и если вы запустите это несколько раз, вы каждый раз будете видеть разные адреса. Однако похоже, что data.table каким-то образом повторно использует буфер с тем же адресом, может быть, выделить один массив с длиной наибольшего подмножества группы и скопировать в него разные значения группы? Интересно, как они это умудряются. Или, может быть, мой код неверен ¯\_(ツ)_/¯

Обновлено: я добавил следующее в качестве первой строки addrs (двойной выход из-за синтаксического анализа R)

Rcout << "input length = " << z.size() << "\\n";

и если я запущу последний код DT[...] сверху, он печатает разную длину, даже если адрес тот же.

Может FAQ 3.1 поможет объяснить? «Одно выделение памяти производится только для самой большой группы, затем эта память повторно используется для других групп. Мусора для сбора очень мало».

Frank 23.04.2022 04:34

Интересно, что они избегают множественных выделений, но все же должны копировать некоторые данные. Теперь мне интересно, как именно они оптимизировали это в 1.14.3.

Alexis 23.04.2022 10:22

Я обнаружил, что первоначальный код был быстрее в ветке разработки версии 1.14.3. Из Новости:

  1. := is now optimized by group

Я считаю, что это применимо везде, где работает GForce. Смотрите ?GForce. (Спасибо, что указали на это @Alexis)

Я видел время, похожее на ваше, но после обновления вижу, что исходный код работает довольно быстро:

microbenchmark(
    direct = DT[, Group_Total := sum(z), keyby = list(w, x, y)],
    indirect = DT[, idx := rowid(w,x,y)][, gt := Group_Total(idx, z)]
)

Unit: milliseconds
     expr      min       lq     mean   median       uq      max neval
   direct 42.92247 44.61097 48.77803 45.48076 46.93751 72.29237   100
 indirect 30.49422 31.95343 34.69138 33.18616 35.32934 58.37454   100

Примечания:

  • rowid строит внутригрупповой индекс.
  • DT[, Group_Total := sum(z), keyby = list(w, x, y), verbose=TRUE] отобразит информацию о том, используется ли оптимизация GForce.

Если я правильно понял, они могли бы быть более конкретными, я думаю, что := теперь также определяет операции, которые могут быть оптимизированы для GForce, что-то вроде sum(diff(z)), вероятно, не будет оптимизировано.

Alexis 23.04.2022 13:48

Спасибо @Alexis, я отредактировал, чтобы отметить это здесь, да, я предполагаю, что это имелось в виду; и новость могла бы быть яснее.

Frank 25.04.2022 09:09

Другие вопросы по теме