[Optimizar esto]: Lento LINQ para consultar objetos

Question

Tengo esta consulta que me molesta; está encapsulado como un nuevo operador de consulta, hice dos versiones de él, tratando de ver cuál funciona mejor. Ambos actúan horriblemente.

Primer intento; estilo declarativo

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerable<α> source, int length) 
{ 
    return source.Any() 
     ? source.Take(length).Cons(source.Skip(length).Section(length)) 
     : Enumerable.Empty<IEnumerable<α>>(); 
} 

Segundo intento: imperativo estilo "yield return"

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerable<α> source, int length) 
{ 
    var fst = source.Take(length); 
    var rst = source.Skip(length); 

    yield return fst; 

    if (rst.Any()) 
     foreach (var section in rst.Section(length)) 
      yield return section; 
} 

De hecho, el segundo intento es peor, tanto en términos de facilidad de lectura, composicionalidad y en términos de velocidad.

¿Alguna pista sobre cómo optimizar esto?

Answer 1

Sospecho que el problema que tiene está relacionado con el hecho de que la enumeración que el resultado final es por lo al menos una operación O (n^2), posiblemente peor; Todavía no he trabajado todo en mi cabeza.

¿Por qué es eso? Bueno, supongamos que tiene [1, 2, 3, 4, 5, 6] y divide eso en lo que cree que es {{1, 2}, {3, 4}, {5, 6}}

Eso no es lo que has hecho. De hecho, has dividido esto en {toma los dos primeros, toma los dos primeros y descartarlos y luego toma los dos siguientes, toma los dos primeros y descarta entonces y luego toma los dos siguientes y descartarlos y luego tomar el tercero dos}

Observe cómo cada paso en el camino recalcula el resultado? Eso es porque la matriz podría estar cambiando entre las llamadas a la enumeración. LINQ fue diseñado para obtener siempre resultados actualizados; usted escribe una consulta que significa "omita las cuatro primeras e itere las siguientes dos", eso es exactamente lo que obtiene, una consulta que ejecuta ese código cuando lo enumera.

¿La secuencia original es lo suficientemente pequeña y rápida como para poder leer todo en la memoria y dividirlo todo a la vez, en lugar de intentar hacerlo de forma perezosa? Alternativamente, ¿la secuencia es indexable? Si todo lo que obtiene es un acceso directo a la secuencia y es demasiado grande o lento para leer en la memoria de una sola vez, entonces no hay mucho que pueda hacer aquí. Pero si tiene una o ambas de esas propiedades, entonces puede hacer esto al menos lineal.

Answer 2

Siempre que sea posible, intento solo iterar a través de una fuente una vez dentro de un operador. Si la fuente es algo así como el resultado de un operador Reverse(), llamando al Any, Take y Skip podría causar un gran rendimiento desagradable.

No está del todo claro lo que su operador está tratando de hacer, pero si puede hacerlo sin leer la fuente varias veces, eso bien puede ayudar, aunque dependerá en gran medida de lo que sea la entrada.

Answer 3

Si entiendo su pregunta correctamente, está tratando de crear una implementación diferida de un enumerador que divide una colección más grande de elementos en colecciones enumerables más pequeñas de elementos.

Por ejemplo, una secuencia de un millón de números podría dividirse en "secciones", cada uno produciendo solo 100 de ellos, y usted lo quiere todo de forma perezosa, es decir. no recolectar 100 elementos en una lista antes de producirlos.

Primero, sus intentos se repetirán varias veces sobre la colección, lo cual es malo, de ahí el problema de rendimiento.

Si usted está tratando de construir una aplicación pura pereza, debe tener en cuenta las siguientes cuestiones:

• Usted quiere iterar sobre la colección subyacente sola vez
• Debe volver enumerables que re-uso el enumerador subyacente
• Debe controlar que una sección que devuelve no esté completamente enumerada (por ejemplo, el código de llamada solo necesitó los primeros 50 de esos 100 elementos).

