Comment partitionner un vecteur en groupes de séquences consécutives régulières?

Question

j'ai un vecteur, tel c(1, 3, 4, 5, 9, 10, 17, 29, 30) et je souhaite regrouper les éléments « voisins » qui forment une séquence régulière, consécutive à un vecteur résultant en lambeaux:

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

Code Naive (d'un programmateur 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) 
} 

Maintenant, je comprends que

a) R n'est pas C (malgré les accolades)
b) les variables globales sont mal pur
c) qui est une façon terriblement inefficace d'obtenir le résultat

, donc de meilleures solutions sont Bienvenue.

Answer 1

Vous pouvez définir les points de coupure facilement:

which(diff(v) != 1) 

Basé sur cette tentative:

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

qui se traduit par:

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

[[2]] 
[1] 3 4 5 

[[3]] 
[1] 9 10 

[[4]] 
[1] 17 

[[5]] 
[1] 29 30 

Cet algorithme est pas nice one mais vous pouvez écrire beaucoup plus de code basé sur diff :) Bonne chance!

Answer 2

daroczig écrit "vous pouvez écrire un code plus propre lot basé sur diff" ...

est ici une façon:

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

EDIT (timings ajoutés):

Tommy a découvert cela pourrait être plus rapide en faisant attention aux types; la raison pour laquelle il est devenu plus rapide est que split est plus rapide sur les entiers, et est encore plus rapide sur les facteurs.

Voici la solution de Joshua; le résultat du cumsum est un numérique car il est c 'd avec 1, donc c'est le plus lent.

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

Juste c ing avec 1L de sorte que le résultat est un nombre entier accélère considérablement vers le haut.

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

Ceci est la solution de Tommy, pour référence; c'est aussi se dédoubler sur un nombre entier.

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

Voici ma solution originale; il est également divisé sur un nombre entier.

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

est ici Joshua, avec le résultat converti en un nombre entier avant 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 

Toutes les versions split sur un vecteur entier sont à peu près les mêmes; cela pourrait être encore plus rapide si ce vecteur entier était déjà un facteur, car la conversion d'entier en facteur prend environ la moitié du temps. Ici, je le fais en un facteur directement; ceci n'est pas recommandé en général car cela dépend de la structure de la classe de facteurs. C'est fait ici à des fins de comparaison seulement.

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

Faire un usage intensif de certains idiomes 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

Vous pouvez créer un data.frame et affecter les éléments à des groupes utilisant diff, ifelse et cumsum, puis agréger en utilisant 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 et Aaron étaient sur place. Cependant, leur code peut encore être rendu plus de deux fois plus rapide par une utilisation prudente des types corrects, entiers et logiques:

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