Récupère les index d'un vecteur de nombres dans un autre vecteur

Question

Supposons que nous ayons le vecteur suivant:

 v <- c(2,2,3,5,8,0,32,1,3,12,5,2,3,5,8,33,1)
 

Étant donné une séquence de nombres, par exemple c(2,3,5,8) , j'essaye de trouver quelle est la position de cette séquence de nombres dans le vecteur v . Le résultat que j'attends est quelque chose comme:

 FALSE TRUE TRUE TRUE TRUE FALSE FALSE FALSE FALSE FALSE FALSE TRUE TRUE TRUE TRUE FALSE FALSE 
 

J'essaie d'utiliser which(v == c(2,3,5,8)) mais cela ne me donne pas ce que je recherche.

Merci d'avance.

Answer 1

En utilisant la base R, vous pouvez effectuer les opérations suivantes:

 v <- c(2,2,3,5,8,0,32,1,3,12,5,2,3,5,8,33,1)
x <- c(2,3,5,8)

idx <- which(v == x[1])
idx[sapply(idx, function(i) all(v[i:(i+(length(x)-1))] == x))]
# [1]  2 12
 

Cela vous indique que la séquence exacte apparaît deux fois, en commençant aux positions 2 et 12 de votre vecteur v .

Il vérifie d'abord les positions de départ possibles, c'est-à-dire où v est égal à la première valeur de x , puis passe en revue ces positions pour vérifier si les valeurs après ces positions sont également égales aux autres valeurs de x .

Answer 2

Deux autres approches à l'aide de l' shift-fonction trom data.table:

library(data.table)

# option 1
which(rowSums(mapply('==',
                     shift(v, type = 'lead', n = 0:(length(x) - 1)),
                     x)
              ) == length(x))

# option 2
which(Reduce("+", Map('==',
                      shift(v, type = 'lead', n = 0:(length(x) - 1)),
                      x)
             ) == length(x))

les deux donnent:

[1]  2 12

Afin d'en obtenir un vecteur des positions correspondantes:

l <- length(x)
w <- which(Reduce("+", Map('==',
                           shift(v, type = 'lead', n = 0:(l - 1)),
                           x)
                  ) == l)
rep(w, each = l) + 0:(l-1)

ce qui donne:

[1]  2  3  4  5 12 13 14 15

L'indice de référence qui a été présenté précédemment dans cette réponse a été déplacé vers un autre wiki de la communauté réponse.

---

Données utilisées:

v <- c(2,2,3,5,8,0,32,1,3,12,5,2,3,5,8,33,1)
x <- c(2,3,5,8)

Answer 3

Vous pouvez utiliser rollapply() de zoo

v <- c(2,2,3,5,8,0,32,1,3,12,5,2,3,5,8,33,1)
x <- c(2,3,5,8)

library("zoo")
searchX <- function(x, X) all(x==X)
rollapply(v, FUN=searchX, X=x, width=length(x))

Le résultat TRUEvous montre le début de la séquence.
Le code peut être simplifié à l' rollapply(v, length(x), identical, x) (merci à G. Grothendieck):

set.seed(2)
vl <- as.numeric(sample(1:10, 1e6, TRUE))
# vm <- vl[1:1e5]
# vs <- vl[1:1e4]
x <- c(2,3,5)

library("zoo")
searchX <- function(x, X) all(x==X)
i1 <- rollapply(vl, FUN=searchX, X=x, width=length(x))
i2 <- rollapply(vl, width=length(x), identical, y=x)

identical(i1, i2)

Pour l'utilisation de identical() les deux arguments doivent être du même type (num et int sont pas les mêmes).
Si nécessaire, == contraindre les int de num; identical() n'a pas de contrainte.

Answer 4

Je pense que le bouclage devrait être efficace:

 w = seq_along(v)
for (i in seq_along(x)) w = w[v[w+i-1L] == x[i]]

w 
# [1]  2 12
 

Cela devrait être accessible en écriture en C ++ en suivant l' approche @SymbolixAU pour plus de vitesse.

