Максимальная сборка емкости в С#

Ответ 1

То, что вы описываете, это круговой буфер. Я иногда использовал это, и недавно портировал некоторый старый код в обобщенный класс С# (прилагается). Этот код является частью SharpNeat V2 development.

Это имеет производительность O (1) при добавлении и удалении отпечатков, тогда как решение отправлено, что инкапсулирует список O (n). Это происходит потому, что удаление 0-го элемента в списке заставляет все остальные элементы перетасовываться, чтобы заполнить пробел.

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

Ответ 2

Нет такой коллекции, но ее довольно легко написать. Лучший способ сделать это - создать новый тип коллекции, который инкапсулирует существующий тип коллекции.

Например

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
}

Несколько ответов предложили наследование как механизм. Это, конечно, не очень хороший маршрут, особенно если вы извлекаете из одной из общих коллекций. Эти коллекции не предназначены для наследования, и очень легко случайно избежать любых проверок, которые вы делаете в результате использования метода добавления или удаления.

Основная причина заключается в том, что эти методы не являются виртуальными, поэтому их нельзя переопределить. Вам придется либо объявить метод Add с другим именем (таким образом, запутать ваших пользователей), либо повторно объявить Add с новым синтаксисом. Последнее очень опасно, поскольку, как только экземпляр вашего класса передается в ссылку базового типа, все ваши методы не будут вызываться, а список может увеличиться.

ИЗМЕНИТЬ

Как показало обсуждение раздела комментариев, реализация List<T> здесь не самый лучший подход. Причина в том, что в некоторых случаях он нарушает принцип замещения. Самый простой способ показать проблему - представить, была ли моя реализация передана следующему методу. Этот код должен пройти для любой реализации IList<T>, но в этом случае произойдет сбой, если список был в состоянии.

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

Единственный интерфейс коллекции, который может быть успешно реализован для указанной коллекции, - IEnumerable<T>. В качестве примера я оставил свою реализацию. Но см. Ответ ShuggyCoUk для реализации IEnumerable<T>:

• Сбор максимальной емкости в С#

Ответ 3

Действительно простое окно прокрутки

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

Ответ 4

Нет ни одного доступного, но должно быть легко написать функцию, чтобы выполнить это с помощью массива или коллекции.

Ответ 5

вы также можете просто переопределить 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);
        }
    }
}

Ответ 6

Вы могли бы наследовать любую существующую коллекцию (Stack, Dequeue, List, CollectionBase и т.д.) и реализовать эту функцию самостоятельно. Просто переопределите или замените метод Add().

Ответ 7

Вам нужен круговой буфер. Этот другой вопрос SO уже говорит об этом, и это может помочь вам представить некоторые идеи.

Ответ 8

метод ArrayList.FixedSize().

Ответ 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
}

Вы можете найти эту реализацию кругового буфера здесь: http://circularbuffer.codeplex.com