понедельник, 19 октября 2015 г.

data.table. Ключи и создание поднаборов на основе быстрого бинарного поиска (перевод)


Эта виньетка предназначена для тех, кто уже знаком с синтаксисом data.table, его общим видом, тем, как выбирать строки в i, выбирать и вычислять столбцы, добавлять/изменять/удалять столбцы по ссылке в j и выполнять группировку при помощи by. Если вы не знакомы с этими концепциями, пожалуйста, прочтите сперва виньетки “Введение в data.table” и “Семантика ссылок”.

Данные

Мы будем использовать набор данных flights, так же как в виньетке “Введение в data.table”.
flights <- fread("https://raw.githubusercontent.com/wiki/arunsrinivasan/flights/NYCflights14/flights14.csv")
head(flights)
#    year month day dep_time dep_delay arr_time arr_delay cancelled carrier tailnum flight origin
# 1: 2014     1   1      914        14     1238        13         0      AA  N338AA      1    JFK
# 2: 2014     1   1     1157        -3     1523        13         0      AA  N335AA      3    JFK
# 3: 2014     1   1     1902         2     2224         9         0      AA  N327AA     21    JFK
# 4: 2014     1   1      722        -8     1014       -26         0      AA  N3EHAA     29    LGA
# 5: 2014     1   1     1347         2     1706         1         0      AA  N319AA    117    JFK
# 6: 2014     1   1     1824         4     2145         0         0      AA  N3DEAA    119    EWR
#    dest air_time distance hour min
# 1:  LAX      359     2475    9  14
# 2:  LAX      363     2475   11  57
# 3:  LAX      351     2475   19   2
# 4:  PBI      157     1035    7  22
# 5:  LAX      350     2475   13  47
# 6:  LAX      339     2454   18  24
dim(flights)
# [1] 253316     17

Введение

В этой виньетке мы:
  1. сперва введем понятие ключа key в таблице data.table, а также зададим и используем ключи для создания поднаборов в i на основе быстрого бинарного поиска
  2. увидим, как можно комбинировать создание поднаборов на основе ключей с j и by тем же способом, что и раньше
  3. взглянем на другие полезные аргументы - mult и nomatch
  4. и, в заключение, оценим преимущество использования ключей - выполним создание поднаборов на основе быстрого бинарного поиска и сравним с традиционным подходом, который состоит в сканировании вектора.

1. Ключи

a) Что такое ключ?

В виньетке “Введение в data.table” мы видели, как выбирать поднаборы строк в i при помощи логических выражений, номеров строк и с использованием order(). В этом разделе мы рассмотрим другой способ невероятно быстрого создания поднаборов - при помощи ключей.
Давайте сперва взглянем на таблицы data.frames. Все они имеют атрибут имен строк. Рассмотрим data.frame DF ниже.
set.seed(1L)
DF = data.frame(ID1 = sample(letters[1:2], 10, TRUE), 
                ID2 = sample(1:3, 10, TRUE),
                val = sample(10), 
                stringsAsFactors = FALSE,
                row.names = sample(LETTERS[1:10]))
DF
#   ID1 ID2 val
# C   a   3   5
# D   a   1   6
# E   b   2   4
# G   a   1   2
# B   b   1  10
# H   a   2   8
# I   b   1   9
# F   b   2   1
# J   a   3   7
# A   b   2   3

rownames(DF)
#  [1] "C" "D" "E" "G" "B" "H" "I" "F" "J" "A"
Мы можем выбрать отдельную строку, используя ее имя, как показано ниже:
DF["C", ]
#   ID1 ID2 val
# C   a   3   5
Т.е. имена строк представляют собой (более или менее) индексы строк в таблице data.frame. Однако,
  1. Каждая строка ограничена ровно одним именем.
Но, например, человек имеет имя и фамилию. Телефонный справочник удобно организовать сначала по фамилии, затем по имени.
  1. Кроме того, имена строк должны быть уникальными.
