5 Вторичные индексы и автоиндексирование

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

5.1 Данные

Мы будем использовать набор данных flights, так же как в виньетке “Введение в data.table”.

# flights <- fread("flights14.csv")
flights <- fread("https://raw.githubusercontent.com/wiki/arunsrinivasan/flights/NYCflights14/flights14.csv")
head(flights)
#    year month day dep_delay arr_delay carrier origin dest air_time distance hour
# 1: 2014     1   1        14        13      AA    JFK  LAX      359     2475    9
# 2: 2014     1   1        -3        13      AA    JFK  LAX      363     2475   11
# 3: 2014     1   1         2         9      AA    JFK  LAX      351     2475   19
# 4: 2014     1   1        -8       -26      AA    LGA  PBI      157     1035    7
# 5: 2014     1   1         2         1      AA    JFK  LAX      350     2475   13
# 6: 2014     1   1         4         0      AA    EWR  LAX      339     2454   18
dim(flights)
# [1] 253316     11

5.2 Введение

В этой виньетке мы:

  1. обсудим вторичные индексы и объясним, зачем они нужны, на примерах, когда установка ключей не является идеальным решением;

  2. вновь выполним быстрое создание поднаборов, но на этот раз с использованием нового аргумента on, который вычисляет вторичные индексы для данной задачи (временно) или использует существующие;

  3. и, наконец, рассмотрим автоиндексирование, которое позволяет пойти еще дальше и создавать вторичные индексы автоматически, но работает так же, как и нативный синтаксис R для создания поднаборов.

5.3 1. Вторичные индексы

5.3.1 a) Что такое вторичные индексы?

Вторичные индексы подобны ключам keys в data.table, не считая двух основных отличий:

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

  • Может быть больше одного вторичного индекса в таблице data.table (как мы увидим ниже).

5.3.2 b) Установка и получение вторичных индексов

5.3.2.1 – Как мы можем задать столбец origin в качестве вторичного индекса в таблице data.table flights?

setindex(flights, origin)
head(flights)
#    year month day dep_delay arr_delay carrier origin dest air_time distance hour
# 1: 2014     1   1        14        13      AA    JFK  LAX      359     2475    9
# 2: 2014     1   1        -3        13      AA    JFK  LAX      363     2475   11
# 3: 2014     1   1         2         9      AA    JFK  LAX      351     2475   19
# 4: 2014     1   1        -8       -26      AA    LGA  PBI      157     1035    7
# 5: 2014     1   1         2         1      AA    JFK  LAX      350     2475   13
# 6: 2014     1   1         4         0      AA    EWR  LAX      339     2454   18

## alternatively we can provide character vectors to the function 'setindexv()'
# setindexv(flights, "origin") # useful to program with

# 'index' attribute added
names(attributes(flights))
# [1] "names"             "row.names"         "class"             ".internal.selfref"
# [5] "index"

  • Функции setindex() и setindexv() позволяют добавлять вторичный индекс в таблицу data.table.

  • Обратите внимание, что таблица flights физически не сортируется в порядке возрастания значений столбца origin, как это было бы при использовании setkey().

  • Также обратите внимание, что к таблице flights был добавлен атрибут index.

  • setindex(flights, NULL) удаляет все вторичные индексы.

5.3.2.2 – Как мы можем получить все вторичные индексы, заданные для таблицы flights?

indices(flights)
# [1] "origin"

setindex(flights, origin, dest)
indices(flights)
# [1] "origin"       "origin__dest"

  • Функция indices() возвращает все имеющиеся вторичные индексы в таблице data.table. Если нет ни одного индекса, возвращается значение NULL.

  • Обратите внимание, что при создании другого индекса по столбцам origin, dest мы не теряем первый индекс, созданный по столбцу origin, т.е. мы можем использовать множественные вторичные индексы.

5.3.3 c) Почему нам нужны вторичные индексы?