---

Editar: Antes de entrar en mi solución simplista, aquí hay algunas advertencias al respecto:

• no se puede guardar cada sección para más tarde, es decir. no puede hacer: collection.Sequence(10).ToArray() para obtener una matriz de secciones.
• No puede enumerar cada sección más de una vez, porque cuando lo hace, cambia una estructura oculta de datos subyacente.

Básicamente: Mi solución no es de uso general.Debería ir con el comentario @LBushkin sobre MoreLinq Lote si necesita esto, y dudaría en poner mi código en una biblioteca de clase, tendría que ser local donde se necesita, o renombrarse a algo que claramente lo advierta sobre la problemas con eso.

---

Aquí hay una aplicación simplista, estoy bastante seguro de que hay errores aquí, así que puede que desee ver en la implementación de una tonelada de pruebas unitarias para edgecases:

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace ConsoleApplication20 
{ 
    class SectionEnumerable<T> : IEnumerable<T> 
    { 
     private readonly IEnumerator<T> _Enumerator; 

     public SectionEnumerable(IEnumerator<T> enumerator, int sectionSize) 
     { 
      _Enumerator = enumerator; 
      Left = sectionSize; 
     } 

     public IEnumerator<T> GetEnumerator() 
     { 
      while (Left > 0) 
      { 
       Left--; 
       yield return _Enumerator.Current; 
       if (Left > 0) 
        if (!_Enumerator.MoveNext()) 
         break; 
      } 
     } 

     System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
     { 
      return GetEnumerator(); 
     } 

     public int Left { get; private set; } 
    } 

    static class SequenceExtensions 
    { 
     public static IEnumerable<IEnumerable<T>> Section<T>(this IEnumerable<T> collection, int sectionSize) 
     { 
      if (collection == null) 
       throw new ArgumentNullException("collection"); 
      if (sectionSize < 1) 
       throw new ArgumentOutOfRangeException("sectionSize"); 

      using (IEnumerator<T> enumerator = collection.GetEnumerator()) 
      { 
       while (enumerator.MoveNext()) 
       { 
        SectionEnumerable<T> enumerable = new SectionEnumerable<T>(enumerator, sectionSize); 
        yield return enumerable; 
        for (int index = 0; index < enumerable.Left; index++) 
         if (!enumerator.MoveNext()) 
          yield break; 
       } 
      } 
     } 
    } 

    class Program 
    { 
     static void Main(string[] args) 
     { 
      var sequence = Enumerable.Range(0, 100); 
      var sections = sequence.Section(10); 
      foreach (var section in sections) 
      { 
       Console.WriteLine(
        String.Join(", ", 
        section.Take(5).ToArray().Select(i => i.ToString()).ToArray())); 
      } 
      Console.ReadLine(); 
     } 
    } 
} 

Salida:

0, 1, 2, 3, 4 
10, 11, 12, 13, 14 
20, 21, 22, 23, 24 
30, 31, 32, 33, 34 
40, 41, 42, 43, 44 
50, 51, 52, 53, 54 
60, 61, 62, 63, 64 
70, 71, 72, 73, 74 
80, 81, 82, 83, 84 
90, 91, 92, 93, 94 

cosas que debe unidad de prueba:

• colección de entrada vacío no produce secciones
• Una colección que tiene el número correcto de elementos, produce sólo una sección
• Una colección que contiene una multiplum de los elementos de sección de tamaño, (es decir. 10, 20, 30, etc. número de elementos con un tamaño de sección de 5 o 10), no produce una sección vacía después de todas las esperadas
• Que es realmente vago, si enumera sobre los primeros 10- sección del elemento, pero solo los primeros 5 de la segunda sección, solo los primeros 15 elementos de la colección subyacente se enumeran en

Answer 4

¿Es esto más rápido? Debería ser así, porque solo necesita una única iteración a través de la secuencia fuente.

