Если вас интересует этот вопрос, вы можете взглянуть на виньетку с данными по теме
По умолчанию R использует линейный поиск. Сканирует весь вектор. Это одна из замечательных возможностей data.table для включения binary search с индексированной таблицей. В data.table индексированный набор данных будет иметь физически упорядоченные элементы в памяти, поэтому поиск значений в нем происходит очень быстро. Вторичные индексы в data.table (см. здесь ) включат двоичный поиск, но физически данные не будут переупорядочены в смежных слотах памяти.
Возможно, виньетка data.table более явная:
Видно, что при каждом поиске мы уменьшаем количество запросов вдвое. Вот почему наборы на основе бинарного поиска невероятно быстрые. Поскольку строки каждого столбца data.tables имеют смежные местоположения в памяти, операции выполняются очень эффективным способом кэширования (также влияет на скорость).
Кроме того, поскольку мы получаем соответствующие индексы строк непосредственно без необходимость создания этих огромных логических векторов (равных количеству строк в data.table) также весьма экономична для памяти.
Пример
Давайте посмотрим на примере , Для сравнения используется пакет microbenchmark.
Мы сравним:
- (Линейный) поиск на
data.frame - Фильтре с
dplyr - (Линейный) поиск по
data.table - (Бинарный) поиск по
data.table с первичными ключами (используется setkey) - (Бинарный) поиск по
data.table с дополнительными ключами (используется setindex)
Давайте создадим все необходимые кусочки:
library(data.table)
library(dplyr)
df <- data.frame(
x = rnorm(1e6),
y = rnorm(1e6)
)
dt <- as.data.table(df)
dt2 <- copy(dt)
dt3 <- copy(dt)
Мы установим первичный ключ на dt2 (бинарный поиск + переупорядочение объекта в памяти) и вторичный ключ на dt3 (бинарный поиск, но не переупорядочение в памяти)
setkey(dt2, x)
setindex(dt3, x)
Микробенчмарк:
m <- microbenchmark::microbenchmark(
df[df$x<0,],
df %>% dplyr::filter(x<0),
dt[x<0],
dt2[x<0],
dt3[x<0],
times = 20L
)
m
Unit: milliseconds
expr min lq mean median uq max neval
df[df$x < 0, ] 56.56557 57.54392 66.97838 61.39609 75.30391 91.42418 20
df %>% dplyr::filter(x < 0) 23.24242 24.15183 34.64290 26.02232 34.91405 143.10476 20
dt[x < 0] 18.32496 18.96585 21.35255 20.25604 23.02666 33.25656 20
dt2[x < 0] 10.85129 10.94804 11.92941 11.21601 11.80469 18.29040 20
dt3[x < 0] 18.37789 18.47568 19.51928 18.76135 19.39782 26.90826 20
Базовый подход R самый медленный, безусловно. В этом примере использование вторичных индексов не повышает производительность. Но первичные ключи делают!
ggplot2::autoplot(m)