5.3.3.1 - Переупорядочивание таблицы data.table может быть затратным и не всегда идеальным решением

Рассмотрим случай, когда вы хотели бы выполнить быстрое создание поднабора на основе ключей для столбца origin и значения “JFK”. Мы будем делать это так:

## not run
setkey(flights, origin)
flights["JFK"] # or flights[.("JFK")]

setkey() требует выполнить:

  1. вычисление для заданных столбцов (в данном случае для origin) вектора, задающего порядок строк, и

  2. переупорядочивание (по ссылке) всей таблицы data.table на основе этого вектора.

Вычисление упорядочивающего вектора не занимает много времени, поскольку пакет data.table использует настоящую поразрядную сортировку для числовых (integer, numeric) и символьных (character) векторов. Однако переупорядочивание таблицы может оказаться длительным процессом (в зависимости от количества строк и столбцов).

Если нам не требуется повторное создание поднаборов по тому же самому столбцу, быстрое создание поднаборов на основе ключей может утратить преимущество по времени выполнения операции (в зависимости от размерности таблицы data.table).

5.3.3.2 - Ключ key может быть всего один

Теперь, если мы хотим повторить ту же операцию, но для столбца dest и значения“LAX”, мы снова должна использовать setkey().

## not run
setkey(flights, dest)
flights["LAX"]

И таблица flights снова сортируется, на этот раз по dest. В действительности нам нужна возможность быстрого создания поднаборов без этапа переупорядочивания таблицы. Вторичные индексы именно это и позволяют делать!

5.3.3.3 - Вторичные индексы могут быть использованы повторно

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

5.3.3.4 - Новый аргумент on обеспечивает более понятный синтаксис и автоматическое создание и повторное использование вторичных индексов

Как мы увидим в следующем разделе, аргумент on обеспечивает несколько преимуществ:

  • делает возможным вычисление вторичных индексов “на лету”. Благодаря этому не нужно каждый раз использовать setindex();

  • позволяет повторно использовать существующие индексы путем простой проверки атрибутов;

  • делает синтаксис понятнее, поскольку явно задаются столбцы, по которым выполняется создание поднабора. Код становится проще для понимания при последующей работе.

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

5.4 2. Быстрое создание поднаборов с использованием аргумента on и вторичных индексов

5.4.1 a) Быстрое создание поднаборов в i

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

flights["JFK", on = "origin"]
#        year month day dep_delay arr_delay carrier origin dest air_time distance hour
#     1: 2014     1   1        14        13      AA    JFK  LAX      359     2475    9
#     2: 2014     1   1        -3        13      AA    JFK  LAX      363     2475   11
#     3: 2014     1   1         2         9      AA    JFK  LAX      351     2475   19
#     4: 2014     1   1         2         1      AA    JFK  LAX      350     2475   13
#     5: 2014     1   1        -2       -18      AA    JFK  LAX      338     2475   21
#    ---                                                                              
# 81479: 2014    10  31        -4       -21      UA    JFK  SFO      337     2586   17
# 81480: 2014    10  31        -2       -37      UA    JFK  SFO      344     2586   18
# 81481: 2014    10  31         0       -33      UA    JFK  LAX      320     2475   17
# 81482: 2014    10  31        -6       -38      UA    JFK  SFO      343     2586    9
# 81483: 2014    10  31        -6       -38      UA    JFK  LAX      323     2475   11

## alternatively
# flights[.("JFK"), on = "origin"] (or) 
# flights[list("JFK"), on = "origin"]

  • Это выражение выполняет быстрое создание поднабора на основе бинарного поиска путем вычисления индекса “на лету”. Тем не менее, индекс не сохраняется автоматически в качестве атрибута. Это поведение может измениться в будущем (сейчас индес сохраняется при использовании синтаксиса вида flights[origin == "JFK"], о чем сказано ниже - прим. пер.).

  • Если мы уже создали вторичный индекс при помощи setindex(), аргумент on будет повторно его использовать вместо того, чтобы заново вычислять. Мы можем это увидеть, задав verbose = TRUE:

