Encuentra secuencia en IEnumerable <T> usando LINQ

Question

¿Cuál es la forma más eficiente para encontrar una secuencia dentro de un IEnumerable<T> usando LINQ

Quiero ser capaz de crear un método de extensión que permite que la siguiente llamada:

int startIndex = largeSequence.FindSequence(subSequence) 

La coincidencia debe ser adyacente y en orden.

Answer 1

ACTUALIZACIÓN: Dada la clarificación de la pregunta mi respuesta a continuación no es tan aplicable. Dejándolo para propósitos históricos.

Es probable que desee utilizar mySequence.Where(). Luego, la clave es optimizar el predicado para que funcione bien en su entorno. Esto puede variar bastante según sus requisitos y patrones de uso típicos.

Es muy posible que lo que funciona bien para colecciones pequeñas no se adapte bien para colecciones mucho más grandes dependiendo del tipo T.

Por supuesto, si el uso del 90% es para colecciones pequeñas, entonces la optimización para la gran colección atípica parece un poco YAGNI.

Answer 2

El código que dice que desea utilizar no es LINQ, por lo que no veo por qué debe implementarse con LINQ.

Esto es esencialmente el mismo problema que la búsqueda de subcadenas (de hecho, una enumeración donde el orden es significativo es una generalización de "cadena").

Dado que la informática ha considerado este problema con frecuencia durante mucho tiempo, usted se pone de pie sobre los hombros de los gigantes.

Algunos puntos de partida razonables son:

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

http://en.wikipedia.org/wiki/Rabin-karp

Aunque sólo el pseudocódigo en los artículos de Wikipedia es suficiente para el puerto de C# con bastante facilidad. Mire las descripciones del rendimiento en diferentes casos y decida qué casos es más probable que encuentre su código.

Answer 3

Aquí hay una implementación de un algoritmo que encuentra una subsecuencia en una secuencia. Que se llama el método IndexOfSequence, ya que hace que el intento más explícito y es similar al método existente IndexOf:

public static class ExtensionMethods 
{ 
    public static int IndexOfSequence<T>(this IEnumerable<T> source, IEnumerable<T> sequence) 
    { 
     return source.IndexOfSequence(sequence, EqualityComparer<T>.Default); 
    } 

    public static int IndexOfSequence<T>(this IEnumerable<T> source, IEnumerable<T> sequence, IEqualityComparer<T> comparer) 
    { 
     var seq = sequence.ToArray(); 

     int p = 0; // current position in source sequence 
     int i = 0; // current position in searched sequence 
     var prospects = new List<int>(); // list of prospective matches 
     foreach (var item in source) 
     { 
      // Remove bad prospective matches 
      prospects.RemoveAll(k => !comparer.Equals(item, seq[p - k])); 

      // Is it the start of a prospective match ? 
      if (comparer.Equals(item, seq[0])) 
      { 
       prospects.Add(p); 
      } 

      // Does current character continues partial match ? 
      if (comparer.Equals(item, seq[i])) 
      { 
       i++; 
       // Do we have a complete match ? 
       if (i == seq.Length) 
       { 
        // Bingo ! 
        return p - seq.Length + 1; 
       } 
      } 
      else // Mismatch 
      { 
       // Do we have prospective matches to fall back to ? 
       if (prospects.Count > 0) 
       { 
        // Yes, use the first one 
        int k = prospects[0]; 
        i = p - k + 1; 
       } 
       else 
       { 
        // No, start from beginning of searched sequence 
        i = 0; 
       } 
      } 
      p++; 
     } 
     // No match 
     return -1; 
    } 
} 

no he probado completamente, por lo que todavía puede contener errores. Acabo de hacer algunas pruebas en casos de esquina conocidos para asegurarme de que no estaba cayendo en trampas obvias. Parece funcionar bien hasta ahora ...

Creo que la complejidad está cerca de O (n), pero no soy un experto en la notación Big O, así que podría estar equivocado ... al menos solo enumera el secuencia fuente una vez, sin volver atrás, por lo que debe ser razonablemente eficiente.

Answer 4

entiendo que esto es una cuestión de edad, pero necesitaba este método exacto y lo he escrito arriba, así:

public static int ContainsSubsequence<T>(this IEnumerable<T> elements, IEnumerable<T> subSequence) where T: IEquatable<T> 
{ 
    return ContainsSubsequence(elements, 0, subSequence); 
} 

private static int ContainsSubsequence<T>(IEnumerable<T> elements, int index, IEnumerable<T> subSequence) where T: IEquatable<T> 
{ 
    // Do we have any elements left? 
    bool elementsLeft = elements.Any(); 

    // Do we have any of the sub-sequence left? 
    bool sequenceLeft = subSequence.Any(); 

    // No elements but sub-sequence not fully matched 
    if (!elementsLeft && sequenceLeft) 
     return -1; // Nope, didn't match 

    // No elements of sub-sequence, which means even if there are 
    // more elements, we matched the sub-sequence fully 
    if (!sequenceLeft) 
     return index - subSequence.Count(); // Matched! 

    // If we didn't reach a terminal condition, 
    // check the first element of the sub-sequence against the first element 
    if (subSequence.First().Equals(e.First())) 
     // Yes, it matched - move onto the next. Consume (skip) one element in each 
     return ContainsSubsequence(elements.Skip(1), index + 1 subSequence.Skip(1)); 
    else 
     // No, it didn't match. Try the next element, without consuming an element 
     // from the sub-sequence 
     return ContainsSubsequence(elements.Skip(1), index + 1, subSequence); 
} 

Actualizado a no sólo la devolución si la sub-secuencia igualada, pero donde se inició en la secuencia original.

Este es un método de extensión en IEnumerable, completamente vago, termina antes de tiempo y está mucho más modificado que la respuesta actualmente votada. Advertido, sin embargo (como señala @ wai-ha-lee) es recursivo y crea un lote de enumeradores. Úselo cuando corresponda (rendimiento/memoria). Esto estuvo bien para mis necesidades, pero YMMV.

Answer 5

Puede usar esta biblioteca llamada Sequences para hacer eso (descargo de responsabilidad: soy el autor).

Tiene un método IndexOfSlice que hace exactamente lo que necesita - es un implementation del Knuth-Morris-Pratt algorithm.

int startIndex = largeSequence.AsSequence().IndexOfSlice(subSequence);