rownames(DF) = sample(LETTERS[1:5], 10, TRUE)
# Warning: non-unique values when setting 'row.names': 'C', 'D'
# Error in `row.names<-.data.frame`(`*tmp*`, value = value): duplicate 'row.names' are not allowed
Теперь давайте сконвертируем эту таблицу в data.table.
DT = as.data.table(DF)
DT
#     ID1 ID2 val
#  1:   a   3   5
#  2:   a   1   6
#  3:   b   2   4
#  4:   a   1   2
#  5:   b   1  10
#  6:   a   2   8
#  7:   b   1   9
#  8:   b   2   1
#  9:   a   3   7
# 10:   b   2   3

rownames(DT)
#  [1] "1"  "2"  "3"  "4"  "5"  "6"  "7"  "8"  "9"  "10"
  • Обратите внимание, что имена строк были удалены.
  • data.tables никогда не используют имена строк. Так как data.tables наследуют data.frames, они по-прежнему имеют атрибут имен строк, но никогда его не используют. Вскоре мы увидим, почему.
Если вы хотите сохранить имена строк, используйте keep.rownames = TRUE в as.data.table() - это создаст новый столбец rn и присвоит ему имена строк.
Вместо этого, в data.tables мы задаем и используем ключи keys. Думайте о них как о “заряженных” именах строк.

Ключи и их свойства

  1. Мы можем устанавливать ключи для множественных столбцов, которые могут иметь разные типы - integer, numeric, character, factor, integer64 и т.д. Списки и комплексные числа пока не поддерживаются.
  2. Уникальность не обеспечивается, т.е. допускаются повторяющиеся значения ключа. Поскольку строки отсортированы по ключу, любые дубликаты в ключевых столбцах отображаются последовательно.
  3. Установка ключа key делает две вещи:
  1. переупорядочивает строки в таблице data.table по столбцам, предоставленным по ссылке, всегда в порядке по возрастанию.
  2. отмечает эти столбцы в качестве ключевых столбцов путем установки атрибута sorted таблицы data.table.
Поскольку строки переупорядочены, таблица data.table может иметь не более одного ключа, поскольку она не может быть отсортирована более чем одним способом [одновременно].
Далее в этой виньетке мы будем работать с набором данных flights.

b) Установка, получение и использование ключей в таблице data.table

- Как мы можем установить столбец origin в качестве ключа в таблице data.table flights?

setkey(flights, origin)
head(flights)
#    year month day dep_time dep_delay arr_time arr_delay cancelled carrier tailnum flight origin
# 1: 2014     1   1     1824         4     2145         0         0      AA  N3DEAA    119    EWR
# 2: 2014     1   1     1655        -5     2003       -17         0      AA  N5CFAA    172    EWR
# 3: 2014     1   1     1611       191     1910       185         0      AA  N471AA    300    EWR
# 4: 2014     1   1     1449        -1     1753        -2         0      AA  N4WNAA    320    EWR
# 5: 2014     1   1      607        -3      905       -10         0      AA  N5DMAA   1205    EWR
# 6: 2014     1   1      949         4     1243       -17         0      AA  N491AA   1223    EWR
#    dest air_time distance hour min
# 1:  LAX      339     2454   18  24
# 2:  MIA      161     1085   16  55
# 3:  DFW      214     1372   16  11
# 4:  DFW      214     1372   14  49
# 5:  MIA      154     1085    6   7
# 6:  DFW      215     1372    9  49

## alternatively we can provide character vectors to the function 'setkeyv()'
# setkeyv(flights, "origin") # useful to program with
  • Мы можем использовать функцию setkey() и передавать имена столбцов (без кавычек). Это полезно при интерактивном использовании.
  • В качестве альтернативы, вы можете передавать символьный вектор имен строк функции setkeyv(). Это особенно полезно при проектировании функций для передачи столбцов для установки ключей в качестве аргументов.
  • Обратите внимание, что мы не должны присваивать результаты переменной. Так происходит, потому что setkey() и setkeyv() изменяют исходную таблицу data.table по ссылке подобно :=, как мы видели в виньетке “Введение в data.table”. Результат возвращается скрыто.
  • Таблица data.table теперь переупорядочена (или отсортирована) по указанному столбцу - origin. Поскольку мы переупорядочивали по ссылке, требуется лишь дополнительный объем памяти для столбца, длина которого равна количеству строк в data.table; это опеспечивает эффективность использования памяти.
  • Вы также можете задавать ключи непосредственно при создании таблицы data.table при помощи функции data.table(), используя аргумент key=. Он принимает символьный вектор имен столбцов.

