如何解决R和性能与SQL的差距和孤岛问题？

Question

我想知道是否可以有效地解决岛屿和间隙问题,类似于SQL.如果我们检查一个ID,我有以下数据:

ID StartDate  StartTime EndDate      EndTime 
1  19-05-2014 19:00     19-05-2014   20:00
1  19-05-2014 19:30     19-05-2014   23:30
1  19-05-2014 16:00     19-05-2014   18:00
1  20-05-2014 20:00     20-05-2014   20:30

请注意,前两行重叠,我想要做的是合并重叠的行,结果:

ID StartDate  StartTime EndDate      EndTime 
1  19-05-2014 19:00     19-05-2014   23:30
1  19-05-2014 16:00     19-05-2014   18:00
1  20-05-2014 20:00     20-05-2014   20:30

在R中有办法做到这一点吗？

我很清楚这是在SQL中完成的,但由于我的数据已经在R中,我更喜欢在R中执行此操作.其次,我对查找间隙和孤岛的性能有一些疑问,我知道SQL非常快这样做,但我想知道由于所有数据都在内存中R是否更快.

我想用data.table这个来做,但我不知道怎么做.

更新 - 对Arun的回应

我创建了以下包含每个可能的间隔方向的测试用例.

dat <- structure(
  list(ID = c(1L, 1L, 1L, 1L, 1L, 1L), 
       stime = structure(c(as.POSIXct("2014-01-15 08:00:00"),
                           as.POSIXct("2014-01-15 10:00:00"),
                           as.POSIXct("2014-01-15 08:30:00"),
                           as.POSIXct("2014-01-15 09:00:00"),
                           as.POSIXct("2014-01-15 11:30:00"),
                           as.POSIXct("2014-01-15 12:00:00")),
                         class = c("POSIXct", "POSIXt"), tzone = ""),
       etime = structure(c(as.POSIXct("2014-01-15 09:30:00"),
                           as.POSIXct("2014-01-15 11:00:00"),
                           as.POSIXct("2014-01-15 10:00:00"), 
                           as.POSIXct("2014-01-15 09:30:00"),
                           as.POSIXct("2014-01-15 12:30:00"),
                           as.POSIXct("2014-01-15 13:00:00")), 
                         class = c("POSIXct", "POSIXt"), tzone = "")
  ),
  .Names = c("ID", "stime", "etime"),
  sorted = c("ID", "stime", "etime"),
  class = c("data.table", "data.frame"),
  row.names = c(NA,-6L)
)

我希望从8:30到10:00的间隔将"粘在"10:00到11:00,但事实并非如此.结果是:

   idx ID               stime               etime
1:   4  1 2014-01-15 08:00:00 2014-01-15 10:00:00
2:   3  1 2014-01-15 10:00:00 2014-01-15 11:00:00
3:   6  1 2014-01-15 11:30:00 2014-01-15 13:00:00

以下数据集提供了更全面的测试:

