Thu thập dung lượng tối đa trong C#

Question

Trong .Net BCL có cấu trúc dữ liệu bộ sưu tập tương tự như danh sách có dung lượng tối đa, được định cấu hình thành 100 mục, khi mục 101 được thêm mục đầu tiên ban đầu được bật/xóa khỏi bộ sưu tập do đó đảm bảo số lượng item không bao giờ vượt quá 100.

tôi đang sử dụng net 3,5

Cảm ơn trước

Answer 1

Điều bạn mô tả là bộ đệm hình tròn. Tôi sử dụng những đôi khi và gần đây đã chuyển một số mã cũ hơn vào một lớp C# genericised (đính kèm). Mã này là một phần của SharpNeat V2 development.

Điều này có hiệu suất O (1) khi thêm và loại bỏ các lỗ trong khi giải pháp được đăng bao bọc Danh sách là O (n). Điều này là do việc loại bỏ mục thứ 0 trong danh sách khiến tất cả các mục khác được xáo trộn để lấp đầy khoảng trống.

 

using System; 
using System.Collections.Generic; 
using System.Text; 

namespace SharpNeat.Utility 
{ 
    /// 
    /// This is a generic circular buffer of items of type T. A circular buffer must be assigned 
    /// a capacity at construction time. Items can be enqueued indefintely, but when the buffer's 
    /// capacity is reached the oldest values in the buffer are overwritten, thus the buffer is best 
    /// thought of as a circular array or buffer. 
    /// 
    public class CircularBuffer 
    { 
     /// 
     /// Internal array that stores the circular buffer's values. 
     /// 
     protected T[] _buff; 

     /// 
     /// The index of the previously enqueued item. -1 if buffer is empty. 
     /// 
     protected int _headIdx; 

     /// 
     /// The index of the next item to be dequeued. -1 if buffer is empty. 
     /// 
     protected int _tailIdx; 

     #region Constructors 

     /// 
     /// Constructs a circular buffer with the specified capacity. 
     /// 
     /// 
     public CircularBuffer(int capacity) 
     { 
      _buff = new T[capacity]; 
      _headIdx = _tailIdx = -1; 
     } 

     #endregion 

     #region Properties 

     /// 
     /// Gets the number of items in the buffer. Returns the buffer's capacity 
     /// if it is full. 
     /// 
     public int Length 
     { 
      get 
      { 
       if(_headIdx == -1) 
        return 0; 

       if(_headIdx > _tailIdx) 
        return (_headIdx - _tailIdx) + 1; 

       if(_tailIdx > _headIdx) 
        return (_buff.Length - _tailIdx) + _headIdx + 1; 

       return 1; 
      } 
     } 

     #endregion 

     #region Public Methods 

     /// 
     /// Clear the buffer. 
     /// 
     public virtual void Clear() 
     { 
      _headIdx = _tailIdx = -1; 
     } 

     /// 
     /// Enqueue a new item. This overwrites the oldest item in the buffer if the buffer 
     /// has reached capacity. 
     /// 
     /// 
     public virtual void Enqueue(T item) 
     { 
      if(_headIdx == -1) 
      { // buffer is currently empty. 
       _headIdx = _tailIdx = 0; 
       _buff[0] = item; 
       return; 
      } 

      // Determine the index to write to. 
      if(++_headIdx == _buff.Length) 
      { // Wrap around. 
       _headIdx = 0; 
      } 

      if(_headIdx == _tailIdx) 
      { // Buffer overflow. Increment tailIdx. 
       if(++_tailIdx == _buff.Length) 
       { // Wrap around. 
        _tailIdx=0; 
       } 
       _buff[_headIdx] = item; 
       return; 
      } 

      _buff[_headIdx] = item; 
      return; 
     } 