set* и :=:

В data.table только оператор := и все функции вида set* (например, setkey, setorder, setnames и т.д.) изменяют исходный объект по ссылке.
Как только вы задали определенные ключевые столбцы в таблице data.table, вы можете выбирать поднаборы при помощи запросов по этим ключевым столбцам с использованием .() в i. Напомним, что .() является псевдонимом для list().

- Использование ключевого столбца origin для выбора всех строк, для которых аэропортом отправки является “JFK”

flights[.("JFK")]
#        year month day dep_time dep_delay arr_time arr_delay cancelled carrier tailnum flight origin
#     1: 2014     1   1      914        14     1238        13         0      AA  N338AA      1    JFK
#     2: 2014     1   1     1157        -3     1523        13         0      AA  N335AA      3    JFK
#     3: 2014     1   1     1902         2     2224         9         0      AA  N327AA     21    JFK
#     4: 2014     1   1     1347         2     1706         1         0      AA  N319AA    117    JFK
#     5: 2014     1   1     2133        -2       37       -18         0      AA  N323AA    185    JFK
#    ---                                                                                             
# 81479: 2014    10  31     1705        -4     2024       -21         0      UA  N596UA    512    JFK
# 81480: 2014    10  31     1827        -2     2133       -37         0      UA  N568UA    514    JFK
# 81481: 2014    10  31     1753         0     2039       -33         0      UA  N518UA    535    JFK
# 81482: 2014    10  31      924        -6     1228       -38         0      UA  N512UA    541    JFK
# 81483: 2014    10  31     1124        -6     1408       -38         0      UA  N590UA    703    JFK
#        dest air_time distance hour min
#     1:  LAX      359     2475    9  14
#     2:  LAX      363     2475   11  57
#     3:  LAX      351     2475   19   2
#     4:  LAX      350     2475   13  47
#     5:  LAX      338     2475   21  33
#    ---                                
# 81479:  SFO      337     2586   17   5
# 81480:  SFO      344     2586   18  27
# 81481:  LAX      320     2475   17  53
# 81482:  SFO      343     2586    9  24
# 81483:  LAX      323     2475   11  24

## alternatively
# flights[J("JFK")] (or) flights[list("JFK")]
  • ключевым столбцом уже был задан столбец origin, поэтому достаточно напрямую передать значение, в данном случае “JFK”. Синтаксис .() помогает определить, что задача требует поиска значения “JFK” в ключевом столбце таблицы data.table (в данном случае это столбец origin)
  • Сперва получены индексы строк, соответствующих значению “JFK” в origin. И, поскольку в j нет никакого выражения, возвращены все столбцы для этих индексов строк.
  • Для отдельного ключевого столбца символьного типа вы можете опустить .() и использовать значения непосредственно, подобно созданию поднабора в data.frames с использованием имен строк.
flights["JFK"]              ## same as flights[.("JFK")]
  • Мы можем выбрать любой поднабор значений в соответствии с требованиями.
flights[c("JFK", "LGA")]    ## same as flights[.(c("JFK", "LGA"))]
Это выражение вернет все столбцы со строками, соответствующими значениям “JFK” или “LGA” для столбца origin.

- Как мы можем получить ключевые столбцы таблицы data.table?

Используем функцию key().
key(flights)
# [1] "origin"
  • Функция возвращает символьный вектор со всеми ключевыми столбцами
  • Если ключи не заданы, возвращается NULL.

c) Ключи и множественные столбцы

Напомним, что ключи - это как заряженные имена строк. Мы можем задавать ключи для множественных столбцов разных типов.

- Как я могу задать ключи для столбцов origin и dest?

setkey(flights, origin, dest)
head(flights)
#    year month day dep_time dep_delay arr_time arr_delay cancelled carrier tailnum flight origin
# 1: 2014     1   2      724        -2      810       -25         0      EV  N11547   4373    EWR
# 2: 2014     1   3     2313        88        9        79         0      EV  N18120   4470    EWR
# 3: 2014     1   4     1526       220     1618       211         0      EV  N11184   4373    EWR
# 4: 2014     1   4      755        35      848        19         0      EV  N14905   4551    EWR
# 5: 2014     1   5      817        47      921        42         0      EV  N19966   4470    EWR
# 6: 2014     1   5     2301        66        2        62         0      EV  N19966   4682    EWR
#    dest air_time distance hour min
# 1:  ALB       30      143    7  24
# 2:  ALB       29      143   23  13
# 3:  ALB       32      143   15  26
# 4:  ALB       32      143    7  55
# 5:  ALB       26      143    8  17
# 6:  ALB       31      143   23   1