Une comparaison de base:

 # create functions for selected approaches
redjaap <- function(v,x)
  which(Reduce("+", Map('==', shift(v, type = 'lead', n = 0:(length(x) - 1)), x)) == length(x))
loop <- function(v,x){
  w = seq_along(v)
  for (i in seq_along(x)) w = w[v[w+i-1L] == x[i]]
  w
}

# check consistency
identical(redjaap(v,x), loop(v,x))
# [1] TRUE

# check speed
library(microbenchmark)
vv <- rep(v, 1e4)
microbenchmark(redjaap(vv,x), loop(vv,x), times = 100)
# Unit: milliseconds
#            expr      min       lq      mean   median       uq       max neval cld
#  redjaap(vv, x) 5.883809 8.058230 17.225899 9.080246 9.907514  96.35226   100   b
#     loop(vv, x) 3.629213 5.080816  9.475016 5.578508 6.495105 112.61242   100  a 

# check consistency again
identical(redjaap(vv,x), loop(vv,x))
# [1] TRUE
 

Answer 5

Voici deux Rcpp solutions. Le premier renvoie à l'emplacement de v qui est la position de départ de la séquence.

library(Rcpp)

v <- c(2,2,3,5,8,0,32,1,3,12,5,2,3,5,8,33,1)
x <- c(2,3,5,8)

cppFunction('NumericVector SeqInVec(NumericVector myVector, NumericVector mySequence) {

    int vecSize = myVector.size();
    int seqSize = mySequence.size();
    NumericVector comparison(seqSize);
    NumericVector res(vecSize);

    for (int i = 0; i < vecSize; i++ ) {

        for (int j = 0; j < seqSize; j++ ) {
                comparison[j] = mySequence[j] == myVector[i + j];
        }

        if (sum(comparison) == seqSize) {
            res[i] = 1;
        }else{
            res[i] = 0;
        }
    }

    return res;

    }')

SeqInVec(v, x)
#[1] 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0

---

Cette deuxième renvoie les valeurs d'index (comme pour les autres réponses) de chaque appariés entrée dans l'ordre.

cppFunction('NumericVector SeqInVec(NumericVector myVector, NumericVector mySequence) {

  int vecSize = myVector.size();
  int seqSize = mySequence.size();
  NumericVector comparison(seqSize);
  NumericVector res(vecSize);
  int foundCounter = 0;

  for (int i = 0; i < vecSize; i++ ) {

    for (int j = 0; j < seqSize; j++ ) {
      comparison[j] = mySequence[j] == myVector[i + j];
    }

    if (sum(comparison) == seqSize) {
      for (int j = 0; j < seqSize; j++ ) {
        res[foundCounter] = i + j + 1;
        foundCounter++;
      }
    }
  }

  IntegerVector idx = seq(0, (foundCounter-1));
  return res[idx];
}')

SeqInVec(v, x)
# [1]  2  3  4  5 12 13 14 15

---

L'optimisation de la

Comme @MichaelChirico souligne dans son commentaire, des optimisations peuvent être faites. Par exemple, si nous savons la première entrée dans la séquence ne correspond pas à une valeur du vecteur, nous n'avons pas besoin de faire le reste de la comparaison

cppFunction('NumericVector SeqInVecOpt(NumericVector myVector, NumericVector mySequence) {

  int vecSize = myVector.size();
  int seqSize = mySequence.size();
  NumericVector comparison(seqSize);
  NumericVector res(vecSize);
  int foundCounter = 0;

  for (int i = 0; i < vecSize; i++ ) {

    if (myVector[i] == mySequence[0]) {
        for (int j = 0; j < seqSize; j++ ) {
          comparison[j] = mySequence[j] == myVector[i + j];
        }

        if (sum(comparison) == seqSize) {
          for (int j = 0; j < seqSize; j++ ) {
            res[foundCounter] = i + j + 1;
            foundCounter++;
          }
        }
    }
  }

  IntegerVector idx = seq(0, (foundCounter-1));
  return res[idx];
}')

La réponse avec des indicateurs montre les performances de ces approches