Подстановка данных. Таблица по 2-му столбцу только из 2-х столбчатого ключа, с использованием двоичного поиска, а не сканирования вектора

Недавно я обнаружил бинарный поиск в data.table. Если таблица сортируется по нескольким клавишам, можно искать только по 2-му ключу?

DT = data.table(x=sample(letters,1e7,T),y=sample(1:25,1e7,T),rnorm(1e7))
setkey(DT,x,y)
#R> DT[J('x')]
#        x  y       V3
#     1: x  1  0.89109
#     2: x  1 -2.01457
#    ---              
#384922: x 25  0.09676
#384923: x 25  0.25168
#R> DT[J('x',3)]
#       x y       V3
#    1: x 3 -0.88165
#    2: x 3  1.51028
#   ---             
#15383: x 3 -1.62218
#15384: x 3 -0.63601

EDIT: благодаря @Arun

R> system.time(DT[J(unique(x), 25)])
   user  system elapsed 
  0.220   0.068   0.288 
R> system.time(DT[y==25])
   user  system elapsed 
  0.268   0.092   0.359

Ответ 1

Да, вы можете передать все значения в первое ключевое значение и подмножество с определенным значением для второго ключа.

DT[J(unique(x), 25), nomatch=0]

Если вам нужно подмножество более чем на одно значение во втором ключе (например, эквивалент DT[y %in% 25:24]), более общим решением является использование CJ

DT[CJ(unique(x), 25:24), nomatch=0]

Обратите внимание, что CJ по умолчанию сортирует столбцы и устанавливает ключ ко всем столбцам, что означает, что результат также будет отсортирован. Если это нежелательно, вы должны использовать sorted=FALSE

DT[CJ(unique(x), 25:24, sorted=FALSE), nomatch=0]

Также есть запрос на добавление дополнительных ключей к data.table в будущем. Я считаю, что план состоит в том, чтобы добавить новую функцию set2key.

FR # 1007 Создание дополнительных ключей

Существует также merge, у которого есть метод для data.table. Он создает вторичный ключ внутри него для вас, поэтому должен быть быстрее, чем слияние базы. См. ?merge.data.table.

Ответ 2

Основываясь на этом потоке электронной почты, я написал следующие функции:

create_index = function(dt, ..., verbose = getOption("datatable.verbose")) {
  cols = data.table:::getdots()
  res = dt[, cols, with=FALSE]
  res[, i:=1:nrow(dt)]
  setkeyv(res, cols, verbose = verbose)
}

JI = function(index, ...) {
  index[J(...),i]$i
}

Вот результаты моей системы с большим DT (строки 1e8):

> system.time(DT[J("c")])
   user  system elapsed 
  0.168   0.136   0.306 

> system.time(DT[J(unique(x), 25)])
   user  system elapsed 
  2.472   1.508   3.980 
> system.time(DT[y==25])
   user  system elapsed 
  4.532   2.149   6.674 

> system.time(IDX_y <- create_index(DT, y))
   user  system elapsed 
  3.076   2.428   5.503 
> system.time(DT[JI(IDX_y, 25)])
   user  system elapsed 
  0.512   0.320   0.831

Если вы используете индекс несколько раз, это того стоит.