     /// 
     /// Remove the oldest item from the back end of the buffer and return it. 
     /// 
     /// 
     public virtual T Dequeue() 
     { 
      if(_tailIdx == -1) 
      { // buffer is currently empty. 
       throw new InvalidOperationException("buffer is empty."); 
      } 

      T item = _buff[_tailIdx]; 

      if(_tailIdx == _headIdx) 
      { // The buffer is now empty. 
       _headIdx=_tailIdx=-1; 
       return item; 
      } 

      if(++_tailIdx == _buff.Length) 
      { // Wrap around. 
       _tailIdx = 0; 
      } 

      return item; 
     } 

     /// 
     /// Pop the most recently added item from the front end of the buffer and return it. 
     /// 
     /// 
     public virtual T Pop() 
     { 
      if(_tailIdx == -1) 
      { // buffer is currently empty. 
       throw new InvalidOperationException("buffer is empty."); 
      } 

      T item = _buff[_headIdx]; 

      if(_tailIdx == _headIdx) 
      { // The buffer is now empty. 
       _headIdx = _tailIdx =- 1; 
       return item; 
      } 

      if(--_headIdx==-1) 
      { // Wrap around. 
       _headIdx=_buff.Length-1; 
      } 

      return item; 
     } 

     #endregion 
    } 
} 

 

Answer 2

không có một có sẵn, nhưng nó phải là dễ dàng để viết một chức năng để thực hiện điều này với một mảng hoặc bộ sưu tập.

Answer 3

ArrayList.FixedSize() phương pháp.

Answer 4

Bạn có thể kế thừa từ bất kỳ bộ sưu tập hiện có nào phù hợp nhất (Stack, Dequeue, List, CollectionBase, v.v.) và tự mình thực hiện tính năng này. Chỉ cần ghi đè hoặc thay thế phương thức Add().

Answer 5

Không có bộ sưu tập nào như vậy nhưng một bộ sưu tập khá dễ viết. Cách tốt nhất để thực hiện việc này là tạo một loại bộ sưu tập mới bao gồm một loại bộ sưu tập hiện có.

Ví dụ

public class FixedSizeList<T> : IList<T> { 
    private List<T> _list = new List<T>(); 
    private int _capacity = 100; 

    public void Add(T value) { 
    _list.Add(value); 
    while (_list.Count > _capacity) { 
     _list.RemoveAt(0); 
    } 
    } 

    // Rest omitted for brevity 
} 

Một vài câu trả lời gợi ý thừa kế như một cơ chế. Điều này chắc chắn không phải là một tuyến đường tốt, đặc biệt nếu bạn bắt nguồn từ một trong những bộ sưu tập chung chung. Những bộ sưu tập này không được thiết kế để được kế thừa và rất dễ vô tình phá vỡ bất kỳ kiểm tra nào mà bạn tạo ra do khả năng là kết quả của phương thức Thêm hoặc Loại bỏ.

Lý do chính là các phương pháp này không phải là ảo để chúng không thể bị ghi đè. Bạn sẽ bị buộc phải khai báo phương thức Thêm bằng tên khác (do đó gây nhầm lẫn cho người dùng của bạn) hoặc khai báo lại Thêm bằng cú pháp mới. Cái thứ hai là rất không an toàn bởi vì ngay sau khi một thể hiện của lớp của bạn được chuyển tới một tham chiếu của kiểu cơ sở, tất cả các phương thức của bạn sẽ không được gọi và danh sách có thể phát triển khả năng trong quá khứ.

EDIT

Khi thảo luận Phần bình luận đã chỉ ra, thực hiện List<T> không phải là phương pháp tốt nhất ở đây. Lý do tại sao là nó vi phạm nguyên tắc thay thế trong một số trường hợp. Cách dễ nhất để hiển thị vấn đề là hình dung xem việc triển khai của tôi có được chuyển đến phương thức sau hay không. Mã này phải chuyển cho bất kỳ việc triển khai IList<T> nào nhưng sẽ không thành công trong trường hợp này nếu danh sách có dung lượng.

public void Example<T>(IList<T> list, T value) { 
    var count = list.Count; 
    list.Add(value); 
    var addedValue = list[count]; 
} 