setindex(flights, origin)
flights["JFK", on = "origin", verbose = TRUE][1:5]
# Looking for existing (secondary) index... found. Reusing index.
# Starting bmerge ...done in 0 secs
#    year month day dep_delay arr_delay carrier origin dest air_time distance hour
# 1: 2014     1   1        14        13      AA    JFK  LAX      359     2475    9
# 2: 2014     1   1        -3        13      AA    JFK  LAX      363     2475   11
# 3: 2014     1   1         2         9      AA    JFK  LAX      351     2475   19
# 4: 2014     1   1         2         1      AA    JFK  LAX      350     2475   13
# 5: 2014     1   1        -2       -18      AA    JFK  LAX      338     2475   21

5.4.1.2 - Как я могу создать поднабор на основе столбцов origin и dest?

Например, если мы хотим создать поднабор для комбинации "JFK", "LAX":

flights[.("JFK", "LAX"), on = c("origin", "dest")][1:5]
#    year month day dep_delay arr_delay carrier origin dest air_time distance hour
# 1: 2014     1   1        14        13      AA    JFK  LAX      359     2475    9
# 2: 2014     1   1        -3        13      AA    JFK  LAX      363     2475   11
# 3: 2014     1   1         2         9      AA    JFK  LAX      351     2475   19
# 4: 2014     1   1         2         1      AA    JFK  LAX      350     2475   13
# 5: 2014     1   1        -2       -18      AA    JFK  LAX      338     2475   21

  • Аргумент on принимает символьный вектор из имен столбцов в том же порядке, который задан в аргументе i.

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

5.4.2 b) Выбор в j

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

5.4.2.1 - Вернуть один столбец arr_delay как таблицу data.table для origin = "LGA" и dest = "TPA"

flights[.("LGA", "TPA"), .(arr_delay), on = c("origin", "dest")]
#       arr_delay
#    1:         1
#    2:        14
#    3:       -17
#    4:        -4
#    5:       -12
#   ---          
# 1848:        39
# 1849:       -24
# 1850:       -12
# 1851:        21
# 1852:       -11

5.4.3 c) Объединение в цепочку

5.4.3.1 - Для результата, полученного выше, использовать объединение операций в цепочку для упорядочивания столбца по убыванию

flights[.("LGA", "TPA"), .(arr_delay), on = c("origin", "dest")][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

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

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

flights[.("LGA", "TPA"), max(arr_delay), on = c("origin", "dest")]
# [1] 486

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

Мы видели этот пример в виньетках “Семантика ссылок” и “Ключи и создание поднаборов на основе быстрого бинарного поиска”. Давайте взглянем на все значения hours, доступные в таблице 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, но на этот раз используем on вместо ключей.

flights[.(24L), hour := 0L, on = "hour"]

Теперь давайте убедимся, что значения 24 заменены на 0 в столбце 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
  • Это особенно значимое преимущество частичных индексов. Ранее для обновления нескольких строк в столбце hour мы должны были использовать setkey(), переупорядочивая всю таблицу. При использовании on исходный порядок строк сохраняется, и операция выполняется гораздо быстрее! Глядя на код, также гораздо проще понять, какую операцию мы хотим выполнить.

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

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

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

5.4.7 g) Аргумент mult

Остальные аргументы, включая mult, работают так же, как мы видели в виньетке “Ключи и создание поднаборов на основе быстрого бинарного поиска”. Значения по умолчанию mult = "all". Вместо этого мы можем выбрать возврат первой или последней подходящей строки.

5.4.7.1 - Выбрать только первые строки, для которых dest соответствует “BOS” и “DAY”

