R data.table多条件加入

Question

我已经设计了一个解决方案,从两个独立的数据表的多列中查找值,并添加一个基于列的新值计算(多个条件比较).代码如下.它涉及在计算两个表的值时使用data.table和join,但是,这些表没有连接到我正在比较的列上,因此我怀疑我可能没有获得data.tables固有的速度优势.我已经阅读了很多关于我的内容并且很兴奋.换句话说,我正在加入一个"虚拟"栏目,所以我认为我没有"正确"加入.

在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!这是使用当前开发版本v1.9.7中的NEW 非equi连接的另一种方法.

问题:你的使用by=.EACHI是完全合理的,因为另一种选择是执行交叉连接(dtGrid连接到所有行的每一行dtEvents),但这太详尽,并且必然会很快爆炸.

然而by = .EACHI,使用虚拟列与等连接一起执行,这导致计算所有距离(除了它一次一个,因此存储器有效).也就是说,在您的代码中,对于每个代码,仍然可以计算所有可能的距离; 因此它的规模不如预期.dtGriddtEvents

策略:那么你会同意,可接受的改进是限制会导致从加入的每一行的行数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

这有助于大幅减少搜索空间,因为我们不必查看每行中的所有行,而只需将这些行提取到其中,dtEventsdtGrid

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)构造非equi连接所需的所有列(因为公式中不允许表达式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

加速比分别为~10x,32x和53x.

请注意,dtGrid即使对于单行也不满足条件的dtEvents行将不会出现在结果中(由于nomatch=0L).如果你想要那些行,你还必须添加一个xm/xp/ym/ypcols ..并检查它们NA(=不匹配).

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

HTH

PS:查看历史记录中的另一个变体,其中实现整个连接,然后计算距离并生成计数.