## or alternatively
# setkeyv(flights, c("origin", "dest")) # provide a character vector of column names

key(flights)
# [1] "origin" "dest"
  • Таблица data.table сортируется сначала по origin, а затем по dest по ссылке.

- Выбрать все строки, для которых первый ключевой столбец имеет значение “JFK”, а второй - “MIA”

flights[.("JFK", "MIA")]
#       year month day dep_time dep_delay arr_time arr_delay cancelled carrier tailnum flight origin
#    1: 2014     1   1     1509        -1     1828       -17         0      AA  N5FJAA    145    JFK
#    2: 2014     1   1      917         7     1227        -8         0      AA  N5DWAA   1085    JFK
#    3: 2014     1   1     1227         2     1534        -1         0      AA  N635AA   1697    JFK
#    4: 2014     1   1      546         6      853         3         0      AA  N5CGAA   2243    JFK
#    5: 2014     1   1     1736         6     2043       -12         0      AA  N397AA   2351    JFK
#   ---                                                                                             
# 2746: 2014    10  31     1659        -1     1956       -22         0      AA  N5FNAA   2351    JFK
# 2747: 2014    10  31      826        -3     1116       -20         0      AA  N5EYAA   1085    JFK
# 2748: 2014    10  31      647         2      941       -17         0      AA  N5BTAA   1101    JFK
# 2749: 2014    10  31      542        -3      834       -12         0      AA  N3ETAA   2299    JFK
# 2750: 2014    10  31     1944        29     2232         4         0      AA  N5FSAA   2387    JFK
#       dest air_time distance hour min
#    1:  MIA      161     1089   15   9
#    2:  MIA      166     1089    9  17
#    3:  MIA      164     1089   12  27
#    4:  MIA      157     1089    5  46
#    5:  MIA      154     1089   17  36
#   ---                                
# 2746:  MIA      148     1089   16  59
# 2747:  MIA      146     1089    8  26
# 2748:  MIA      150     1089    6  47
# 2749:  MIA      150     1089    5  42
# 2750:  MIA      146     1089   19  44

Как здесь работает создание поднабора?

  • Важно понимать, как это работает изнутри. “JFK” сначала сопоставляется с первым ключевым столбцом origin. И среди этих сопоставленных строк “MIA” сопоставляется со вторым ключевым столбцом dest для получения индексов строк, где origin и dest совпадают с данными значениями.
  • Поскольку элемент j не задан, мы просто возвращаем все столбцы для этих индексов строк.

- Выбрать все строки, для которых только первый ключевой столбец origin соответствует значению “JFK”

key(flights)
# [1] "origin" "dest"

flights[.("JFK")] ## or in this case simply flights["JFK"], for convenience
#        year month day dep_time dep_delay arr_time arr_delay cancelled carrier tailnum flight origin
#     1: 2014     1   1     2011        10     2308         4         0      B6  N766JB     65    JFK
#     2: 2014     1   2     2215       134      145       161         0      B6  N507JB     65    JFK
#     3: 2014     1   7     2006         6     2314         6         0      B6  N652JB     65    JFK
#     4: 2014     1   8     2009        15     2252       -15         0      B6  N613JB     65    JFK
#     5: 2014     1   9     2039        45     2339        32         0      B6  N598JB     65    JFK
#    ---                                                                                             
# 81479: 2014    10  31      800         0     1040       -18         0      DL  N915AT   2165    JFK
# 81480: 2014    10  31     1932         1     2228        -8         0      B6  N516JB    225    JFK
# 81481: 2014    10  31     1443        -2     1726       -22         0      B6  N334JB    325    JFK
# 81482: 2014    10  31      957        -8     1255        -5         0      B6  N637JB    925    JFK
# 81483: 2014    10  31      831        -4     1118       -18         0      B6  N595JB   1025    JFK
#        dest air_time distance hour min
#     1:  ABQ      280     1826   20  11
#     2:  ABQ      252     1826   22  15
#     3:  ABQ      269     1826   20   6
#     4:  ABQ      259     1826   20   9
#     5:  ABQ      267     1826   20  39
#    ---                                
# 81479:  TPA      142     1005    8   0
# 81480:  TPA      149     1005   19  32
# 81481:  TPA      145     1005   14  43
# 81482:  TPA      149     1005    9  57
# 81483:  TPA      145     1005    8  31
  • Поскольку мы не задали никаких значений для второго ключевого столбца dest, происходит лишь сопоставление “JFK” в первом ключевом столбце origin и возврат всех соответствующих строк.

