R data.table多个条件联接

Question

我设计了一种解决方案，可以从两个单独的数据表的多个列中查找值，并添加一个基于新列的值计算(多个条件比较)。下面的代码。它涉及使用data.table并在计算两个表中的值时进行联接，但是，这些表未在我正在比较的列上联接，因此我怀疑我可能无法获得data.tables固有的速度优势。我已经读了很多，并为能进入而感到兴奋。换句话说，我要加入“虚拟”列，所以我认为我没有“适本地”加入。

给定一个X x X网格dtGrid和该网格内X ^ 2个随机事件dtEvents的列表，以确定每个网格点的1个单位半径内发生了多少个事件。代码如下。我选择了100 X 100的网格大小，这需要约1.5秒才能在我的计算机上运行联接。但是，如果不引入巨大的性能提升(200 X 200需要大约22秒)，我就无法做得更好。

我真的很喜欢能够在val语句中添加多个条件的灵活性(例如，如果我想添加一堆AND和OR组合，我可以做到这一点)，所以我想保留该功能。

有没有一种方法可以使用data.table“适本地”联接(或任何其他data.table解决方案)来获得更快/更有效的结果？

非常感谢!

#Initialization stuff
library(data.table)
set.seed(77L)

#Set grid size constant
#Increasing this number to a value much larger than 100 will result in significantly longer run times
cstGridSize = 100L

#Create Grid
vecXYSquare <- seq(0, cstGridSize, 1)
dtGrid <- data.table(expand.grid(vecXYSquare, vecXYSquare))
setnames(dtGrid, 'Var1', 'x')
setnames(dtGrid, 'Var2', 'y')
dtGrid[, DummyJoin:='A']
setkey(dtGrid, DummyJoin)

#Create Events
xrand <- runif(cstGridSize^2, 0, cstGridSize + 1)
yrand <- runif(cstGridSize^2, 0, cstGridSize + 1)
dtEvents <- data.table(x=xrand, y=yrand)
dtEvents[, DummyJoin:='A']
dtEvents[, Counter:=1L]
setkey(dtEvents, DummyJoin)

#Return # of events within 1 unit radius of each grid point
system.time(
    dtEventsWithinRadius <- dtEvents[dtGrid, {
        val = Counter[(x - i.x)^2 + (y - i.y)^2 < 1^2];  #basic circle fomula: x^2 + y^2 = radius^2
        list(col_i.x=i.x, col_i.y=i.y, EventsWithinRadius=sum(val))
    }, by=.EACHI]
)

Answer 1

非常有趣的问题..以及by = .EACHI的大量使用!这是使用NEW non-equi joins from the current development version, v1.9.7的另一种方法。

问题:完全可以证明您对by=.EACHI的使用是正确的，因为另一种选择是执行交叉连接(每一行dtGrid连接到dtEvents的所有行)，但这过于详尽，势必会迅速爆炸。

但是，by = .EACHI与使用伪列的等值连接一起执行，这导致计算所有距离(但一次只能计算一次，因此具有存储效率)。也就是说，在您的代码中，对于每个dtGrid，仍然使用dtEvents计算所有可能的距离；因此，它的扩展性没有预期的好。

策略:然后，您将接受一个可接受的改进，即限制将dtGrid的每一行连接到dtEvents所导致的行数。

让(x_i, y_i)来自dtGrid和(a_j, b_j)来自dtEvents，比如1 <= i <= nrow(dtGrid)和1 <= j <= nrow(dtEvents)。然后，i = 1表示，需要提取所有满足j的(x1 - a_j)^2 + (y1 - b_j)^2 < 1。只有在以下情况下才会发生这种情况:

(x1 - a_j)^2 < 1 AND (y1 - b_j)^2 < 1

这有助于大幅减少搜索空间，因为我们不必为 dtEvents中的每一行查看 dtGrid中的所有行，而只需要提取这些行，

a_j - 1 <= x1 <= a_j + 1 AND b_j - 1 <= y1 <= b_j + 1
# where '1' is the radius

该约束可以直接转换为非等价联接，并像以前一样与 by = .EACHI组合。唯一需要执行的附加步骤是构造 a_j-1, a_j+1, b_j-1, b_j+1列，如下所示:

foo1 <- function(dt1, dt2) {
    dt2[, `:=`(xm=x-1, xp=x+1, ym=y-1, yp=y+1)]                   ## (1) 
    tmp = dt2[dt1, on=.(xm<=x, xp>=x, ym<=y, yp>=y), 
              .(sum((i.x-x)^2+(i.y-y)^2<1)), by=.EACHI, 
              allow=TRUE, nomatch=0L
          ][, c("xp", "yp") := NULL]                              ## (2)
    tmp[]
}

## (1)构造非等额联接所需的所有列(因为 on=的公式中尚不允许使用表达式。
## (2)执行一个非等距联接，该联接计算距离并检查 < 1中每一行的受限组合上是否为 dtGrid的所有距离-因此应快得多。

基准测试:

# Here's your code (modified to ensure identical column names etc..):
foo2 <- function(dt1, dt2) {
    ans = dt2[dt1, 
                {
                 val = Counter[(x - i.x)^2 + (y - i.y)^2 < 1^2];
                 .(xm=i.x, ym=i.y, V1=sum(val))
                }, 
            by=.EACHI][, "DummyJoin" := NULL]
    ans[]
}

# on grid size of 100:
system.time(ans1 <- foo1(dtGrid, dtEvents)) # 0.166s
system.time(ans2 <- foo2(dtGrid, dtEvents)) # 1.626s

# on grid size of 200:
system.time(ans1 <- foo1(dtGrid, dtEvents)) # 0.983s
system.time(ans2 <- foo2(dtGrid, dtEvents)) # 31.038s

# on grid size of 300:
system.time(ans1 <- foo1(dtGrid, dtEvents)) # 2.847s
system.time(ans2 <- foo2(dtGrid, dtEvents)) # 151.32s

identical(ans1[V1 != 0]L, ans2[V1 != 0L]) # TRUE for all of them

加速分别约为10倍，32倍和53倍。

请注意，即使对于 dtGrid中的单行，也不满足条件的 dtEvents中的行将不会出现在结果中(由于 nomatch=0L)。如果要这些行，则还必须添加 xm/xp/ym/yp列之一。并检查它们的 NA(=不匹配)。

这就是我们必须删除所有0计数以获得相同= TRUE的原因。

高温超导

PS:请参阅历史记录，了解另一个变体，在该变体中实现了整个连接，然后计算了距离并生成了计数。