public static IEnumerable<IEnumerable<T>> Section<T>(
    this IEnumerable<T> source, int length) 
{ 
    return source 
     .Select((x, i) => new { Value = x, Group = i/length }) 
     .GroupBy(x => x.Group, y => y.Value); 
} 

Answer 5

Aquí hay otro enfoque no usando LINQ, que era mucho más rápido que el segundo método:

public static IEnumerable<IEnumerable<a>> Section<a>(this IEnumerable<a> source, int length) 
     { 


      var enumerator = source.GetEnumerator(); 
      var continueLoop = true; 
      do 
      { 
       var list = new List<a>(); 
       var index = 0; 
       for (int i = 0; i < length; i++) 
       { 
        if (enumerator.MoveNext()) 
        { 
         list.Add(enumerator.Current); 
         index++; 
        } 
        else 
        { 
         continueLoop = false; 
         break; 
        } 
       } 
       if (list.Count > 0) 
       { 
        yield return list; 
       } 
      } while (continueLoop); 


     } 

Answer 6

Tuve una idea hoy; mira esto

public static IEnumerable<α> Take<α>(this IEnumerator<α> iterator, int count) 
{ 
    for (var i = 0; i < count && iterator.MoveNext(); i++) 
     yield return iterator.Current; 
} 

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerator<α> iterator, int length) 
{ 
    var sct = Enumerable.Empty<α>(); 
    do 
    { 
     sct = iterator.Take(length).ToArray(); 
     if (sct.Any()) 
      yield return sct; 
    } 
    while (sct.Any()); 
} 

Esto todavía no es super-elegante, pero al menos la implementación es muy corta y legible.

Puede ser bastante interesante investigar operadores de consultas sobre IEnumerator.

Y para mayor comodidad

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerable<α> source, int length) 
{ 
    using (var iterator = source.GetEnumerator()) 
     foreach (var e in iterator.Section(length)) 
      yield return e; 
} 

Answer 7

¿Es necesario para mantener su fuente original alrededor por alguna razón, a medida que avanza? Si no es así, ¿por qué no usas la recursión y usas el estilo hd :: tl para tirar de la cabeza, pasas el tl a la llamada recursiva y en cualquier recursión de números pares fusionas los dos que tienes sentados en una sección?

Con la versión actualizada de las extensiones experimentales Ix, se puede utilizar el Window o Buffer operadores para crear un sliding window, que debe alcanzar lo que está después.

Answer 8

¿Qué tal un método de extensión

public static class IEnumerableExtensions 
{ 
    public static IEnumerable<List<T>> InSetsOf<T>(this IEnumerable<T> source, int max) 
    { 
     List<T> toReturn = new List<T>(); 
     foreach(var item in source) 
     { 
       toReturn.Add(item); 
       if (toReturn.Count == max) 
       { 
         yield return toReturn; 
         toReturn = new List<T>(); 
       } 
     } 
     if (toReturn.Any()) 
     { 
       yield return toReturn; 
     } 
    } 
} 

algunas pruebas:

[TestFixture] 
public class When_asked_to_return_items_in_sets 
{ 
    [Test] 
    public void Should_return_the_correct_number_of_sets_if_the_input_contains_a_multiple_of_the_setSize() 
    { 
     List<string> input = "abcdefghij".Select(x => x.ToString()).ToList(); 
     var result = input.InSetsOf(5); 
     result.Count().ShouldBeEqualTo(2); 
     result.First().Count.ShouldBeEqualTo(5); 
     result.Last().Count.ShouldBeEqualTo(5); 
    } 

    [Test] 
    public void Should_separate_the_input_into_sets_of_size_requested() 
    { 
     List<string> input = "abcdefghijklm".Select(x => x.ToString()).ToList(); 
     var result = input.InSetsOf(5); 
     result.Count().ShouldBeEqualTo(3); 
     result.First().Count.ShouldBeEqualTo(5); 
     result.Last().Count.ShouldBeEqualTo(3); 
    } 
}