Trova sequenza in IEnumerable <T> utilizzando Linq

Question

Qual è il modo più efficace per trovare una sequenza all'interno di un IEnumerable<T> utilizzando LINQ

voglio essere in grado di creare un metodo di estensione che permette la seguente chiamata:

int startIndex = largeSequence.FindSequence(subSequence) 

La partita deve essere adiacente e in ordine.

Answer 1

UPDATE: Dato il chiarimento della questione la mia risposta qui di seguito non è seconda dei casi. Lasciandolo per scopi storici.

Probabilmente si desidera utilizzare mySequence.Where(). Quindi la chiave è ottimizzare il predicato per funzionare bene nel proprio ambiente. Questo può variare un po 'a seconda delle esigenze e dei modelli di utilizzo tipici.

È del tutto possibile che ciò che funziona bene per le piccole raccolte non si adatta bene a raccolte molto più grandi a seconda del tipo T.

Ovviamente, se l'utilizzo del 90% è per piccole raccolte, quindi l'ottimizzazione per le precedenti grande raccolta sembra un po 'YAGNI.

Answer 2

Il codice che dici di voler utilizzare non è LINQ, quindi non vedo perché debba essere implementato con LINQ.

Questo è essenzialmente lo stesso problema della ricerca di sottostringhe (anzi, un'enumerazione in cui l'ordine è significativo è una generalizzazione di "stringa").

Dal momento che l'informatica ha considerato questo problema frequentemente per molto tempo, così si arriva a stare sulle spalle dei giganti.

alcuni punti di partenza sono ragionevoli:

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

Anche solo il pseudocodice negli articoli di Wikipedia è sufficiente a porta per C# abbastanza facilmente. Guarda le descrizioni delle prestazioni in diversi casi e decidi quali sono i casi più probabili da incontrare nel tuo codice.

Answer 3

Ecco un'implementazione di un algoritmo che trova una sottosequenza in una sequenza. Ho chiamato il metodo IndexOfSequence, perché rende l'intento più esplicito ed è simile al metodo esistente 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; 
    } 
} 

non ho la prova pienamente, quindi potrebbe ancora contenere bug. Ho fatto solo alcuni test su casi d'angolo noti per assicurarmi che non stavo cadendo in trappole evidenti. Sembra funzionare fino a oggi ...

Penso che la complessità sia vicina a O (n), ma non sono un esperto di notazione Big O quindi potrei sbagliarmi ... almeno enumera solo il sequenza sorgente una volta, senza mai tornare indietro, quindi dovrebbe essere ragionevolmente efficiente.

Answer 4

Capisco che questo è una vecchia questione, ma avevo bisogno di questo metodo esatto e l'ho scritto in questo modo:

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); 
} 

Aggiornato non solo di ritorno se il sub-sequenza abbinato, ma dove ha cominciato a la sequenza originale.

Questo è un metodo di estensione su IEnumerable, completamente pigro, viene terminato anticipatamente ed è molto più lineare rispetto alla risposta attualmente votata. Bewarned, tuttavia (come indicato da @ wai-ha-lee), lo è ricorsivo e crea un lotto di enumeratori. Usalo laddove applicabile (prestazioni/memoria). Questo andava bene per i miei bisogni, ma YMMV.

Answer 5

È possibile utilizzare questa libreria denominata Sequences per farlo (dichiarazione di non responsabilità: sono l'autore).

Ha un metodo IndexOfSlice che fa esattamente quello che ti serve: è un implementation dello Knuth-Morris-Pratt algorithm.

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