如何在R中确定长序列中的最长连续序列

Question

我有一个序列，用作玩具示例。如何确定最长连续子序列？现在，我能够找到断点位置，但如何获取值呢？

DT <- data.table(X = c(3:7, 16:18, 22:29, 31:36))
DT[,Y:=(shift(.SD,type = "lag", fill = -1))][,Y:= Y-X]
with(DT, which(Y !=-1)) 

我希望找到的是子序列的值，在此情况下应为c(22, 23, 24, 25, 26, 27, 28, 29)。

- Grec001

---

我不确定你期望的输出是什么？不知道 DT[with(DT, which(Y !=-1)),] 是否是你想要的？ - deepseefan

你想要什么结果？也许可以检查“cgwtools”包中的seqle函数。 - A5C1D2H2I1M1N2O1R2T1

供参考，我想到的方法类似于 library(cgwtools); inverse.seqle(setDT(seqle(DT$X))[lengths == max(lengths)]) 或者 library(cgwtools); inverse.seqle(setDT(seqle(DT$X))[which.max(lengths)])，具体取决于您如何处理多个最长序列。 - A5C1D2H2I1M1N2O1R2T1

Answer 1

不确定您的期望输出是什么，但在这里我们将data.table中每个序列的长度加起来。

library(data.table)
DT[, length := .N, by = cumsum(c(1, diff(X) != 1))]

DT
#     X length
# 1:  3      5
# 2:  4      5
# 3:  5      5
# 4:  6      5
# 5:  7      5
# 6: 16      3
# 7: 17      3
# 8: 18      3
# 9: 22      8
#10: 23      8
#11: 24      8
#12: 25      8
#13: 26      8
#14: 27      8
#15: 28      8
#16: 29      8
#17: 31      6
#18: 32      6
#19: 33      6
#20: 34      6
#21: 35      6
#22: 36      6
#     X length

如果您只想提取最大值，则可以执行以下操作：

DT[length == max(length), ]

#    X length
#1: 22      8
#2: 23      8
#3: 24      8
#4: 25      8
#5: 26      8
#6: 27      8
#7: 28      8
#8: 29      8

- Ronak Shah

Answer 2

查找最长序列及其内容的方法...

ls <- split(DT$X, cumsum(c(TRUE, diff(DT$X) != 1)))
ls[[which.max(lengths(ls))]]

And identifying them ...

DT[X %in% ls[[which.max(lengths(ls))]], match := TRUE]

     X  Y match
 1:  3 -1    NA
 2:  4  3    NA
 3:  5  4    NA
 4:  6  5    NA
 5:  7  6    NA
 6: 16  7    NA
 7: 17 16    NA
 8: 18 17    NA
 9: 22 18  TRUE
10: 23 22  TRUE
11: 24 23  TRUE
12: 25 24  TRUE
13: 26 25  TRUE
14: 27 26  TRUE
15: 28 27  TRUE
16: 29 28  TRUE
17: 31 29    NA
18: 32 31    NA
19: 33 32    NA
20: 34 33    NA
21: 35 34    NA
22: 36 35    NA
     X  Y match

- Khaynes

---

真的是一种聪明的方式！ - Grec001

Answer 3

另一个选项，当数据量很大时应该更快：

DT[DT[, {
    rl <- cumsum(c(1L, diff(X)>1L))
    rw <- rowid(rl)
    .I[rl==rl[which.max(rw)]]}]]

计时代码：

set.seed(0L)
nr <- 1e7
ngap <- nr/2
DT <- data.table(X=sample(nr, ngap))
setorder(DT, X)

mtd0 <- function() {
    DT[, length := .N, by = cumsum(c(1, diff(X) != 1))][length == max(length), X]
}

mtd1 <- function() {
    ls <- split(DT$X, cumsum(c(TRUE, diff(DT$X) != 1)))
    DT[X %in% ls[[which.max(lengths(ls))]], X]
}

mtd2 <- function() {
    DT[DT[, {
        rl <- cumsum(c(1L, diff(X)>1L))
        rw <- rowid(rl)
        .I[rl==rl[which.max(rw)]]}], X]
}

bench::mark(mtd0(), mtd1(), mtd2(), check=FALSE)

输出：

> mtd0()
[1] 4622514 4622515 4622516 4622517 4622518 4622519 4622520 4622521 4622522 4622523 4622524 4622525 4622526 4622527 4622528 4622529 4622530 4622531 4622532
[20] 4622533 4622534 4622535 8390357 8390358 8390359 8390360 8390361 8390362 8390363 8390364 8390365 8390366 8390367 8390368 8390369 8390370 8390371 8390372
[39] 8390373 8390374 8390375 8390376 8390377 8390378
> mtd1()
[1] 4622514 4622515 4622516 4622517 4622518 4622519 4622520 4622521 4622522 4622523 4622524 4622525 4622526 4622527 4622528 4622529 4622530 4622531 4622532
[20] 4622533 4622534 4622535
> mtd2()
[1] 4622514 4622515 4622516 4622517 4622518 4622519 4622520 4622521 4622522 4622523 4622524 4622525 4622526 4622527 4622528 4622529 4622530 4622531 4622532
[20] 4622533 4622534 4622535

时间：

# A tibble: 3 x 13
  expression      min   median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result     memory                time     gc              
  <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list>     <list>                <list>   <list>          
1 mtd0()        1.34s    1.34s     0.747     363MB     1.49     1     2      1.34s <int [44]> <df[,3] [42 x 3]>     <bch:tm> <tibble [1 x 3]>
2 mtd1()        2.13s    2.13s     0.470     548MB     1.88     1     4      2.13s <int [22]> <df[,3] [34,671 x 3]> <bch:tm> <tibble [1 x 3]>
3 mtd2()     642.91ms 642.91ms     1.56      343MB     4.67     1     3   642.91ms <int [22]> <df[,3] [29 x 3]>     <bch:tm> <tibble [1 x 3]>

- chinsoon12

---

非常鼓舞人心。似乎`[,{}]'为进程创建了一个独立的命名空间，比即时计算更有效率。非常感谢。 - Grec001