Подстановка data.table с двоичным поиском по диапазону в двух столбцах - PullRequest
Новая
       21

Подстановка data.table с двоичным поиском по диапазону в двух столбцах

1 голос
/ 29 февраля 2020

Я пытаюсь быстро получить доступ к подмножеству большой таблицы данных. Данные имеют три столбца, все числовые c (с плавающей запятой), все с очень небольшим повторением. Два столбца - это данные, для которых я хотел бы выполнить бинарный поиск, а третий столбец содержит числа, которые мне действительно интересны. По сути, у меня есть (x, y, z) данные, которые я хотел бы указать диапазон в x и диапазон в y и возвращают все строки в этих диапазонах. 

# Generate some toy data of about the same size as the real data
DT <- data.table(x=runif(2000000), y=runif(2000000), z=runif(2000000))
head(DT)
#            x         y         z
# 1: 0.2675023 0.5725162 0.4162230
# 2: 0.1444540 0.8114941 0.1557195
# 3: 0.3607260 0.8159502 0.9705079
# 4: 0.3370213 0.9217284 0.5269885
# 5: 0.1085204 0.6312943 0.9676716
# 6: 0.1076674 0.1623447 0.1753712
ranges <- data.frame(x_min=runif(10000, max = 0.5), x_max=runif(10000, min = 0.5),
                     y_min=runif(10000, max = 0.5), y_max=runif(10000, min = 0.5))
head(ranges)
#        x_min     x_max      y_min     y_max
# 1 0.43817551 0.6720366 0.28052942 0.6309755
# 2 0.07469295 0.6744950 0.23170272 0.8431767
# 3 0.29520846 0.6991277 0.01882153 0.5162244
# 4 0.10500034 0.8977652 0.04806678 0.9528880
# 5 0.20168728 0.5655350 0.34401695 0.8241058
# 6 0.44158099 0.6739211 0.05359761 0.5832320

Вот наглядный пример того, что я пытаюсь сделать; Я хочу, чтобы все точки внутри красного прямоугольника, где края прямоугольника определяются максимальным и минимальным значениями диапазонов x и y. Тем не менее, у меня есть много красных прямоугольников, над которыми я буду зацикливаться. 

plot(DT$x, DT$y)
rect(xleft = ranges$x_min[1], xright = ranges$x_max[1],
     ybottom = ranges$y_min[1], ytop = ranges$y_max[1], border = "red")

Example

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

lapply(seq_len(nrow(ranges)), function(i){
  DT[x%between%c(ranges[i,]$x_min, ranges[i,]$x_max)&
       y%between%c(ranges[i,]$y_min, ranges[i,]$y_max)]
})

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

Этот вопрос задает нечто очень похожее, но лучший ответ (от Мэтта) указывает на то, что это было нелегко сделать в 2014 году, когда вопрос был опубликован. Он отмечает, что проблема такого рода действительно требует реализации объединения диапазонов и ссылается на запрос Feature на странице GitHub, который был с тех пор решен (через пару месяцев после открытия).

Три года спустя, вопрос был обновлен с помощью новой функциональности %between%, которую я уже реализовал, но я все еще не думаю, что здесь используется бинарный поиск по данным. Запрос на функцию подразумевал, что идеальное решение будет иметь форму DT[J(id,DT(from,to)),...], которая явно использует синтаксис J() для использования ключей.

Использует ли синтаксис %ween% фактический двоичный поиск под капотом? Если нет, как я могу предоставить два диапазона и при этом использовать функцию быстрого бинарного поиска?

PS dplyr * filter() примерно в 3 раза медленнее в наборе данных, так что это не так.

1 Ответ

1 голос
/ 29 февраля 2020

Насколько я понимаю, в скользящем соединении используется двоичный поиск, но только по последнему ключу соединения, поэтому одновременное объединение 4 ключей невозможно. Кроме того, ваши значения не являются целочисленными по своей природе, и, следовательно, невозможно точно определить 4 угла с помощью бинарного поиска.

Сказав это, вот несколько вариантов, позволяющих ускорить подмножество с неэквивалентным объединением Быстрее всего, но я сталкиваюсь с некоторыми проблемами ограничения памяти с вашими размерами: 

m0 <- function()
    lapply(seq_len(nrow(ranges)), function(i){
        DT[x%between%c(ranges[i,]$x_min, ranges[i,]$x_max)&
                y%between%c(ranges[i,]$y_min, ranges[i,]$y_max)]
    })

m1 <- function()
    ranges[, DT[x %between% c(x_min, x_max) & y %between% c(y_min, y_max)], 1L:nrow(ranges)]

m2 <- function() {
    setkey(DT, x, y)
    setDT(ranges, key=c("x_min", "x_max", "y_min", "y_max"))
    DT[ranges, on=.(x>=x_min, x<=x_max, y>=y_min, y<=y_max), allow.cartesian=TRUE, .(x.x, x.y, x.z)]
}

m3 <- function() {
    setkey(DT3, x)[, rn := .I]
    ranges[, ixmin := DT3[.SD, on=.(x=x_min), roll=-Inf, rn]]
    ranges[, ixmax := DT3[.SD, on=.(x=x_max), roll=Inf, rn]]

    setkey(DT3, y)
    DT3[DT3[ranges, on=.(y>=y_min, y<=y_max),
        by=.EACHI, .(rn=rn[rn %between% c(ixmin, ixmax)])], on=.(rn),
        .(x, y, z)]
}

microbenchmark::microbenchmark(times=1L, m0(), m1(), m2(), m3())

время: 

Unit: milliseconds
 expr      min       lq     mean   median       uq      max neval
 m0() 782.6070 782.6070 782.6070 782.6070 782.6070 782.6070     1
 m1() 713.9469 713.9469 713.9469 713.9469 713.9469 713.9469     1
 m2() 272.6018 272.6018 272.6018 272.6018 272.6018 272.6018     1
 m3() 765.3667 765.3667 765.3667 765.3667 765.3667 765.3667     1

данные: 

library(data.table)
set.seed(0L)
nr <- 2e4L
nrng <- 1e3L
dat <- data.table(x=runif(nr), y=runif(nr), z=runif(nr))
ranges <- data.frame(x_min=runif(nrng, max = 0.5), x_max=runif(nrng, min = 0.5),
    y_min=runif(nrng, max = 0.5), y_max=runif(nrng, min = 0.5))
dat[, rn := .I]

DT3 <- copy(dat)
DT <- copy(dat)
...