Giao diện thu thập duy nhất có thể được triển khai hợp lệ cho bộ sưu tập được chỉ định là IEnumerable<T>. Tôi đã để việc triển khai của tôi ở đó như một ví dụ. Nhưng xem câu trả lời ShuggyCoUk cho một thực hiện IEnumerable<T>:

• Maximum capacity collection in c#

Answer 6

Bạn muốn có một bộ đệm tròn. Điều này khác SO question đã nói về điều đó và nó có thể giúp cung cấp một số ý tưởng cho bạn.

Answer 7

bạn cũng có thể chỉ ghi đè Collection

public class FixedSizeList<T> : Collection<T> 
{ 
    public int MaxItems {get;set;} 

    protected override void InsertItem(int index, T item){ 
     base.InsertItem(index, item); 

     while (base.Count > MaxItems) { 
      base.RemoveItem(0); 
     } 
    } 
} 

Answer 8

Một cửa sổ lăn thực sự đơn giản

public class RollingWindow<T> : IEnumerable<T> 
{ 
    private readonly T[] data; 
    private int head; 
    private int nextInsert = 0; 

    public RollingWindow(int size) 
    { 
     if (size < 1) 
      throw new Exception(); 
     this.data = new T[size]; 
     this.head = -size; 
    } 

    public void Add(T t) 
    { 
     data[nextInsert] = t; 
     nextInsert = (nextInsert + 1) % data.Length; 
     if (head < 0) 
      head++; 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     if (head < 0) 
     { 
      for (int i = 0; i < nextInsert; i++) 
       yield return data[i]; 
     } 
     else 
     { 
      for(int i = 0; i < data.Length; i++) 
       yield return data[(nextInsert + i) % data.Length]; 
     } 
    } 

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

Answer 9

public class CircularBuffer<T> : ICollection<T>, IEnumerable<T>, ICollection, IEnumerable 
{ 
    private int capacity; 
    private int size; 
    private int head; 
    private int tail; 
    private T[] buffer; 

    [NonSerialized()] 
    private object syncRoot; 

    public CircularBuffer(int capacity) 
     : this(capacity, false) 
    { 
    } 

    public CircularBuffer(int capacity, bool allowOverflow) 
    { 
     if (capacity < 0) 
      throw new ArgumentException(Properties.Resources.MessageZeroCapacity, "capacity"); 

     this.capacity = capacity; 
     size = 0; 
     head = 0; 
     tail = 0; 
     buffer = new T[capacity]; 
     AllowOverflow = allowOverflow; 
    } 

    public bool AllowOverflow 
    { 
     get; 
     set; 
    } 

    public int Capacity 
    { 
     get { return capacity; } 
     set 
     { 
      if (value == capacity) 
       return; 

      if (value < size) 
       throw new ArgumentOutOfRangeException("value", Properties.Resources.MessageCapacityTooSmall); 

      var dst = new T[value]; 
      if (size > 0) 
       CopyTo(dst); 
      buffer = dst; 

      capacity = value; 
     } 
    } 

    public int Size 
    { 
     get { return size; } 
    } 

    public bool Contains(T item) 
    { 
     int bufferIndex = head; 
     var comparer = EqualityComparer<T>.Default; 
     for (int i = 0; i < size; i++, bufferIndex++) 
     { 
      if (bufferIndex == capacity) 
       bufferIndex = 0; 

      if (item == null && buffer[bufferIndex] == null) 
       return true; 
      else if ((buffer[bufferIndex] != null) && 
       comparer.Equals(buffer[bufferIndex], item)) 
       return true; 
     } 

     return false; 
    } 

    public void Clear() 
    { 
     size = 0; 
     head = 0; 
     tail = 0; 
    } 

    public int Put(T[] src) 
    { 
     return Put(src, 0, src.Length); 
    } 

    public int Put(T[] src, int offset, int count) 
    { 
     if (!AllowOverflow && count > capacity - size) 
      throw new InvalidOperationException(Properties.Resources.MessageBufferOverflow); 

     int srcIndex = offset; 
     for (int i = 0; i < count; i++, tail++, srcIndex++) 
     { 
      if (tail == capacity) 
       tail = 0; 
      buffer[tail] = src[srcIndex]; 
     } 
     size = Math.Min(size + count, capacity); 
     return count; 
    } 

