Almacenamiento en caché IEnumerable

Question

public IEnumerable<ModuleData> ListModules() 
{ 
    foreach (XElement m in Source.Descendants("Module")) 
    { 
     yield return new ModuleData(m.Element("ModuleID").Value); 
    } 
} 

Inicialmente, el código anterior es excelente ya que no es necesario evaluar toda la colección si no es necesario.

Sin embargo, una vez que todos los módulos se han enumerado una vez, se vuelve más costoso consultar repetidamente el XDocument cuando no hay cambios.

Por lo tanto, como una mejora en el rendimiento:

public IEnumerable<ModuleData> ListModules() 
{ 
    if (Modules == null) 
    { 
     Modules = new List<ModuleData>(); 
     foreach (XElement m in Source.Descendants("Module")) 
     { 
      Modules.Add(new ModuleData(m.Element("ModuleID").Value, 1, 1)); 
     } 
    } 
    return Modules; 
} 

que es grande si estoy usando repetidamente toda la lista, pero no tan grande lo contrario.

¿Existe un término medio en el que pueda generar el retorno hasta que se haya iterado toda la lista, luego lo guarde en caché y entregue el caché a las solicitudes subsiguientes?

Answer 1

Puede consultar Saving the State of Enumerators que describe cómo crear una lista diferida (que almacena en caché una vez los elementos iterados).

Answer 2

No veo ningún problema serio con la idea de almacenar los resultados en una lista, como en el código anterior. Probablemente, sería mejor construir la lista usando el método ToList().

public IEnumerable<ModuleData> ListModules() 
{ 
    if (Modules == null) 
    { 
     Modules = Source.Descendants("Module") 
         .Select(m => new ModuleData(m.Element("ModuleID").Value, 1, 1))) 
         .ToList(); 
    } 
    return Modules; 
} 

Answer 3

Salida MemoizeAll() en el Reactive Extensions for .NET biblioteca (Rx). Como se evalúa con pereza puede establecer con seguridad que durante la construcción y acaba de regresar de ModulesListModules():

Modules = Source. 
    Descendants("Module"). 
    Select(m => new ModuleData(m.Element("ModuleID").Value, 1, 1)). 
    MemoizeAll(); 

Hay una buena explicación de MemoizeAll() (y algunas de las otras extensiones Rx menos obvias) here.

Answer 4

He visto un puñado de implementaciones, algunas más antiguas y sin aprovechar las más nuevas clases .Net, algunas demasiado elaboradas para mis necesidades. Terminé con el código más conciso y declarativo que pude reunir, que se sumó a una clase con aproximadamente 15 líneas de código (real). Parece alinear bien con las necesidades de OP:

Edición: Segunda revisión, mejor soporte para enumerables vacías

/// <summary> 
/// A <see cref="IEnumerable{T}"/> that caches every item upon first enumeration. 
/// </summary> 
/// <seealso cref="http://blogs.msdn.com/b/matt/archive/2008/03/14/digging-deeper-into-lazy-and-functional-c.aspx"/> 
/// <seealso cref="http://blogs.msdn.com/b/wesdyer/archive/2007/02/13/the-virtues-of-laziness.aspx"/> 
public class CachedEnumerable<T> : IEnumerable<T> { 
    private readonly bool _hasItem; // Needed so an empty enumerable will not return null but an actual empty enumerable. 
    private readonly T _item; 
    private readonly Lazy<CachedEnumerable<T>> _nextItems; 

    /// <summary> 
    /// Initialises a new instance of <see cref="CachedEnumerable{T}"/> using <paramref name="item"/> as the current item 
    /// and <paramref name="nextItems"/> as a value factory for the <see cref="CachedEnumerable{T}"/> containing the next items. 
    /// </summary> 
    protected internal CachedEnumerable(T item, Func<CachedEnumerable<T>> nextItems) { 
    _hasItem = true; 
    _item = item; 
    _nextItems = new Lazy<CachedEnumerable<T>>(nextItems); 
    } 

    /// <summary> 
    /// Initialises a new instance of <see cref="CachedEnumerable{T}"/> with no current item and no next items. 
    /// </summary> 
    protected internal CachedEnumerable() { 
    _hasItem = false; 
    } 

    /// <summary> 
    /// Instantiates and returns a <see cref="CachedEnumerable{T}"/> for a given <paramref name="enumerable"/>. 
    /// Notice: The first item is always iterated through. 
    /// </summary> 
    public static CachedEnumerable<T> Create(IEnumerable<T> enumerable) { 
    return Create(enumerable.GetEnumerator()); 
    } 

    /// <summary> 
    /// Instantiates and returns a <see cref="CachedEnumerable{T}"/> for a given <paramref name="enumerator"/>. 
    /// Notice: The first item is always iterated through. 
    /// </summary> 
    private static CachedEnumerable<T> Create(IEnumerator<T> enumerator) { 
    return enumerator.MoveNext() ? new CachedEnumerable<T>(enumerator.Current,() => Create(enumerator)) : new CachedEnumerable<T>(); 
    } 