- Выбрать все строки, для которых только второй ключевой столбец dest соответствует значению “MIA”

flights[.(unique(origin), "MIA")]
#       year month day dep_time dep_delay arr_time arr_delay cancelled carrier tailnum flight origin
#    1: 2014     1   1     1655        -5     2003       -17         0      AA  N5CFAA    172    EWR
#    2: 2014     1   1      607        -3      905       -10         0      AA  N5DMAA   1205    EWR
#    3: 2014     1   1     1125        -5     1427        -8         0      AA  N3AGAA   1623    EWR
#    4: 2014     1   1     1533        43     1840        42         0      UA  N491UA    244    EWR
#    5: 2014     1   1     2130        60       29        49         0      UA  N476UA    308    EWR
#   ---                                                                                             
# 9924: 2014    10  31     1348       -11     1658        -8         0      AA  N3AMAA   2283    LGA
# 9925: 2014    10  31      950        -5     1257       -11         0      AA  N3LFAA   2287    LGA
# 9926: 2014    10  31      658        -2     1017        10         0      AA  N3HNAA   2451    LGA
# 9927: 2014    10  31     1913        -2     2212       -16         0      AA  N3LFAA   2455    LGA
# 9928: 2014    10  31     1530         1     1839       -11         0      US  N768US   1715    LGA
#       dest air_time distance hour min
#    1:  MIA      161     1085   16  55
#    2:  MIA      154     1085    6   7
#    3:  MIA      157     1085   11  25
#    4:  MIA      155     1085   15  33
#    5:  MIA      162     1085   21  30
#   ---                                
# 9924:  MIA      157     1096   13  48
# 9925:  MIA      150     1096    9  50
# 9926:  MIA      156     1096    6  58
# 9927:  MIA      156     1096   19  13
# 9928:  MIA      164     1096   15  30

Что здесь происходит?

  • Прочтите еще раз пункт “Как здесь работает создание поднабора?”. Значение для второго ключевого столбца “MIA” должно найти соответствия в ключевом столбце dest среди строк, для которых есть соответствие по первому ключевому столбцу origin. Мы не можем пропустить значения предшествующих ключевых столбцов. Поэтому мы задаем все уникальные значения ключевого столбца origin.
  • “MIA” автоматически повторяется, чтобы соответствовать длине unique(origin), которая равна 3.

2) Комбинирование ключей с j и by

По сути, все, что мы видели до сих пор - это получение индексов строк в i, но с использованием другого метода - с помощью ключей. Не удивительно, что мы можем делать то же самое в j и by, как мы видели в предыдущих виньетках. Мы покажем это на нескольких примерах.

a) Выбор в j

Вернуть столбец arr_delay как таблицу data.table, соответствующую origin = "LGA" и dest = "TPA".

key(flights)
# [1] "origin" "dest"
flights[.("LGA", "TPA"), .(arr_delay)]
#       arr_delay
#    1:         1
#    2:        14
#    3:       -17
#    4:        -4
#    5:       -12
#   ---          
# 1848:        39
# 1849:       -24
# 1850:       -12
# 1851:        21
# 1852:       -11
  • Индексы строк, соответствующих origin = "LGA" и dest = "TPA", получены с использованием поднабора на основе ключей.
  • Как только у нас есть индексы строк, мы смотрим на j, где требуется только столбец arr_delay. Поэтому мы просто выбираем столбец arr_delay для этих индексов строк точно таким же образом, как мы видели в виньетке “Введение в data.table”.
  • Мы могли бы также получить результат с помощью with = FALSE.
