Ключи и создание поднаборов на основе быстрого бинарного поиска
translated by Andrey Ogurtsov
2015-06-24
Эта виньетка предназначена для тех, кто уже знаком с синтаксисом 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Введение
В этой виньетке мы:- сперва введем понятие ключа
keyв таблице data.table, а также зададим и используем ключи для создания поднаборов вiна основе быстрого бинарного поиска - увидим, как можно комбинировать создание поднаборов на основе ключей с
jиbyтем же способом, что и раньше - взглянем на другие полезные аргументы -
multиnomatch - и, в заключение, оценим преимущество использования ключей - выполним создание поднаборов на основе быстрого бинарного поиска и сравним с традиционным подходом, который состоит в сканировании вектора.
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- Каждая строка ограничена ровно одним именем.
- Кроме того, имена строк должны быть уникальными.
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 allowedDT = 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. Думайте о них как о “заряженных” именах строк.Ключи и их свойства
- Мы можем устанавливать ключи для множественных столбцов, которые могут иметь разные типы - integer, numeric, character, factor, integer64 и т.д. Списки и комплексные числа пока не поддерживаются.
- Уникальность не обеспечивается, т.е. допускаются повторяющиеся значения ключа. Поскольку строки отсортированы по ключу, любые дубликаты в ключевых столбцах отображаются последовательно.
- Установка ключа
keyделает две вещи:
- переупорядочивает строки в таблице data.table по столбцам, предоставленным по ссылке, всегда в порядке по возрастанию.
- отмечает эти столбцы в качестве ключевых столбцов путем установки атрибута
sortedтаблицы 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"))]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 2425 уникальных значений. Присутствуют и 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.
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] TRUEb) Почему использование ключей в 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- Начинаем со значения в середине = 19. 1 == 19? Нет. 1 < 19.
- Поскольку значение, которое мы ищем, меньше 19, оно должно быть где-то до 19. Таким образом, мы можем отбросить другую половину, которая >= 19.
- Наш набор значений теперь сократился до 1, 5, 10. Еще раз возьмем значение в середине = 5. 1 == 5? Нет. 1 < 5.
- Наш набор значений сократился до 1. 1 == 1? Да. Соответствующий индекс также равен 1. И это единственное соответствие.
Видно, что с каждым поиском мы уменьшаем количество элементов в два раза. Поэтому выбор поднаборов на основе бинарного поиска является невероятно быстрым. Поскольку строки каждого столбца data.tables находятся в смежных ячейках памяти, операции выполняются способом, эффективным с точки зрения использования кэша (что также способствует большей скорости).
Кроме того, поскольку мы получаем индексы соответствующих строк непосредственно, без создания этих больших логических векторов (равных по размеру числу строк в таблице data.table), также более эффективно используется память.
Резюме
В этой виньетке мы изучили другой способ выбора поднаборов строк вi путем установки ключей в таблице data.table. Установка ключей позволяет нам выполнять молниеносное создание поднаборов при помощи использования бинарного поиска. В частности, мы увидели, как:- устанавливать ключ и создавать поднаборы в таблице data.table, используя ключ
- создавать поднаборы, используя ключи, которые задают индексы строк в
i, но гораздо быстрее - комбинировать создание поднаборов по ключу с
jиby. Обратите внимание, что операцииjиby- те же, что и раньше.
Вообще, мы не обязаны устанавливать и использовать ключи для операций агрегирования, пока наши данные не являются очень большими и/или задача не требует повторяющегося создания поднаборов, когда подход с использованием ключей будет заметно более производительным.
Тем не менее, установка ключей имеет важное значение для объединения двух таблиц
data.table, что является предметом обсуждения в виньетке “Joins and rolling joins” (еще не написанной - прим. пер.). Мы расширим концепцию создания поднаборов на основе ключей для объединения двух таблиц data.table, основанного на ключевых столбцах.
Комментариев нет:
Отправить комментарий