Caching IEnumerable

Question

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

Ban đầu mã trên là rất lớn vì không cần đánh giá toàn bộ bộ sưu tập nếu không cần thiết.

Tuy nhiên, một khi tất cả các Mô-đun đã được liệt kê một lần, sẽ trở nên tốn kém hơn khi truy vấn nhiều lần XDocument khi không có thay đổi.

Vì vậy, như một sự cải thiện hiệu suất:

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; 
} 

Đó là tuyệt vời nếu tôi đang liên tục sử dụng toàn bộ danh sách nhưng không quá lớn khác.

Có nền tảng trung gian nơi tôi có thể mang lại lợi nhuận cho đến khi toàn bộ danh sách đã được lặp lại, sau đó lưu trữ bộ nhớ cache và phục vụ bộ nhớ cache cho các yêu cầu tiếp theo không?

Answer 1

Bạn có thể xem Saving the State of Enumerators mô tả cách tạo danh sách lười (lưu trữ một lần các mục được lặp lại).

Answer 2

Tôi không thấy bất kỳ vấn đề nghiêm trọng nào với ý tưởng lưu vào bộ nhớ cache kết quả trong danh sách, giống như trong mã ở trên. Có lẽ, nó sẽ là tốt hơn để xây dựng danh sách bằng cách sử dụng ToList() phương pháp.

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

Kiểm tra MemoizeAll() trong thư viện Reactive Extensions for .NET (Rx). Vì nó được đánh giá một cách lười biếng bạn có thể yên tâm thiết lập nó trong quá trình thi và chỉ trả Modules từ ListModules():

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

Có một lời giải thích tốt MemoizeAll() (và một số các phần mở rộng Rx ít rõ ràng khác) here.

Answer 4

Tôi đã thấy một số ít triển khai ở đó, một số cũ hơn và không tận dụng các lớp Net. Mới nhất, một số quá phức tạp cho nhu cầu của tôi. Tôi đã kết thúc với đoạn mã ngắn gọn và khai báo nhất mà tôi có thể tập hợp, thêm vào một lớp với khoảng 15 dòng (thực tế) mã. Có vẻ như để gắn kết tốt với nhu cầu của OP của:

Edit: sửa đổi Thứ hai, hỗ trợ tốt hơn cho enumerables trống

/// <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(); 
    } 
} 

Một phương pháp mở rộng hữu ích có thể là:

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); 
    } 
} 

Và đối với các đơn vị người thử nghiệm trong số các bạn: (nếu bạn không sử dụng tính năng chia sẻ lại chỉ cần lấy ra các thuộc tính [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

Tôi thích câu trả lời của @ tsemer. Nhưng tôi muốn đề xuất các giải pháp của tôi, không liên quan gì đến FP. Đó là cách tiếp cận ngây thơ, nhưng nó tạo ra rất ít phân bổ. Và nó không phải là chủ đề an toàn.

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(); 
    } 
} 

---

Đây là cách kiểm tra ma trận từ câu trả lời @ tsemer sẽ làm việc:

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. Các vòng ngoài (x) bỏ qua đầu for, vì _cache là trống rỗng;
2. x tìm nạp một mục từ _enumerator đến _cache;
3. x tạm dừng trước giây thứ hai for vòng lặp;
4. Vòng lặp bên trong (y) liệt kê một phần tử từ _cache;
5. y tìm nạp tất cả các phần tử từ _enumerator đến _cache;
6. y bỏ qua vòng lặp thứ ba for, vì biến số index bằng 5;
7. x hồ sơ, index bằng 1. Nó bỏ qua vòng lặp for thứ hai vì _enumerator hoàn tất;
8. x liệt kê một phần tử từ _cache bằng cách sử dụng vòng lặp for thứ ba;
9. x tạm dừng trước số thứ ba for;
10. y liệt kê 5 phần tử từ _cache bằng cách sử dụng vòng lặp for đầu tiên;
11. y bỏ qua vòng lặp for thứ hai, vì _enumerator hoàn tất;
12. y bỏ qua vòng lặp thứ ba for, vì index của y bằng 5;
13. x hồ sơ, gia số index. Nó lấy một phần tử từ _cache bằng cách sử dụng vòng lặp for thứ ba.
14. x tạm dừng.
15. nếu index biến số x nhỏ hơn 5 rồi chuyển đến 10;
16. kết thúc.

Answer 6

Tôi khá thích câu trả lời của hazzik ... đẹp và đơn giản luôn là cách. NHƯNG có lỗi trong phần GetEnumerator

nó nhận ra rằng có một vấn đề, và đó là lý do tại sao có vòng lặp thứ 3 lạ sau vòng lặp đếm thứ 2 .... nhưng nó không đơn giản như vậy. Vấn đề kích hoạt sự cần thiết cho vòng lặp thứ 3 là chung ... vì vậy nó cần phải được đệ quy.

Câu trả lời trông thậm chí còn đơn giản hơn.

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; 
       } 
      } 
     } 
    } 

có bạn có thể làm cho nó hiệu quả hơn một chút bằng cách sử dụng hiện tại ... nhưng tôi sẽ thực hiện một giây ... nó chỉ xảy ra một lần cho mỗi phần tử.

và không an toàn ... nhưng ai quan tâm đến điều đó.