Maksymalne gromadzenie pojemności w C#

Question

W .Net BCL istnieje struktura danych kolekcji podobna do listy o maksymalnej pojemności, powiedzmy skonfigurowana do 100 elementów, która po dodaniu pozycji 101 oryginalna pierwsza pozycja jest wysuwana/usuwana z kolekcja zapewniając zatem liczba przekracza 100. poz nigdy

używam .NET 3.5

góry dzięki

Answer 1

To, co opisujesz, to bufor cykliczny. Używam tych sporadycznie i niedawno przenosiłem jakiś starszy kod do uogólnionej klasy C# (dołączonej). Ten kod jest częścią SharpNeat V2 development.

Ma wydajność O (1) przy dodawaniu i usuwaniu operacji, natomiast rozwiązanie, które zawiera enkapsulację listy, to O (n). Dzieje się tak dlatego, że usunięcie 0 pozycji z listy powoduje przesunięcie wszystkich pozostałych elementów w celu wypełnienia luki.

 

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

nie ma jednej dostępne, ale to powinno być łatwe do napisać funkcję do osiągnięcia tego celu z tablica lub kolekcja. Metoda

Answer 3

ArrayList.FixedSize().

Answer 4

Możesz odziedziczyć z jakiejkolwiek kolekcji, która byłaby najbardziej odpowiednia (Stack, Dequeue, List, CollectionBase, itp.) I wdrożyć tę funkcję samodzielnie. Wystarczy zastąpić lub zastąpić metodę Add().

Answer 5

Nie ma takiej kolekcji, ale jedna jest dość łatwa do napisania. Najlepszym sposobem jest utworzenie nowego typu kolekcji, który obejmuje istniejący typ kolekcji.

Na przykład

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 
} 

Kilka odpowiedzi sugeruje dziedziczenie jako mechanizm. Z pewnością nie jest to dobra trasa, szczególnie jeśli pochodzisz z jednej z ogólnych kolekcji. Kolekcje te nie są zaprojektowane do odziedziczenia i bardzo łatwo można przypadkowo obejść wszelkie kontrole, które wykonujesz w wyniku metody Dodaj lub Usuń.

Głównym powodem jest to, że metody te nie są wirtualne, więc nie można ich przesłonić. Będziesz zmuszony albo zadeklarować metodę Add z inną nazwą (tym samym myląc swoich użytkowników) lub ponownie zadeklarować Dodaj z nową składnią. Ta ostatnia jest bardzo niebezpieczna, ponieważ gdy tylko instancja twojej klasy zostanie przekazana do referencji typu bazowego, wszystkie twoje metody nie zostaną wywołane, a lista może przekroczyć pojemność.

EDIT

W dyskusji sekcji komentarz został wskazany, wdrażanie List<T> nie jest najlepszym podejściem tutaj. Powód jest taki, że w kilku przypadkach narusza on zasadę zastępowania. Najłatwiejszym sposobem wyświetlenia problemu jest wyobrazić sobie, że moja implementacja została przekazana do poniższej metody. Ten kod powinien przejść dla dowolnej implementacji IList<T>, ale w tym przypadku nie powiedzie się, jeśli lista była w stanie.

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

Jedyny interfejs zbierania, które mogą być skutecznie realizowane przez określony kolekcji jest IEnumerable<T>. Na przykład zostawiłem tam moją implementację. Ale patrz odpowiedź ShuggyCoUk dla implementacji IEnumerable<T>:

• Maximum capacity collection in c#

Answer 6

Chcesz okrągły bufor. Ten drugi numer SO question już o tym mówi i może pomóc ci w opracowaniu pomysłów.

Answer 7

można też po prostu zastąpić 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

bardzo prosty toczenia okno

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 
} 

ten można znaleźć realizację buforze cyklicznym tutaj: http://circularbuffer.codeplex.com