flights[.("LGA", "TPA"), "arr_delay", with=FALSE]

b) Цепочки операций

- Для результатов, полученных выше, использовать цепочку операций для сортировки столбца по убыванию.
flights[.("LGA", "TPA"), .(arr_delay)][order(-arr_delay)]
#       arr_delay
#    1:       486
#    2:       380
#    3:       351
#    4:       318
#    5:       300
#   ---          
# 1848:       -40
# 1849:       -43
# 1850:       -46
# 1851:       -48
# 1852:       -49

c) Вычислить или выполнить в j

- Найти максимальную задержку прибытия, соответствующую origin = "LGA" и dest = "TPA".

flights[.("LGA", "TPA"), max(arr_delay)]
# [1] 486
  • Мы можем убедиться, что результат совпадает с первым значением (486) из предыдущего примера.

d) Частичное присваивание по ссылке с использованием := в j

Мы уже видели этот пример в виньетке “Семантика ссылок”. Давайте взглянем на все часы hours, доступные в таблице data.table flights:
# get all 'hours' in flights
flights[, sort(unique(hour))]
#  [1]  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Мы видим, что данные имеют всего 25 уникальных значений. Присутствуют и 0, и 24. Давайте двигаться дальше и заменим 24 на 0, но в этот раз с использованием ключа.
setkey(flights, hour)
key(flights)
# [1] "hour"
flights[.(24), hour := 0L]
key(flights)
# NULL
  • Сперва мы сделали столбец hour ключом key . Это переупорядочило flights по столбцу hour и пометило этот столбец как key.
  • Теперь мы можем создавать поднаборы по столбцу hour, используя .(). Мы выбрали значение 24 и получили соответствующие индексы строк.
  • И для этих индексов мы заменили столбец key значением 0.
  • После того, как мы заменили значения ключевого столбца, таблица data.table flights больше не является упорядоченной по столбцу hour. Таким образом, ключ был автоматически удален путем установки в NULL.
Теперь значений 24 не должно быть в столбце hour.
flights[, sort(unique(hour))]
#  [1]  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

e) Агрегирование с использованием by

Давайте снова сделаем ключом столбцы origin, dest.
setkey(flights, origin, dest)
key(flights)
# [1] "origin" "dest"

- Получить максимальную задержку вылета за каждый месяц для origin = "JFK". Упорядочить результат по month

ans <- flights["JFK", max(dep_delay), keyby=month]
head(ans)
#    month   V1
# 1:     1  881
# 2:     2 1014
# 3:     3  920
# 4:     4 1241
# 5:     5  853
# 6:     6  798
key(ans)
# [1] "month"
  • Мы выбираем поднабор по ключевому столбцу origin для получения индексов строк, соответствующих “JFK”.
  • После того, как мы получили индексы строк, нам нужно лишь два столбца - month, чтобы выполнить по нему группировку, и dep_delay для получения max() в каждой группе. Поэтому оптимизация запросов в data.table приведет к выбору только этих двух столбцов для соответствующих индексов строк, полученных в i, для скорости и эффективного использования памяти.
  • И на этом поднаборе мы выполняем группировку по month и рассчитываем max(dep_delay).
  • Мы используем keyby, чтобы автоматически сделать month ключом для результата. Теперь мы понимаем, что это значит. В добавок к упорядочиванию, это также делает month ключевым столбцом.

3) Дополнительные аргументы - mult и nomatch

a) Аргумент mult

Для каждого запроса при помощи аргумента mult мы можем выбрать, должны ли быть возвращены “все” соответствующие строки, или только “первая” или “последняя”. Значение по умолчанию “все” - это то, что мы видели до сих пор.

- Выбрать только первую строку из всех строк, для которых origin соответствует “JFK” и dest соответствует “MIA”

flights[.("JFK", "MIA"), mult="first"]
#    year month day dep_time dep_delay arr_time arr_delay cancelled carrier tailnum flight origin
# 1: 2014     1   1      546         6      853         3         0      AA  N5CGAA   2243    JFK
#    dest air_time distance hour min
# 1:  MIA      157     1089    5  46

- Выбрать только последнюю строку из всех строк, для которых origin соответствует “LGA”, “JFK”, “EWR” и dest соответствует “XNA”

