data.table: производительность бинарного поиска VS векторного сканирования - PullRequest
Новая
       23

data.table: производительность бинарного поиска VS векторного сканирования

7 голосов
/ 03 мая 2020

Я искал лучший способ подмножества в таблице данных, определенной следующим образом: 

library(data.table)
library(microbenchmark)

set.seed(2L)
N = 1e7L
DT = data.table(x = sample(letters, N, TRUE),
                y = sample(1000L, N, TRUE),
                val = runif(N))
setkey(DT, x, y)

Существует двоичный поиск (SUBSET1), а также «векторный путь сканирования» (SUBSET2). 

SUBSET1 <- function(){
  a <- DT[.(c("a"), c(5L)), .N, nomatch = NULL]
}
SUBSET2 <- function(){
  a <- DT[ x == "a" & y == 5L, .N, nomatch = NULL]
}

Что мне особенно нравится в «векторном сканировании», так это то, что он действительно понятен и очень удобочитаем. Тем не менее, он кажется в 2 раза медленнее по сравнению с собственным способом двоичного поиска. 

microbenchmark(SUBSET1(), 
               SUBSET2(), 
               times = 500 )
  Unit: milliseconds
        expr    min      lq     mean  median     uq      max neval
   SUBSET1() 1.0328 1.27790 1.878415 1.53370 1.8924  20.5789   500
   SUBSET2() 2.4896 3.06665 4.476864 3.52685 4.3682 179.1607   500

Мой вопрос
Я не понимаю, почему SUBSET2 медленнее. Это потому, что существует своего рода внутреннее преобразование из «пути векторного сканирования» в двоичный поиск или из-за того, что «путь векторного сканирования» выполняется как таковой (и, следовательно, медленнее, чем двоичный поиск)?

1 Ответ

12 голосов
/ 04 мая 2020

Как отмечает @jangorecki, оба запроса уже используют ключ - последний просто требует небольшого дополнительного времени для преобразования формы «векторного сканирования» в форму двоичного поиска. Вы можете увидеть это с помощью verbose=TRUE: 

DT[ x == "a" & y == 5L, .N, nomatch = NULL, verbose = TRUE]

показывает вывод: 

Optimized subsetting with key 'x, y'
forder.c received 1 rows and 2 columns
forder took 0.001 sec
x is already ordered by these columns, no need to call reorder
i.x has same type (character) as x.x. No coercion needed.
i.y has same type (integer) as x.y. No coercion needed.
on= matches existing key, using key
Starting bmerge ...
bmerge done in 0.000s elapsed (0.000s cpu) 
Constructing irows for '!byjoin || nqbyjoin' ... 0.000s elapsed (0.000s cpu) 
Detected that j uses these columns: <none>

Сравните с версией прямого двоичного поиска: 

DT[.(c("a"), c(5L)), .N, nomatch = NULL, verbose = TRUE]

i.V1 has same type (character) as x.x. No coercion needed.
i.V2 has same type (integer) as x.y. No coercion needed.
on= matches existing key, using key
Starting bmerge ...
forder.c received 1 rows and 2 columns
bmerge done in 0.001s elapsed (0.000s cpu) 
Constructing irows for '!byjoin || nqbyjoin' ... 0.000s elapsed (0.000s cpu) 
Detected that j uses these columns: <none>

Но это в два раза медленнее, верно? Также, как указано, масштаб времени очень мал. Более полезное сравнение - это случай, когда ключ вообще не используется. Давайте создадим несортированную копию ваших данных: 

DTrand = DT[sample(.N)]

Еще один быстрый шаг вперед - мы должны быть осторожны при сравнительном анализе, потому что data.table также выполняет некоторые автоматические c оптимизации, чтобы помочь сортировать ваши данные даже в этот несортированный случай: 

DTrand[ x == "a" & y == 5L, .N, nomatch = NULL, verbose = TRUE]

Внимательно прочитайте вывод: 

Creating new index 'y__x'
Creating index y__x done in ... forder.c received 10000000 rows and 3 columns
forder took 0.424 sec
0.286s elapsed (1.117s cpu) 
Optimized subsetting with index 'y__x'
forder.c received 1 rows and 2 columns
forder took 0.002 sec
x is already ordered by these columns, no need to call reorder
i.y has same type (integer) as x.y. No coercion needed.
i.x has same type (character) as x.x. No coercion needed.
on= matches existing index, using index
Starting bmerge ...
bmerge done in 0.000s elapsed (0.000s cpu) 
Constructing irows for '!byjoin || nqbyjoin' ... 0.000s elapsed (0.001s cpu) 
Reorder irows for 'mult=="all" && !allGrp1' ... forder.c received 360 rows and 2 columns
0.000s elapsed (0.002s cpu) 
Detected that j uses these columns: <none> 
[1] 360

data.table автоматически применил setindex к вашей таблице, что (хотя и не так быстро, как физическая сортировка, как с setkey), тем не менее, ускорит любые будущие подмножества; просто повторяя (как это было бы с тестом): 

DTrand[ x == "a" & y == 5L, .N, nomatch = NULL, verbose = TRUE]

Обратите внимание на сходство с регистром с ключом (swap key для index): 

Optimized subsetting with index 'y__x'
forder.c received 1 rows and 2 columns
forder took 0 sec
x is already ordered by these columns, no need to call reorder
i.y has same type (integer) as x.y. No coercion needed.
i.x has same type (character) as x.x. No coercion needed.
on= matches existing index, using index
Starting bmerge ...
bmerge done in 0.000s elapsed (0.000s cpu) 
Constructing irows for '!byjoin || nqbyjoin' ... 0.000s elapsed (0.000s cpu) 
Reorder irows for 'mult=="all" && !allGrp1' ... forder.c received 360 rows and 2 columns
0.001s elapsed (0.001s cpu) 
Detected that j uses these columns: <none> 
[1] 360

Таким образом, Наивный тест даже на DTrand не будет настоящим сравнением - после первого запуска теста таблица будет проиндексирована, и последующие подмножества будут использовать этот & бинарный поиск. См. виньетка для вторичных индексов для получения более подробной информации.

Мы можем обойти это и получить надлежащий тест, установив для параметра datatable.auto.index значение FALSE и сбросив существующий индекс: 

options(datatable.auto.index = FALSE)
setindex(DTrand, NULL)

Теперь data.table забывает, как сортировать DTrand по x и y, и мы можем сравнить подход двоичного поиска и подмножество истинного вектора: 

microbenchmark::microbenchmark(
  times = 50L,
  vector = DTrand[ x == "a" & y == 5L, .N, nomatch = NULL],
  binary = DT[     x == "a" & y == 5L, .N, nomatch = NULL]
)
# Unit: milliseconds
#    expr       min         lq       mean     median        uq        max neval
#  vector 101.43306 114.325340 134.154362 119.367909 128.05273 345.721296    50
#  binary   1.06033   1.160188   1.631119   1.367017   1.57334   5.508802    50

Так что пока прямой подход с использованием .() в два раза быстрее, чем оптимизированный подход с использованием ==, == все еще в 100 раз быстрее, чем true векторное подмножество.

Вы также можете выгода от data.table бенчмаркинга

...