Какова цель установки ключа в data.table?

Я использую data.table, и есть много функций, которые требуют от меня установки ключа (например X[Y]). Таким образом, я хочу понять, что делает ключ, чтобы правильно устанавливать ключи в моих таблицах данных.

Я прочитал один источник ?setkey.

setkey()сортирует data.tableи отмечает его как отсортированный. Отсортированные столбцы - это ключ. Ключом могут быть любые столбцы в любом порядке. Столбцы всегда отсортированы по возрастанию. Таблица изменена по ссылке. Никаких копий не производится, кроме временной рабочей памяти размером в один столбец.

Мой вывод заключается в том, что ключ будет «сортировать» data.table, что дает эффект, очень похожий на order(). Однако это не объясняет, зачем нужен ключ.

В FAQ 3.2 и 3.3 data.table объясняется:

3.2 У меня нет ключа на большом столе, но группировка по-прежнему очень быстрая. Это почему?

data.table использует сортировку по основанию. Это значительно быстрее, чем другие алгоритмы сортировки. Radix предназначен только для целых чисел, см ?base::sort.list(x,method="radix"). Это также одна из причин, почему setkey()это быстро. Когда ключ не задан или мы группируем в порядке, отличном от порядка ключа, мы называем это специальным путем.

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

Поскольку каждая группа является смежной в ОЗУ, тем самым сводя к минимуму выборку страниц, а память можно копировать массово ( memcpyв C), а не зацикливаться в C.

Отсюда я предполагаю, что установка ключа каким-то образом позволяет R использовать "поразрядную сортировку" по сравнению с другими алгоритмами, и поэтому это быстрее.

В 10-минутном кратком руководстве также есть руководство по клавишам.

1. Ключи

Начнем с рассмотрения data.frame, в частности имен строк (или, по-английски, имен строк). То есть несколько имен, принадлежащих одной строке. Несколько имен, принадлежащих одной строке? Это не то, к чему мы привыкли в data.frame. Мы знаем, что каждая строка имеет не более одного имени. У человека есть как минимум два имени: первое и второе. Это полезно, например, для организации телефонного справочника, который отсортирован по фамилии, затем по имени. Однако каждая строка в data.frame может иметь только одно имя.

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

Уникальность не гарантируется, т. Е. Разрешены повторяющиеся значения ключей. Поскольку строки сортируются по ключу, любые дубликаты в ключе будут отображаться последовательно.

Телефонный справочник помог понять, что такое ключ, но кажется, что ключ ничем не отличается от столбца факторов. Кроме того, он не объясняет, зачем нужен ключ (особенно для использования определенных функций) и как выбрать столбец для установки в качестве ключа. Кроме того, кажется, что в data.table со временем в качестве столбца установка любого другого столбца в качестве ключа, вероятно, также испортит столбец времени, что делает его еще более запутанным, поскольку я не знаю, разрешено ли мне установить любой другой столбец как ключ. Может кто-нибудь просветите меня, пожалуйста?

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

Я снова обновил этот ответ (февраль 2016 г.) в свете новой on=функции, которая также позволяет выполнять специальные соединения. Более ранние (устаревшие) ответы см. В истории.

Что именно делает setkey(DT, a, b) ?

Он делает две вещи:

1. переупорядочивает строки таблицы data.table DT по столбцам, предоставленным ( a , b ) по ссылке , всегда в порядке возрастания .
2. знаки этих столбцов в качестве ключевых столбцов, установив атрибут , называемый sortedв DT.

Переупорядочение происходит быстро (благодаря внутренней сортировке по основанию data.table ) и эффективно с точки зрения памяти (только один дополнительный столбец типа double выделяется ).

Когда setkey() требуется?

Для операций группировки setkey()это никогда не было абсолютным требованием. То есть мы можем выполнить холодный обход или обходной путь .

## "cold" by
require(data.table)
DT <- data.table(x=rep(1:5, each=2), y=1:10)
DT[, mean(y), by=x] # no key is set, order of groups preserved in result

Однако до v1.9.6этого x[i]необходимо keyбыло установить соединения формы x. С новым on=аргументом из v1.9.6 + это больше не верно, и поэтому установка ключей здесь также не является абсолютным требованием.

## joins using < v1.9.6 
setkey(X, a) # absolutely required
setkey(Y, a) # not absolutely required as long as 'a' is the first column
X[Y]

## joins using v1.9.6+
X[Y, on="a"]
# or if the column names are x_a and y_a respectively
X[Y, on=c("x_a" = "y_a")]

Обратите внимание, что on=аргумент может быть явно указан даже для keyedобъединений.

Единственная операция, которая требует keyабсолютной настройки, - это функция foverlaps () . Но мы работаем над еще некоторыми функциями, которые, когда будут готовы, устранят это требование.

