Как определить все последовательные номера, не охваченные позициями «до» и «от»? - PullRequest
Новая
       15

Как определить все последовательные номера, не охваченные позициями «до» и «от»?

6 голосов
/ 16 апреля 2019

У меня есть таблица данных, которая определяет начальную и конечную координаты для набора последовательностей. Например: 

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).

Ответы [ 3 ]

2 голосов
/ 16 апреля 2019

Так как вам нужно быстрое решение, мы могли бы попробовать базовый подход R, используя setdiff и split. Векторизацию оставляем до 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

Benchmark

Как видно из теста, мы достигли довольно быстрого решения. 

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
2 голосов
/ 16 апреля 2019

Edit: должен был прочитать вопрос лучше.Это в основном ваш нынешний подход.

Вы можете pmap на входе с помощью функции seq и unlist, чтобы получить вектор всех значений.Затем setdiff, чтобы получить пропущенные значения.Используя diff и cumsum, вы можете создать переменную группировки для отсутствующих значений, сгруппировав их в пары from-to.Затем разделите вектор отсутствующего значения на группы var и 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
1 голос
/ 17 апреля 2019

Заимствование идеи из Как сгладить / объединить перекрывающиеся периоды времени , но вместо этого использовать 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))]

Надеюсь, это достаточно быстро для вашего фактического набора данных с 100 млн.целые числа.

...