flights[c("BOS", "DAY"), on = "dest", mult = "first"]
#    year month day dep_delay arr_delay carrier origin dest air_time distance hour
# 1: 2014     1   1         3         1      AA    JFK  BOS       39      187   12
# 2: 2014     1   1        25        35      EV    EWR  DAY      102      533   17

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

flights[.(c("LGA", "JFK", "EWR"), "XNA"), on = c("origin", "dest"), mult = "last"]
#    year month day dep_delay arr_delay carrier origin dest air_time distance hour
# 1: 2014    10  31        -5       -11      MQ    LGA  XNA      165     1147    6
# 2:   NA    NA  NA        NA        NA      NA    JFK  XNA       NA       NA   NA
# 3: 2014    10  31        -2       -25      EV    EWR  XNA      160     1131    6

5.4.8 h) Аргумент nomatch

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

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

flights[.(c("LGA", "JFK", "EWR"), "XNA"), mult = "last", on = c("origin", "dest"), nomatch = 0L]
#    year month day dep_delay arr_delay carrier origin dest air_time distance hour
# 1: 2014    10  31        -5       -11      MQ    LGA  XNA      165     1147    6
# 2: 2014    10  31        -2       -25      EV    EWR  XNA      160     1131    6

Поскольку не было рейсов между “JFK” и “XNA”, соответствующие строки были исключены из результата.

5.5 3. Автоиндексирование

Сперва мы разобрали, как быстро создавать поднаборы при помощи бинарного поиска и ключей. Затем выяснили, как можно еще сильнее повысить производительность и сделать синтаксис понятнее, используя вторичные индексы. Что может быть лучше? Ответ - оптимизация нативного синтаксиса R для внутреннего использования вторичных индексов таким образом, чтобы мы получили ту же производительность без изучения нового синтаксиса.

Эту операцию выполняет автоиндексирование. В данный момент оно реализовано только для бинарных операторов == и %in% и работает только для отдельных столбцов. Индекс автоматически создается и сохраняется в качестве атрибута. В этом состоит отличие от аргумента on, который каждый раз вычисляет индексы “на лету”.

Давайте начнем с создания таблицы, достаточно большой для демонстрации преимущества.

set.seed(1L)
dt = data.table(x = sample(1e5L, 1e7L, TRUE), y = runif(100L))
print(object.size(dt), units = "Mb")
# 114.4 Mb

Когда мы используем == или %in% для отдельного столбца в первый раз, вторичный индекс создается автоматически и используется для создания поднабора.

## посмотрим на имена атрибутов
names(attributes(dt))
# [1] "names"             "row.names"         "class"             ".internal.selfref"

## запускаем в первый раз
(t1 <- system.time(ans <- dt[x == 989L]))
#    user  system elapsed 
#   0.202   0.006   0.210
head(ans)
#      x         y
# 1: 989 0.5372007
# 2: 989 0.5642786
# 3: 989 0.7151100
# 4: 989 0.3920405
# 5: 989 0.9547465
# 6: 989 0.2914710

## создан вторичный индекс
names(attributes(dt))
# [1] "names"             "row.names"         "class"             ".internal.selfref"
# [5] "index"

indices(dt)
# [1] "x"

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

## последовательное создание поднаборов
(t2 <- system.time(dt[x == 989L]))
#    user  system elapsed 
#   0.001   0.000   0.001
system.time(dt[x %in% 1989:2012])
#    user  system elapsed 
#   0.001   0.000   0.001

  • При первом запуске потребовалось 0.210 секунды, при втором - 0.001 секунды.

  • Автоиндексирование можно отключить при помощи глобального аргумента options(datatable.auto.index = FALSE).

В будущем мы планируем расширить автоиндексирование для выражений, содержащих больше одного столбца. Также мы работаем над расширением бинарного поиска для работы с другими операторами, такими как <, <=, > и >=.

Мы расширим быстрое создание поднаборов с использованием ключей и вторичных индексов на объединения (joins) в следующей виньетке, “Joins and rolling joins”.