# The numbers represent seconds from 1970-01-01 01:00:01
dat <- structure(
  list(ID = c(1L, 1L, 1L, 1L, 1L, 1L, 2L, 2L, 2L, 2L, 2L, 2L, 2L), 
       stime = structure(c(as.POSIXct("2014-01-15 08:00:00"),
                           as.POSIXct("2014-01-15 10:00:00"),
                           as.POSIXct("2014-01-15 08:30:00"),
                           as.POSIXct("2014-01-15 09:00:00"),
                           as.POSIXct("2014-01-15 11:30:00"),
                           as.POSIXct("2014-01-15 12:00:00"),
                           as.POSIXct("2014-01-15 07:30:00"),
                           as.POSIXct("2014-01-15 08:00:00"),
                           as.POSIXct("2014-01-15 08:30:00"),
                           as.POSIXct("2014-01-15 09:00:00"),
                           as.POSIXct("2014-01-15 09:00:00"),
                           as.POSIXct("2014-01-15 09:30:00"),
                           as.POSIXct("2014-01-15 10:00:00")
                           ),
                         class = c("POSIXct", "POSIXt"), tzone = ""),
       etime = structure(c(as.POSIXct("2014-01-15 09:30:00"),
                           as.POSIXct("2014-01-15 11:00:00"),
                           as.POSIXct("2014-01-15 10:00:00"), 
                           as.POSIXct("2014-01-15 09:30:00"),
                           as.POSIXct("2014-01-15 12:30:00"),
                           as.POSIXct("2014-01-15 13:00:00"),
                           as.POSIXct("2014-01-15 08:30:00"),
                           as.POSIXct("2014-01-15 09:00:00"),
                           as.POSIXct("2014-01-15 09:30:00"),
                           as.POSIXct("2014-01-15 10:00:00"),
                           as.POSIXct("2014-01-15 10:00:00"),
                           as.POSIXct("2014-01-15 10:30:00"),
                           as.POSIXct("2014-01-15 11:00:00")
                           ), 
                         class = c("POSIXct", "POSIXt"), tzone = "")
  ),
  .Names = c("ID", "stime", "etime"),
  sorted = c("ID", "stime", "etime"),
  class = c("data.table", "data.frame"),
  row.names = c(NA,-6L)
)

所以我们的结果是:

   idx ID               stime               etime
1:   4  1 2014-01-15 08:00:00 2014-01-15 10:00:00
2:   3  1 2014-01-15 10:00:00 2014-01-15 11:00:00
3:   6  1 2014-01-15 11:30:00 2014-01-15 13:00:00
4:  12  2 2014-01-15 07:30:00 2014-01-15 09:30:00
5:  13  2 2014-01-15 09:00:00 2014-01-15 11:00:00

现在对于ID = 2的受访者,我们看到间隔是重叠的,但没有报告为一个间隔.正确的解决方案是:

   idx ID               stime               etime
1:   ?  1 2014-01-15 08:00:00 2014-01-15 11:00:00
3:   ?  1 2014-01-15 11:30:00 2014-01-15 13:00:00
4:  ??  2 2014-01-15 07:30:00 2014-01-15 11:00:00

更新 - 基准测试和大型数据集

我有以下数据集,大约有1000个用户,每个用户有500个持续时间,给出50万行.您可以在我的Google云端硬盘下载数据集,包括Google云端硬盘中的解决方案.

使用Itzik Ben-Gan在SQL中提供的解决方案,使用8GB RAM,64位,i5-4210U CPU @ 1.70Ghz - 2.39Ghz的笔记本电脑上的SQL Server 2014大约需要5秒钟.5秒不包括创建功能的过程.此外,不会为任何表创建索引.

PS:我用 library(lubridate);

Answer 1

这是一个非常简单的想法.按开始时间排序,然后查找结束时间的累计最大值.完成后,重叠组只是下一个开始时间仍然小于或等于当前累计最大结束时间(全部由ID完成)的重叠组:

setorder(dat, ID, stime) # ordering by ID is unnecessary, it's just prettier

dat[, etime.max := as.POSIXct(cummax(as.numeric(etime)), origin = '1970-01-01'), by = ID]

# find the grouping of intervals (1:.N hack is to avoid warnings when .N=1)
dat[, grp := cumsum(c(FALSE, stime[2:.N] > etime.max[1:(.N-1)]))[1:.N], by = ID]

dat[, .(stime = min(stime), etime = max(etime)), by = .(ID, grp)][, grp := NULL][]
#   ID               stime               etime
#1:  1 2014-01-15 08:00:00 2014-01-15 11:00:00
#2:  1 2014-01-15 11:30:00 2014-01-15 13:00:00
#3:  2 2014-01-15 07:30:00 2014-01-15 11:00:00

由于这不需要找到所有可能的重叠,因此速度非常快.在大致匹配OP描述的模拟数据集上,它对我来说是瞬时的(<0.2s).