Есть ли наглядное объяснение того, почему операции data.table быстрее, чем операции tidyverse, когда вам нужно сгруппировать по переменной?

Question

Я понимаю из превосходных ресурсов здесь , здесь и здесь , что data.table использует автоматическое индексирование c (для создания key, то есть с наддувом имена строк) и подмножество бинарного поиска в отличие от tidyverse, которое опирается на векторное сканирование.

Я понимаю, что векторное сканирование требует сканирования каждой отдельной строки и создания логических векторов длиной nrow(dataset), и что повторять это не так эффективно.

Мне интересно, может ли кто-нибудь помочь мне точно сформулировать, как эти два метода означают, что data.table операции выполняются намного быстрее по сравнению с tidyverse, когда вам нужно сгруппировать по переменной. То есть это потому, что data.table автоматически индексирует столбец group_by и разбивает его на сгруппированные подмножества и выполняет операции для каждого подмножества, в то время как метод векторного сканирования потребует генерации n = unique groups нескольких логических векторов, а затем запускает операции на каждый отдельный логический вектор, перед сопоставлением результатов?

Кроме того, согласно data.table виньетка ,

Мы можем установить ключи в нескольких столбцах, причем столбцы могут быть разных типов ...

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

Что означает, что мы можем установить ключи для нескольких столбцов, и все же data.table может иметь не более одного ключа? Т.е. в любой момент при выполнении операции есть только один ссылочный ключ, но в каком столбце задан ссылочный ключ, который может измениться, когда мы перейдем к другому компоненту всей операции?

Спасибо за заранее!

Answer 1

Нет.

Существуют разные способы поиска групп, а затем вычисления выражений по группам. Каждая вещь может быть реализована по-разному. Они не связаны с ключами или индексом. Кроме того, data.table не создает автоматически ключ / индекс во время группирования (на данный момент).

data.table имеет очень быструю, тщательно реализованную функцию order, она используется для поиска групп. Это было внесено в базу R позже. Есть идея использовать его в dplyr для ускорения группировки: https://github.com/tidyverse/dplyr/issues/4406
С тех пор функция заказа data.table была улучшена и теперь масштабируется еще лучше.

Помимо Нахождение групп, есть часть о вычислении выражения. Если мы оценим «пользовательскую функцию», она всегда будет намного медленнее. Многие общие функции оптимизированы внутри, поэтому они не переключаются между R и C для каждой группы. Здесь data.table также очень тщательно реализовал функции "GForce". Не уверен, но в dplyr они называются «гибридной оценкой».

Всегда важно протестировать ваш конкретный вариант использования данных. Если у вас есть только 2 уникальные группы в данных, то быстрые алгоритмы группировки не будут особенно хорошими.

Также есть хранилище сообщества, которое предназначено для описания алгоритмов data.table https://github.com/asantucci/algo_data.table, но это не очень активен. Я только недавно разместил там комментарий о «групповой оптимизации», также вставлю его сюда. Ответ предоставлен автором data.table Мэттом Доулом.

В: выделяет ли GForce mem для самой большой группы, а затем копирует туда значения группы для агрегирования, чтобы выиграть от смежности в памяти и будет более эффективным кеш? если так, мы проверяем, не отсортированы ли группы уже? поэтому мы можем избежать выделения и копирования?

A: gforce (gsum) назначает сразу нескольким групповым результатам; это не собирает группы вместе. Вы описываете non-gforce (dogroup. c), который копирует в наибольшую группу. Смотрите ветку по группам собак. c, которая знает, группируются ли уже группы: она переключается на memcpy. Memcpy очень быстрый (непрерывный, предварительный выбор), так что он уже довольно хорош. Мы должны скопировать, потому что DATAPTR R не указатель, который мы можем переписать, это смещение от SEXP.