    /// <summary> 
    /// Returns an enumerator that iterates through the collection. 
    /// </summary> 
    public IEnumerator<T> GetEnumerator() { 
    if (_hasItem) { 
     yield return _item; 

     var nextItems = _nextItems.Value; 
     if (nextItems != null) { 
     foreach (var nextItem in nextItems) { 
      yield return nextItem; 
     } 
     } 
    } 
    } 

    /// <summary> 
    /// Returns an enumerator that iterates through a collection. 
    /// </summary> 
    IEnumerator IEnumerable.GetEnumerator() { 
    return GetEnumerator(); 
    } 
} 

Un método de extensión útil podría ser:

public static class IEnumerableExtensions { 
    /// <summary> 
    /// Instantiates and returns a <see cref="CachedEnumerable{T}"/> for a given <paramref name="enumerable"/>. 
    /// Notice: The first item is always iterated through. 
    /// </summary> 
    public static CachedEnumerable<T> ToCachedEnumerable<T>(this IEnumerable<T> enumerable) { 
    return CachedEnumerable<T>.Create(enumerable); 
    } 
} 

Y para la unidad probadores entre ustedes: (si no usa el reafilador solo elimine los atributos [SuppressMessage])

/// <summary> 
/// Tests the <see cref="CachedEnumerable{T}"/> class. 
/// </summary> 
[TestFixture] 
public class CachedEnumerableTest { 
    private int _count; 

    /// <remarks> 
    /// This test case is only here to emphasise the problem with <see cref="IEnumerable{T}"/> which <see cref="CachedEnumerable{T}"/> attempts to solve. 
    /// </remarks> 
    [Test] 
    [SuppressMessage("ReSharper", "PossibleMultipleEnumeration")] 
    [SuppressMessage("ReSharper", "ReturnValueOfPureMethodIsNotUsed")] 
    public void MultipleEnumerationAreNotCachedForOriginalIEnumerable() { 
    _count = 0; 

    var enumerable = Enumerable.Range(1, 40).Select(IncrementCount); 

    enumerable.Take(3).ToArray(); 
    enumerable.Take(10).ToArray(); 
    enumerable.Take(4).ToArray(); 

    Assert.AreEqual(17, _count); 
    } 

    /// <remarks> 
    /// This test case is only here to emphasise the problem with <see cref="IList{T}"/> which <see cref="CachedEnumerable{T}"/> attempts to solve. 
    /// </remarks> 
    [Test] 
    [SuppressMessage("ReSharper", "PossibleMultipleEnumeration")] 
    [SuppressMessage("ReSharper", "ReturnValueOfPureMethodIsNotUsed")] 
    public void EntireListIsEnumeratedForOriginalListOrArray() { 
    _count = 0; 
    Enumerable.Range(1, 40).Select(IncrementCount).ToList(); 
    Assert.AreEqual(40, _count); 

    _count = 0; 
    Enumerable.Range(1, 40).Select(IncrementCount).ToArray(); 
    Assert.AreEqual(40, _count); 
    } 

    [Test] 
    [SuppressMessage("ReSharper", "ReturnValueOfPureMethodIsNotUsed")] 
    public void MultipleEnumerationsAreCached() { 
    _count = 0; 

    var cachedEnumerable = Enumerable.Range(1, 40).Select(IncrementCount).ToCachedEnumerable(); 

    cachedEnumerable.Take(3).ToArray(); 
    cachedEnumerable.Take(10).ToArray(); 
    cachedEnumerable.Take(4).ToArray(); 

    Assert.AreEqual(10, _count); 
    } 

    [Test] 
    public void FreshCachedEnumerableDoesNotEnumerateExceptFirstItem() { 
    _count = 0; 

    Enumerable.Range(1, 40).Select(IncrementCount).ToCachedEnumerable(); 

    Assert.AreEqual(1, _count); 
    } 

    /// <remarks> 
    /// Based on Jon Skeet's test mentioned here: http://www.siepman.nl/blog/post/2013/10/09/LazyList-A-better-LINQ-result-cache-than-List.aspx 
    /// </remarks> 
    [Test] 
    [SuppressMessage("ReSharper", "LoopCanBeConvertedToQuery")] 
    public void MatrixEnumerationIteratesAsExpectedWhileStillKeepingEnumeratedValuesCached() { 
    _count = 0; 

    var cachedEnumerable = Enumerable.Range(1, 5).Select(IncrementCount).ToCachedEnumerable(); 

    var matrixCount = 0; 

    foreach (var x in cachedEnumerable) { 
     foreach (var y in cachedEnumerable) { 
     matrixCount++; 
     } 
    } 

    Assert.AreEqual(5, _count); 
    Assert.AreEqual(25, matrixCount); 
    } 

