c# - Rendimiento de Skip(y funciones similares, como Take)

performance linq

Question

Acabo de echar un vistazo al código fuente de los métodos de extensión Skip / Take de .NET Framework (en el tipo IEnumerable<T> ) y descubrí que la implementación interna está funcionando con el método GetEnumerator :

// .NET framework
    public static IEnumerable<TSource> Skip<TSource>(this IEnumerable<TSource> source, int count)  
    {
        if (source == null) throw Error.ArgumentNull("source"); 
        return SkipIterator<TSource>(source, count); 
    }

    static IEnumerable<TSource> SkipIterator<TSource>(IEnumerable<TSource> source, int count) 
    {
        using (IEnumerator<TSource> e = source.GetEnumerator()) 
        {
            while (count > 0 && e.MoveNext()) count--;
            if (count <= 0) 
            { 
                while (e.MoveNext()) yield return e.Current;
            } 
        } 
    }

Supongamos que tengo un IEnumerable<T> con 1000 elementos (el tipo subyacente es List<T> ). ¿Qué pasa si estoy haciendo list.Skip (990) .Take (10)? ¿Recorrerá los primeros 990 elementos antes de tomar los últimos diez? (Así es como lo entiendo). Si es así, entonces no entiendo por qué Microsoft no implementó el método Skip esta manera:

    // Not tested... just to show the idea
    public static IEnumerable<T> Skip<T>(this IEnumerable<T> source, int count)
    {
        if (source is IList<T>)
        {
            IList<T> list = (IList<T>)source;
            for (int i = count; i < list.Count; i++)
            {
                yield return list[i];
            }
        }
        else if (source is IList)
        {
            IList list = (IList)source;
            for (int i = count; i < list.Count; i++)
            {
                yield return (T)list[i];
            }
        }
        else
        {
            // .NET framework
            using (IEnumerator<T> e = source.GetEnumerator())
            {
                while (count > 0 && e.MoveNext()) count--;
                if (count <= 0)
                {
                    while (e.MoveNext()) yield return e.Current;
                }
            }
        }
    }

De hecho, lo hicieron para el método Count , por ejemplo ...

    // .NET Framework...
    public static int Count<TSource>(this IEnumerable<TSource> source) 
    {
        if (source == null) throw Error.ArgumentNull("source");

        ICollection<TSource> collectionoft = source as ICollection<TSource>; 
        if (collectionoft != null) return collectionoft.Count;

        ICollection collection = source as ICollection; 
        if (collection != null) return collection.Count; 

        int count = 0;
        using (IEnumerator<TSource> e = source.GetEnumerator())
        { 
            checked 
            {
                while (e.MoveNext()) count++;
            }
        } 
        return count;
    } 

Entonces, ¿cuál es la razón?

Answer 1

Como mencionó ledbutter, cuando Jon Skeet volvió a implementar Linq , mencionó que una optimización como su Skip "no detectaría el caso en el que la fuente se modificó entre iteraciones". Puede cambiar su código a lo siguiente para que verifique ese caso. Lo hace llamando a MoveNext() en el enumerador de la colección, aunque no use e.Current , de modo que el método se lance si la colección cambia.

Por supuesto, esto elimina una parte importante de la optimización: que el enumerador debe crearse, avanzar parcialmente y eliminarse, pero aún así tiene el beneficio de que no es necesario pasar inútilmente por los primeros objetos de count . Y puede ser confuso que tenga un e. e.Current que no es útil, ya que apunta a la list[i - count] lugar de la list[i] .

public static IEnumerable<T> Skip<T>(this IEnumerable<T> source, int count)
{
    using (IEnumerator<T> e = source.GetEnumerator())
    {
        if (source is IList<T>)
        {
            IList<T> list = (IList<T>)source;
            for (int i = count; i < list.Count; i++)
            {
                e.MoveNext();
                yield return list[i];
            }
        }
        else if (source is IList)
        {
            IList list = (IList)source;
            for (int i = count; i < list.Count; i++)
            {
                e.MoveNext();
                yield return (T)list[i];
            }
        }
        else
        {
            // .NET framework
            while (count > 0 && e.MoveNext()) count--;
            if (count <= 0)
            {
                while (e.MoveNext()) yield return e.Current;
            }
        }
    }
}

Answer 2

En el excelente tutorial de Jon Skeet que reimplementa Linq , él discute (brevemente) esa pregunta:

Aunque la mayoría de estas operaciones no se pueden optimizar sensiblemente, tendría sentido optimizar Omitir cuando la fuente implemente IList. Podemos omitir la omisión, por así decirlo, e ir directamente al índice apropiado. Esto no detectaría el caso en el que se modificó la fuente entre iteraciones, lo que puede ser una razón por la que no está implementado en el marco, que yo sepa.

Esa parece ser una razón razonable para postergar esa optimización, pero estoy de acuerdo en que, para casos específicos, puede valer la pena hacer esa optimización si puede garantizar que su fuente no pueda ser modificada.

Answer 3

Supongo que querían lanzar InvalidOperationException "La colección se modificó ..." cuando la colección subyacente se modifica mientras tanto en otro hilo. Tu versión no hace eso. Dará resultados terribles.

Esa es la práctica estándar que MSFT está siguiendo en todo .Net framework en todas las Colecciones, que no es seguro para subprocesos (aunque algunos son excepcionales).