c# - ¿Por qué Enumerable.Single() itera todos los elementos, incluso cuando ya se ha encontrado más de un elemento?

linq .net-4.0

Question

Al perfilar una de nuestras aplicaciones, descubrimos una desaceleración misteriosa en algún código donde llamábamos Enumerable.Single(source, predicate) para una colección grande que tenía más de un elemento que coincidía con el predicado cerca del inicio de la colección.

La investigación reveló que la implementación de Enumerable.Single() es la siguiente:

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) 
{
        TSource result = default(TSource);
        long count = 0;
        // Note how this always iterates through ALL the elements:
        foreach (TSource element in source) { 
            if (predicate(element)) {
                result = element;
                checked { count++; }
            }
        }
        switch (count) {
            case 0: throw Error.NoMatch();
            case 1: return result;
        }
        throw Error.MoreThanOneMatch();
    }

Esa implementación se repetirá en todos los elementos de la secuencia, incluso si más de un elemento ya ha coincidido con el predicado.

La siguiente implementación parecería dar los mismos resultados:

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    TSource result = default(TSource);
    long count = 0;
    foreach (TSource element in source) {
        if (predicate(element)) {
            if (count == 1) // Exit loop immediately if more than one match found.
                throw Error.MoreThanOneMatch();

            result = element;
            count++; // "checked" is no longer needed.
        }
    }

    if (count == 0)
        throw Error.NoMatch();

    return result;
}

¿Alguien sabe por qué la implementación real no usa esta obvia optimización? ¿Se me escapa algo? (No puedo imaginar que una optimización tan obvia sea pasada por alto, y por lo tanto, debe haber alguna razón concreta para ello).

(Nota: me doy cuenta de que esta pregunta puede atraer respuestas que son opiniones; espero respuestas que proporcionen razones concretas para iterar todos los elementos. Si la respuesta es en realidad "porque los diseñadores no pensaron que tal optimización fuera necesaria", entonces esta pregunta no tiene respuesta y supongo que debería borrarla ...)

Para comparar, mire la implementación de Single() que no tiene un predicado:

public static TSource Single<TSource>(this IEnumerable<TSource> source) 
{
    IList<TSource> list = source as IList<TSource>;
    if (list != null) {
        switch (list.Count) {
            case 0: throw Error.NoElements();
            case 1: return list[0];
        }
    }
    else {
        using (IEnumerator<TSource> e = source.GetEnumerator()) {
            if (!e.MoveNext()) throw Error.NoElements();
            TSource result = e.Current;
            if (!e.MoveNext()) return result;
        }
    }
    throw Error.MoreThanOneElement();
}

En este caso, se han esforzado por agregar una optimización para IList .

Answer 1

Como han señalado las otras respuestas, se ha aplicado la optimización, pero solo me gustaría plantear la hipótesis de que lo habían hecho de esa manera, pensando originalmente que no tienen forma de garantizar que la función de predicado no tenga sentido. efectos

No estoy seguro de que realmente haya un caso en el que ese comportamiento sea usado / útil, pero es una consideración a tener en cuenta.

Answer 2

La optimización se aplicó en .NET Core

El código ahora es:

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null)
    {
        throw Error.ArgumentNull(nameof(source));
    }

    if (predicate == null)
    {
        throw Error.ArgumentNull(nameof(predicate));
    }

    using (IEnumerator<TSource> e = source.GetEnumerator())
    {
        while (e.MoveNext())
        {
            TSource result = e.Current;
            if (predicate(result))
            {
                while (e.MoveNext())
                {
                    if (predicate(e.Current))
                    {
                        throw Error.MoreThanOneMatch();
                    }
                }

                return result;
            }
        }
    }

    throw Error.NoMatch();
}

Siempre que sea posible, el código incluso comprueba si el objetivo es un IList<T> para evitar la iteración:

public static TSource Single<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull(nameof(source));
    }

    if (source is IList<TSource> list)
    {
        switch (list.Count)
        {
            case 0:
                throw Error.NoElements();
            case 1:
                return list[0];
        }
    }
    else
    {
        using (IEnumerator<TSource> e = source.GetEnumerator())
        {
            if (!e.MoveNext())
            {
                throw Error.NoElements();
            }

            TSource result = e.Current;
            if (!e.MoveNext())
            {
                return result;
            }
        }
    }

    throw Error.MoreThanOneElement();
}

ACTUALIZAR

La comprobación de la salida de Git Culge muestra que la optimización de iteración se aplicó en 2016.

La optimización IList<> se agregó hace 1 año, probablemente como parte de las optimizaciones Core 2.1

Answer 3

No parecías ser el único que pensaba eso. La implementación de .NET Core tiene una versión optimizada:

using (IEnumerator<TSource> e = source.GetEnumerator())
{
    while (e.MoveNext())
    {
        TSource result = e.Current;
        if (predicate(result))
        {
            while (e.MoveNext())
            {
                if (predicate(e.Current))
                {
                    throw Error.MoreThanOneMatch();
                }
            }

            return result;
        }
    }
}

Entonces, para responder a su pregunta: no parece haber una "buena" razón, aparte de un simple desarrollador que no está pensando en optimizar este caso de uso.