r语言 - 如何识别'to'和'from'位置未涵盖的所有序列号？

Question

我有一个数据表，定义了一组序列的开始和结束坐标。例如：

df1 <- data.frame(from = c(7, 22, 35, 21, 50),
              to = c(13, 29, 43, 31, 60))

给定开始和结束坐标(即 1 和 100(，我正在尝试使用相同的输出格式识别序列未涵盖的所有整数。例如：

df2 <- data.frame(from = c(1, 14, 32, 44, 61),
              to = c(6, 20, 34, 49, 100))

这是我目前的尝试，其中我向量化 df1 中的序列，然后识别所有与序列 1：100 不匹配的整数。

seq2 <- Vectorize(seq.default, vectorize.args = c("from", "to"))
seq <- c(1:100)
df1_int <- unlist(seq2(from = df1$from, to = df1$to))
df1_int <- unique(df1_int)
df2_int <- seq[!seq %in% df1_int]
all(diff(df2_int) == 1)

但是，此方法对于我要应用它的数据集(~100,000,000 个整数(来说太慢了，而且我不知道如何将向量df2_int重新格式化为 df2 格式的数据帧。

任何帮助将不胜感激！

注意：df1 中的序列并不总是以最小的整数开头(例如，序列可以从 13 运行到 7，而不是从 7 到 13(。也可能有一个整数的序列(例如从 7 到 7(。

Answer 1

由于您需要一个快速的解决方案，我们可以尝试使用 setdiff 和 split 的基本 R 方法。我们留给mapply的矢量化.要找到split的因素，我们使用 findInterval .为了获取结果列表的元素起点和终点，我们使用 range 清除。

d <- setdiff(1:100, unlist(mapply(seq.default, df1[, 1], df1[, 2])))
t(sapply(split(d, findInterval(d, d[which(c(1, diff(d)) > 1)])), range))
#   [,1] [,2]
# 0    1    6
# 1   14   20
# 2   32   34
# 3   44   49
# 4   61  100

基准

正如我们从基准测试中看到的那样，我们已经实现了相当快的解决方案。

Unit: microseconds
         expr      min        lq      mean    median       uq      max neval cld
        purrr 1575.479 1593.2110 1634.3573 1604.9475 1634.033 2028.095   100   b
 findInterval  250.801  256.9245  276.8609  273.3815  281.673  498.285   100  a 

Answer 2

编辑：应该更好地阅读这个问题。这基本上是您当前的方法。

您可以使用 seq 函数pmap输入，并unlist该函数以获取所有值的向量。然后setdiff获取缺失值。使用 diff 和 cumsum 可以为缺失值创建分组变量，将它们分组为"从-"到"对。然后按分组变量拆分缺失值向量，并map该向量以为每个组创建一行输出。

library(purrr)
miss <- setdiff(1:100, unlist(pmap(df1, seq)))
i <- 
  miss %>% 
    diff %>% 
    `>`(1) %>% 
    rev %>%
    cumsum %>% 
    rev 
map_df(split(miss, c(i, 0)), ~list(from = head(.x, 1), to = tail(.x, 1))) %>% 
  dplyr::arrange(from)

# # A tibble: 5 x 2
#    from    to
#   <int> <int>
# 1     1     6
# 2    14    20
# 3    32    34
# 4    44    49
# 5    61   100

Answer 3

借用思想 如何扁平化/合并重叠的时间段，但以data.table的方法代替：

library(data.table)
setDT(df1)
setorder(df1, from, to)
maxn <- 100L    
#see linked post
df1[, g := c(0, cumsum(shift(from, -1L) > cummax(to))[-.N])]
#get desired output
df1[, .(from=max(to)+1L, to=min(from)-1L), by=.(g)][, 
    .(from=c(1L, from), to=c(to, maxn))]

希望这对于具有 100mio 整数的实际数据集来说足够快。