¿Cómo dividir un vector en grupos de secuencias regulares y consecutivas?

Question

Tengo un vector, tal como c(1, 3, 4, 5, 9, 10, 17, 29, 30) y me gustaría para agrupar elementos el 'vecinos' que forman una secuencia regular, consecutivo en un vector desigual resulta en:

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

código Naive (de un programador ex-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) 
} 

Ahora entiendo que

a) R no es C (a pesar de las llaves)
b) las variables globales son pura maldad
c) que es una forma terriblemente ineficiente de alcanzar el resultado

, por lo que cualquier soluciones son mejores Bienvenido.

Answer 1

se podría definir los puntos de corte con facilidad:

which(diff(v) != 1) 

Con base en esa oportunidad:

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]] 

que se traduce en:

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

[[2]] 
[1] 3 4 5 

[[3]] 
[1] 9 10 

[[4]] 
[1] 17 

[[5]] 
[1] 29 30 

Este algoritmo no es una agradable pero podrías escribir un código mucho más limpio basado en diff :) ¡Buena suerte!

Answer 2

daroczig escribe "se podría escribir un código mucho más limpio basado en diff" ...

Aquí hay una manera:

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

EDITAR (tiempos añadidos):

Tommy descubierto que esto podría sea ​​más rápido teniendo cuidado con los tipos; La razón por la que se hizo más rápido es que split es más rápido en enteros, y en realidad es aún más rápido en factores.

Aquí está la solución de Joshua; el resultado del cumsum es numérico porque está siendo c 'd con 1, por lo que es el más lento.

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

Sólo c ing con 1L lo que el resultado es un número entero que lo acelera considerablemente.

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

Esta es la solución de Tommy, para referencia; también se divide en un número entero.

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

Aquí está mi solución original; también se está dividiendo en un número entero.

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

Aquí es Joshua, con el resultado de convertir en un entero antes de la 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 

Todas las versiones que split en un vector de número entero son sobre el mismo; podría ser aún más rápido si ese vector entero ya fuera un factor, ya que la conversión de un número entero a un factor en realidad lleva aproximadamente la mitad del tiempo. Aquí lo transformo en un factor directamente; esto no se recomienda en general porque depende de la estructura de la clase de factor. Esto se hace aquí solo con fines de comparación.

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

Hacer un uso intensivo de algunos modismos 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 4

Se puede crear un data.frame y asignar los elementos a grupos utilizando diff, ifelse y cumsum, a continuación, agregar el uso de 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

Joshua y Aaron fueron acertados. Sin embargo, su código aún se puede hacer más de dos veces más rápido mediante el uso cuidadoso de los tipos, números enteros y lógicos correctos:

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