    [Test] 
    public void OrderingCachedEnumerableWorksAsExpectedWhileStillKeepingEnumeratedValuesCached() { 
    _count = 0; 

    var cachedEnumerable = Enumerable.Range(1, 5).Select(IncrementCount).ToCachedEnumerable(); 

    var orderedEnumerated = cachedEnumerable.OrderBy(x => x); 
    var orderedEnumeratedArray = orderedEnumerated.ToArray(); // Enumerated first time in ascending order. 
    Assert.AreEqual(5, _count); 

    for (int i = 0; i < orderedEnumeratedArray.Length; i++) { 
     Assert.AreEqual(i + 1, orderedEnumeratedArray[i]); 
    } 

    var reorderedEnumeratedArray = orderedEnumerated.OrderByDescending(x => x).ToArray(); // Enumerated second time in descending order. 
    Assert.AreEqual(5, _count); 

    for (int i = 0; i < reorderedEnumeratedArray.Length; i++) { 
     Assert.AreEqual(5 - i, reorderedEnumeratedArray[i]); 
    } 
    } 

    private int IncrementCount(int value) { 
    _count++; 
    return value; 
    } 
} 

Answer 5

Me gusta la respuesta de @ tsemer. Pero me gustaría proponer mis soluciones, que no tienen nada que ver con FP. Es un enfoque ingenuo, pero genera muchas menos asignaciones. Y no es seguro para subprocesos.

public class CachedEnumerable<T> : IEnumerable<T>, IDisposable 
{ 
    IEnumerator<T> _enumerator; 
    readonly List<T> _cache = new List<T>(); 

    public CachedEnumerable(IEnumerable<T> enumerable) 
     : this(enumerable.GetEnumerator()) 
    { 
    } 

    public CachedEnumerable(IEnumerator<T> enumerator) 
    { 
     _enumerator = enumerator; 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     // The index of the current item in the cache. 
     int index = 0; 

     // Enumerate the _cache first 
     for (; index < _cache.Count; index++) 
     { 
      yield return _cache[index]; 
     } 

     // Continue enumeration of the original _enumerator, 
     // until it is finished. 
     // This adds items to the cache and increment 
     for (; _enumerator != null && _enumerator.MoveNext(); index++) 
     { 
      var current = _enumerator.Current; 
      _cache.Add(current); 
      yield return current; 
     } 

     if (_enumerator != null) 
     { 
      _enumerator.Dispose(); 
      _enumerator = null; 
     } 

     // Some other users of the same instance of CachedEnumerable 
     // can add more items to the cache, 
     // so we need to enumerate them as well 
     for (; index < _cache.Count; index++) 
     { 
      yield return _cache[index]; 
     } 
    } 

    public void Dispose() 
    { 
     if (_enumerator != null) 
     { 
      _enumerator.Dispose(); 
      _enumerator = null; 
     } 
    } 

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

---

Esta es la forma en la prueba de matriz de respuesta de @ tsemer funcionará:

var ints = new [] { 1, 2, 3, 4, 5 }; 
var cachedEnumerable = new CachedEnumerable<int>(ints); 
foreach (var x in cachedEnumerable) 
{ 
    foreach (var y in cachedEnumerable) 
    { 
     //Do something 
    } 
} 

1. El bucle exterior (x) salta primero for, porque _cache está vacía;
2. x obtiene un artículo del _enumerator al _cache;
3. x hace una pausa antes del segundo for loop;
4. El bucle interno (y) enumera un elemento del _cache;
5. y recupera todos los elementos del _enumerator al _cache;
6. y omite el tercer bucle for, porque su variable index es igual a 5;
7. x se reanuda, su index es igual a 1. Se salta el segundo bucle for porque _enumerator está terminado;
8. x enumera un elemento del _cache utilizando el tercer bucle for;
9. x hace una pausa antes del tercero for;
10. y enumera 5 elementos del _cache utilizando el primer ciclo for;
11. y omite el segundo bucle for, porque _enumerator está terminado;
12. y omite el tercer bucle for, porque index de y es igual a 5;
13. x currículos, incrementos index. Obtiene un elemento del _cache utilizando el tercer bucle for.
14. x hace una pausa.
15. if index variable de x es menor que 5 luego vaya a 10;
16. final.

Answer 6

Me gusta mucho la respuesta de hazzik ... bueno y simple siempre es el camino. PERO hay un error en GetEnumerator

de alguna manera se da cuenta de que hay un problema, y ​​es por eso que hay un tercer bucle extraño después del bucle del segundo enumerador ... pero tampoco es tan simple como eso. El problema que desencadena la necesidad del tercer ciclo es general ... por lo que debe ser recursivo.

La respuesta parece incluso más simple.

public IEnumerator<T> GetEnumerator() 
    { 
     int index = 0; 

     while (true) 
     { 
      if (index < _cache.Count) 
      { 
       yield return _cache[index]; 
       index = index + 1; 
      } 
      else 
      { 
       if (_enumerator.MoveNext()) 
       { 
        _cache.Add(_enumerator.Current); 
       } 
       else 
       { 
        yield break; 
       } 
      } 
     } 
    } 

sí se puede hacer que sea un poquito más eficiente, al ceder actual ... pero me quedo con el golpe microsegundo ... es sólo alguna vez ocurre una vez por elemento.

y no es inseguro ... pero a quién le importa eso.