    public void Put(T item) 
    { 
     if (!AllowOverflow && size == capacity) 
      throw new InvalidOperationException(Properties.Resources.MessageBufferOverflow); 

     buffer[tail] = item; 
     if (++tail == capacity) 
      tail = 0; 
     size++; 
    } 

    public void Skip(int count) 
    { 
     head += count; 
     if (head >= capacity) 
      head -= capacity; 
    } 

    public T[] Get(int count) 
    { 
     var dst = new T[count]; 
     Get(dst); 
     return dst; 
    } 

    public int Get(T[] dst) 
    { 
     return Get(dst, 0, dst.Length); 
    } 

    public int Get(T[] dst, int offset, int count) 
    { 
     int realCount = Math.Min(count, size); 
     int dstIndex = offset; 
     for (int i = 0; i < realCount; i++, head++, dstIndex++) 
     { 
      if (head == capacity) 
       head = 0; 
      dst[dstIndex] = buffer[head]; 
     } 
     size -= realCount; 
     return realCount; 
    } 

    public T Get() 
    { 
     if (size == 0) 
      throw new InvalidOperationException(Properties.Resources.MessageBufferEmpty); 

     var item = buffer[head]; 
     if (++head == capacity) 
      head = 0; 
     size--; 
     return item; 
    } 

    public void CopyTo(T[] array) 
    { 
     CopyTo(array, 0); 
    } 

    public void CopyTo(T[] array, int arrayIndex) 
    { 
     CopyTo(0, array, arrayIndex, size); 
    } 

    public void CopyTo(int index, T[] array, int arrayIndex, int count) 
    { 
     if (count > size) 
      throw new ArgumentOutOfRangeException("count", Properties.Resources.MessageReadCountTooLarge); 

     int bufferIndex = head; 
     for (int i = 0; i < count; i++, bufferIndex++, arrayIndex++) 
     { 
      if (bufferIndex == capacity) 
       bufferIndex = 0; 
      array[arrayIndex] = buffer[bufferIndex]; 
     } 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     int bufferIndex = head; 
     for (int i = 0; i < size; i++, bufferIndex++) 
     { 
      if (bufferIndex == capacity) 
       bufferIndex = 0; 

      yield return buffer[bufferIndex]; 
     } 
    } 

    public T[] GetBuffer() 
    { 
     return buffer; 
    } 

    public T[] ToArray() 
    { 
     var dst = new T[size]; 
     CopyTo(dst); 
     return dst; 
    } 

    #region ICollection<T> Members 

    int ICollection<T>.Count 
    { 
     get { return Size; } 
    } 

    bool ICollection<T>.IsReadOnly 
    { 
     get { return false; } 
    } 

    void ICollection<T>.Add(T item) 
    { 
     Put(item); 
    } 

    bool ICollection<T>.Remove(T item) 
    { 
     if (size == 0) 
      return false; 

     Get(); 
     return true; 
    } 

    #endregion 

    #region IEnumerable<T> Members 

    IEnumerator<T> IEnumerable<T>.GetEnumerator() 
    { 
     return GetEnumerator(); 
    } 

    #endregion 

    #region ICollection Members 

    int ICollection.Count 
    { 
     get { return Size; } 
    } 

    bool ICollection.IsSynchronized 
    { 
     get { return false; } 
    } 

    object ICollection.SyncRoot 
    { 
     get 
     { 
      if (syncRoot == null) 
       Interlocked.CompareExchange(ref syncRoot, new object(), null); 
      return syncRoot; 
     } 
    } 

    void ICollection.CopyTo(Array array, int arrayIndex) 
    { 
     CopyTo((T[])array, arrayIndex); 
    } 

    #endregion 

    #region IEnumerable Members 

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

    #endregion 
} 

Bạn có thể tìm thấy điều này thực hiện của một bộ đệm tròn ở đây: http://circularbuffer.codeplex.com