c# - que - firstordefault linq default value

Buscar secuencia en IEnumerable<T> usando Linq

Question

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

Deseo poder crear un método de extensión que permita la siguiente llamada:

int startIndex = largeSequence.FindSequence(subSequence)

El partido debe ser adyacente y en orden.

Answer 1

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

Este 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").

Como 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

Incluso solo el pseudocódigo en los artículos de wikipedia es suficiente para portar a 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 2

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

Probablemente quiera usar 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 a colecciones mucho más grandes dependiendo del tipo T.

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

Answer 3

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

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 lo probé por completo, por lo que aún podría contener errores. Acabo de hacer algunas pruebas en casos de esquina conocidos para asegurarme de que no estaba cayendo en trampas obvias. Parece que funciona 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 la secuencia de origen una vez, sin volver atrás, por lo que debería ser razonablemente eficiente.

Answer 4

Entiendo que esta es una pregunta antigua, pero necesitaba este método exacto y lo escribí 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 para que no solo regrese si la subsecuencia coincide, sino dónde comenzó 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 que se votó hasta el momento. Advertido, sin embargo (como señala @ wai-ha-lee) es recursivo y crea muchos 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 una implementación del algoritmo Knuth-Morris-Pratt .

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