flights[.(c("LGA", "JFK", "EWR"), "XNA"), mult="last"]
#    year month day dep_time dep_delay arr_time arr_delay cancelled carrier tailnum flight origin
# 1: 2014     5  23     1803       163     2003       148         0      MQ  N515MQ   3553    LGA
# 2:   NA    NA  NA       NA        NA       NA        NA        NA      NA      NA     NA    JFK
# 3: 2014     2   3     1208       231     1516       268         0      EV  N14148   4419    EWR
#    dest air_time distance hour min
# 1:  XNA      158     1147   18   3
# 2:  XNA       NA       NA   NA  NA
# 3:  XNA      184     1131   12   8
  • Запрос “JFK”, “XNA” не соответствует никаким строкам в таблице flights, поэтому возвращается NA.
  • И снова, запрос для второго ключевого столбца dest, “XNA”, повторяется, чтобы соответствовать длине первого ключевого столбца origin, которая равна 3.

b) Аргумент nomatch

Мы можем выбрать при помощи аргумента nomatch, должны ли запросы, для которых нет соответствий, возвращать NA или вообще быть пропущенными.

- Выбрать только те строки из предыдущего примера, для которых есть соответствия

lights[.(c("LGA", "JFK", "EWR"), "XNA"), mult="last", nomatch = 0L]
#    year month day dep_time dep_delay arr_time arr_delay cancelled carrier tailnum flight origin
# 1: 2014     5  23     1803       163     2003       148         0      MQ  N515MQ   3553    LGA
# 2: 2014     2   3     1208       231     1516       268         0      EV  N14148   4419    EWR
#    dest air_time distance hour min
# 1:  XNA      158     1147   18   3
# 2:  XNA      184     1131   12   8
  • Значением по умолчанию для nomatch является NA. Установка nomatch = 0L приведет к пропуску запросов, для которых нет соответствий.
  • Для запроса “JFK”, “XNA” нет соответствующих строк в таблице flights, поэтому он пропускается.

4) Бинарный поиск в сравнении со сканированием вектора

До сих пор мы видели, как можно устанавливать и использовать ключи для создания поднаборов. Но в чем преимущество? Например, вместо:
# key by origin,dest columns
flights[.("JFK", "MIA")]
мы можем выполнить:
flights[origin == "JFK" & dest == "MIA"]
Одним из преимуществ, вероятно, является меньшее количество кода. Но, более того, создание поднаборов на основе бинарного поиска является невероятно быстрым.

a) Производительность бинарного поиска

В качестве примера, давайте создадим таблицу data.table с 20 млн. строк и тремя столбцами, задав столбцы x и y в качестве ключа.
set.seed(2L)
N = 2e7L
DT = data.table(x = sample(letters, N, TRUE), 
                y = sample(1000L, N, TRUE), 
                val=runif(N), key = c("x", "y"))
print(object.size(DT), units="Mb")
# 381.5 Mb

key(DT)
# [1] "x" "y"
DT весит ~380MB. Это не так уж много, но достаточно для иллюстрации.
Как мы видели в виньетке “Введение в data.table”, мы можем выбрать те строки, где x = "g" и y = 877, следующим образом:
## (1) Usual way of subsetting - vector scan approach
t1 <- system.time(ans1 <- DT[x == "g" & y == 877L])
t1
#    user  system elapsed 
#   0.871   0.022   0.919
head(ans1)
#    x   y       val
# 1: g 877 0.3946652
# 2: g 877 0.9424275
# 3: g 877 0.7068512
# 4: g 877 0.6959935
# 5: g 877 0.9673482
# 6: g 877 0.4842585
dim(ans1)
# [1] 761   3
Теперь давайте попробуем выбрать поднабор с использованием ключей.
## (2) Subsetting using keys
t2 <- system.time(ans2 <- DT[.("g", 877L)])
t2
#    user  system elapsed 
#   0.001   0.000   0.002
head(ans2)
#    x   y       val
# 1: g 877 0.3946652
# 2: g 877 0.9424275
# 3: g 877 0.7068512
# 4: g 877 0.6959935
# 5: g 877 0.9673482
# 6: g 877 0.4842585
dim(ans2)
# [1] 761   3

