Как разбить вектор на группы регулярных последовательных последовательностей?

Question

У меня есть вектор, например c(1, 3, 4, 5, 9, 10, 17, 29, 30), и я хотел бы сгруппировать «соседние» элементы, которые образуют регулярную последовательную последовательность в рваный вектор, в результате чего:

L1: 1
L2: 3,4,5
L3: 9,10
L4: 17
L5: 29,30

Наивный код (бывшего программиста на C):

partition.neighbors <- function(v)
{
    result <<- list() #jagged array
    currentList <<- v[1] #current series

    for(i in 2:length(v))
    {
        if(v[i] - v [i-1] == 1)
        {
            currentList <<- c(currentList, v[i])
        }
        else
        {
            result <<- c(result, list(currentList))
            currentList <<- v[i] #next series
        }       
    }

    return(result)  
}

Теперь я понимаю, что

a) R не является C (несмотря на фигурные скобки)
b) глобальные переменные являются чистым злом
c) это ужасно неэффективный способдостижение результата

, поэтому любые лучшие решения приветствуются.

Answer 1

Сильное использование некоторых идиом R:

> split(v, cumsum(c(1, diff(v) != 1)))
$`1`
[1] 1

$`2`
[1] 3 4 5

$`3`
[1]  9 10

$`4`
[1] 17

$`5`
[1] 29 30

Answer 2

Дароциг пишет: «Вы можете написать много аккуратного кода на основе diff» ...

Вот один из способов:

split(v, cumsum(diff(c(-Inf, v)) != 1))

РЕДАКТИРОВАТЬ (добавлено время):

Томми обнаружил, что это может быть быстрее, если быть осторожным с типами; причина, по которой он стал быстрее, состоит в том, что split быстрее на целых числах, и на самом деле быстрее, чем на факторы

Вот решение Иисуса Навина; результат от cumsum является числовым, потому что он c 'с 1, поэтому он самый медленный.

system.time({
a <- cumsum(c(1, diff(v) != 1))
split(v, a)
})
#   user  system elapsed 
#  1.839   0.004   1.848 

Просто c с 1L, так что результат - целое число, значительно ускоряет его.

system.time({
a <- cumsum(c(1L, diff(v) != 1))
split(v, a)
})
#   user  system elapsed 
#  0.744   0.000   0.746 

Это решение Томми, для справки; оно также разбивается на целое число.

> system.time({
a <- cumsum(c(TRUE, diff(v) != 1L))
split(v, a)
})
#   user  system elapsed 
#  0.742   0.000   0.746 

Вот мое оригинальное решение; оно также разбивается на целое число.

system.time({
a <- cumsum(diff(c(-Inf, v)) != 1)
split(v, a)
})
#   user  system elapsed 
#  0.750   0.000   0.754 

Вот Джошуа с результатом, преобразованным в целое число перед split.

system.time({
a <- cumsum(c(1, diff(v) != 1))
a <- as.integer(a)
split(v, a)
})
#   user  system elapsed 
#  0.736   0.002   0.740 

Все версии, которые split на целочисленном векторе, примерно одинаковы; это могло бы быть даже быстрее, если бы этот целочисленный вектор уже был фактором, поскольку преобразование из целого числа в множитель фактически занимает примерно половину времени. Здесь я превращаю это непосредственно в фактор; это вообще не рекомендуется, потому что это зависит от структуры класса факторов. Это сделано только для сравнения.

system.time({
a <- cumsum(c(1L, diff(v) != 1))
a <- structure(a, class = "factor", levels = 1L:a[length(a)])
split(v,a)
})
#   user  system elapsed 
#  0.356   0.000   0.357 

Answer 3

Джошуа и Аарон были на месте.Тем не менее, их код может быть выполнен более чем в два раза быстрее благодаря тщательному использованию правильных типов, целых чисел и логики:

split(v, cumsum(c(TRUE, diff(v) != 1L)))

v <- rep(c(1:5, 19), len = 1e6) # Huge vector...
system.time( split(v, cumsum(c(1, diff(v) != 1))) ) # Joshua's code
# user  system elapsed 
#   2.64    0.00    2.64 

system.time( split(v, cumsum(c(TRUE, diff(v) != 1L))) ) # Modified code
# user  system elapsed 
# 1.09    0.00    1.12 

Answer 4

Вы можете создать data.frame и назначить элементы группам, используя diff, ifelse и cumsum, а затем агрегировать, используя tapply:

v.df <- data.frame(v = v)
v.df$group <- cumsum(ifelse(c(1, diff(v) - 1), 1, 0))
tapply(v.df$v, v.df$group, function(x) x)

$`1`
[1] 1

$`2`
[1] 3 4 5

$`3`
[1]  9 10

$`4`
[1] 17

$`5`
[1] 29 30

Answer 5

Вы можете легко определить точки отсечения:

which(diff(v) != 1)

На основании этой попытки:

v <- c(1,3,4,5,9,10,17,29,30)
cutpoints <- c(0, which(diff(v) != 1), length(v))
ragged.vector <- vector("list", length(cutpoints)-1)
for (i in 2:length(cutpoints)) ragged.vector[[i-1]] <- v[(cutpoints[i-1]+1):cutpoints[i]]

Что приводит к:

> ragged.vector
[[1]]
[1] 1

[[2]]
[1] 3 4 5

[[3]]
[1]  9 10

[[4]]
[1] 17

[[5]]
[1] 29 30

Этот алгоритмне очень хороший, но вы можете написать много аккуратного кода, основанного на diff :) Удачи!