• Так в чем же причина on=аргументации?

  Причин довольно много.

  1. Это позволяет четко различать операцию как операцию с двумя таблицами data.tables . Простое выполнение X[Y]также не различает этого, хотя это можно понять, если присвоить переменным соответствующее имя.

  2. Это также позволяет сразу понять столбцы, в которых выполняется объединение / подмножество , путем просмотра этой строки кода (без необходимости отслеживания соответствующей setkey()строки).

  3. В операциях, в которых столбцы добавляются или обновляются по ссылке , on=операции намного более производительны, поскольку не нужно переупорядочивать всю таблицу data.table только для добавления / обновления столбца (столбцов). Например,

     ## compare 
     setkey(X, a, b) # why physically reorder X to just add/update a column?
     X[Y, col := i.val]
     
     ## to
     X[Y, col := i.val, on=c("a", "b")]

     Во втором случае заказывать заново не пришлось. Это не вычисление порядка, что отнимает много времени, а физическое изменение порядка таблицы data.table в ОЗУ, и, избегая этого, мы сохраняем исходный порядок, и он также является эффективным.

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

Это приводит к вопросу, какое преимущество имеет ввод data.table ?

• Есть ли преимущество в использовании таблицы data.table?

  Ключ data.table физически меняет ее порядок на основе этих столбцов в ОЗУ. Вычисление заказа обычно не занимает много времени, это скорее повторный заказ. . Однако после того, как мы отсортировали данные в ОЗУ, все строки, принадлежащие к одной группе, будут непрерывными в ОЗУ и, следовательно, очень эффективны в кешировании. Именно отсортированность ускоряет операции с ключевыми данными data.tables.

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

Поэтому в большинстве случаев больше не нужно устанавливать ключи. Мы рекомендуем использовать on=везде, где это возможно, если только установка ключа не приводит к значительному повышению производительности, которое вы хотели бы использовать.

Вопрос: Как вы думаете, какой будет производительность по сравнению с ключевым соединением, если вы используете setorder()для изменения порядка data.table и используете on=? Если вы следили за этим до сих пор, вы сможете понять это :-).

Ключ - это, по сути, индекс в наборе данных, который позволяет очень быстро и эффективно выполнять операции сортировки, фильтрации и объединения. Вероятно, это лучшие причины использовать таблицы данных вместо фреймов данных (синтаксис для использования таблиц данных также намного удобнее для пользователя, но это не имеет ничего общего с ключами).

Если вы не разбираетесь в индексах, учтите следующее: телефонная книга «индексируется» по имени. Так что если я хочу найти чей-то номер телефона, это довольно просто. Но предположим, что я хочу выполнить поиск по номеру телефона (например, найти, у кого есть конкретный номер телефона)? Если я не смогу «переиндексировать» телефонную книгу по номеру телефона, это займет очень много времени.

Рассмотрим следующий пример: предположим, у меня есть таблица ZIP всех почтовых индексов в США (> 33 000) вместе со связанной информацией (город, штат, население, средний доход и т. Д.). Если я хочу найти информацию по определенному почтовому индексу, поиск (фильтр) будет примерно в 1000 раз быстрее, если яsetkey(ZIP,zipcode) сначала.

Еще одно преимущество связано с объединениями. Предположим, у вас есть список людей и их почтовые индексы в таблице данных (назовите ее «PPL»), и я хочу добавить информацию из почтовой таблицы (например, город, штат и т. Д.). Следующий код сделает это:

setkey(ZIP,zipcode)
setkey(PPL,zipcode)
full.info <- PPL[ZIP, nomatch=F]

Это «соединение» в том смысле, что я объединяю информацию из двух таблиц в общем поле (почтовый индекс). Подобные соединения в очень больших таблицах выполняются очень медленно с фреймами данных и очень быстрыми с таблицами данных. В реальном примере мне пришлось сделать более 20 000 таких соединений на полной таблице почтовых индексов. С таблицами данных скрипт занял около 20 минут. бежать. Я даже не пробовал это с фреймами данных, потому что это заняло бы больше 2 недель.

ИМХО нужно не просто читать, а изучать FAQ и вводный материал. Это легче понять, если у вас есть реальная проблема, к которой можно применить это.

[Ответ на комментарий @Frank]

Re: сортировка против индексации. Основываясь на ответе на этот вопрос , выяснилось, что setkey(...)на самом деле столбцы в таблице меняются (например, физическая сортировка) и не создается индекс в смысле базы данных. Это имеет некоторые практические последствия: с одной стороны, если вы установите ключ в таблице с помощью, setkey(...)а затем измените любое из значений в ключевом столбце, data.table просто объявляет, что таблица больше не сортируется (путем отключения sortedатрибута); он делает не динамически повторно индекса для поддержания надлежащего порядка сортировки (как произошло бы в базе данных). Кроме того , «вынув ключ» , используя setky(DT,NULL)это не восстановить таблицу в исходном, отсортированный порядок.

Re: фильтр или соединение - практическая разница в том, что фильтрация извлекает подмножество из одного набора данных, тогда как соединение объединяет данные из двух наборов данных на основе общего поля. Есть много разных видов соединения (внутреннее, внешнее, левое). Приведенный выше пример представляет собой внутреннее соединение (возвращаются только записи с ключами, общими для обеих таблиц), и это имеет много общего с фильтрацией.