identical(ans1$val, ans2$val)
# [1] TRUE
Произошло ускорение в ~460 раз!

b) Почему использование ключей в data.table приводит к молниеносному созданию поднаборов?

Чтобы это понять, давайте сперва рассмотрим подход, состоящий в сканировании вектора (метод 1).

Сканирование вектора:

  • Происходит поиск значения “g” по столбцу x строка за строкой по всем 20 млн. строк. Это приводит к созданию логического вектора длиной 20 млн. со значениями TRUE, FALSE или NA, которые соответствуют значениям x.
  • Аналогичным образом, по столбцу y ищутся значения 877 среди всех 20 млн. строк и сохраняются в другом логическом векторе.
  • Поэлементная операция & выполняется на промежуточных логических векторах, и возвращаются все строки, для которых значение выражения равно TRUE.
Это то, что мы называем сканированием вектора. И это весьма неэффективно, особенно в случае больших таблиц, а также когда требуется повторное создание поднаборов, потому что каждый раз происходит повторное сканирование всех строк.
Теперь давайте рассмотрим бинарный поиск (метод 2). Напомним, из раздела “Свойства ключей”, что установка ключей переупорядочивает таблицу data.table по ключевым столбцам. Поскольку данные отсортированы, нам не нужно осуществлять сканирование по всей длине столбца! Вместо этого мы можем использовать бинарный поиск значения за время O(log n), в отличие от времени O(n) в случае сканирования вектора, где n является числом строк в таблице data.table

Бинарный поиск:

Вот очень простой пример. Рассмотрим (упорядоченные) значения, показанные ниже:
1, 5, 10, 19, 22, 23, 30
Предположим, мы хотели бы найти позицию, соответствующую значению 1, используя бинарный поиск - потому что мы знаем, что данные отсортированы.
  • Начинаем со значения в середине = 19. 1 == 19? Нет. 1 < 19.
  • Поскольку значение, которое мы ищем, меньше 19, оно должно быть где-то до 19. Таким образом, мы можем отбросить другую половину, которая >= 19.
  • Наш набор значений теперь сократился до 1, 5, 10. Еще раз возьмем значение в середине = 5. 1 == 5? Нет. 1 < 5.
  • Наш набор значений сократился до 1. 1 == 1? Да. Соответствующий индекс также равен 1. И это единственное соответствие.
С другой стороны, сканирование вектора привело бы к проверке всех значений, количество которых 7.
Видно, что с каждым поиском мы уменьшаем количество элементов в два раза. Поэтому выбор поднаборов на основе бинарного поиска является невероятно быстрым. Поскольку строки каждого столбца data.tables находятся в смежных ячейках памяти, операции выполняются способом, эффективным с точки зрения использования кэша (что также способствует большей скорости).
Кроме того, поскольку мы получаем индексы соответствующих строк непосредственно, без создания этих больших логических векторов (равных по размеру числу строк в таблице data.table), также более эффективно используется память.

Резюме

В этой виньетке мы изучили другой способ выбора поднаборов строк в i путем установки ключей в таблице data.table. Установка ключей позволяет нам выполнять молниеносное создание поднаборов при помощи использования бинарного поиска. В частности, мы увидели, как:
  • устанавливать ключ и создавать поднаборы в таблице data.table, используя ключ
  • создавать поднаборы, используя ключи, которые задают индексы строк в i, но гораздо быстрее
  • комбинировать создание поднаборов по ключу с j и by. Обратите внимание, что операции j и by - те же, что и раньше.
Создание поднаборов на основе ключа является невероятно быстрым и особенно полезным, когда задача включает повторяющееся создание поднаборов.
Вообще, мы не обязаны устанавливать и использовать ключи для операций агрегирования, пока наши данные не являются очень большими и/или задача не требует повторяющегося создания поднаборов, когда подход с использованием ключей будет заметно более производительным.
Тем не менее, установка ключей имеет важное значение для объединения двух таблиц data.table, что является предметом обсуждения в виньетке “Joins and rolling joins” (еще не написанной - прим. пер.). Мы расширим концепцию создания поднаборов на основе ключей для объединения двух таблиц data.table, основанного на ключевых столбцах.

Комментариев нет:

Отправить комментарий