一个有效而简单的实现方法是使用一个具有前索引和后索引的数组来实现Circular Buffer
.
如果将底层数组设置为比要存储的最大项目数大一个,则代码会简化.这允许你安排事情,如果front_index
== back_index
,那么缓冲区是空的.
下面是一个示例实现.它有添加元素、移除最老元素、索引元素从最老到最新以及枚举元素从最老到最新的方法.希望代码是相当自解释的:
public sealed class CircularBuffer<T> : IEnumerable<T>
{
/// <summary>Constructor.</summary>
/// <param name="capacity">The maximum capacity of the buffer.</param>
public CircularBuffer(int capacity)
{
// We will use a buffer with a size one greater than the capacity.
// The reason for this is to simplify the logic - we can use "front == back" to indicate an empty buffer.
_buffer = new T[capacity + 1];
}
public int Capacity => _buffer.Length - 1;
/// <summary>The number of elements currently stored in the buffer.</summary>
public int Count
{
get
{
int result = _back - _front;
if (result < 0)
result += _buffer.Length;
return result;
}
}
public bool IsEmpty => this.Count == 0;
public bool IsFull => nextSlot(_back) == _front;
/// <summary>Removes all elements.</summary>
public void Empty()
{
_front = _back = 0;
Array.Clear(_buffer, 0, _buffer.Length); // Destroy any old references so they can be GCed.
}
/// <summary>Add an element to the buffer, overwriting the oldest element if the buffer is full.</summary>
/// <param name="newItem">The element to add.</param>
public void Add(T newItem)
{
_buffer[_back] = newItem;
_back = nextSlot(_back);
if (_back != _front) // Buffer is not full?
return;
_front = nextSlot(_front); // Bump the front, overwriting the current front.
_buffer[_back] = default!; // Remove the old front value.
}
/// <summary>Return the item at index, where 0 is the oldest thing in the buffer </summary>
public T this[int index] => _buffer[(index + _front) % _buffer.Length];
/// <summary>Removes and returns the oldest element from the buffer.</summary>
/// <returns>The element that was removed from the buffer.</returns>
/// <exception cref="InvalidOperationException">Thrown if the buffer is empty.</exception>
public T RemoveOldestElement()
{
if (IsEmpty)
throw new InvalidOperationException("Cannot remove an element from an empty buffer.");
T result = _buffer[_front];
_buffer[_front] = default!; // Zap the front element.
_front = nextSlot(_front);
return result;
}
/// <summary>Returns elements in oldest to newest order. </summary>
public IEnumerator<T> GetEnumerator()
{
for (int i = _front; i != _back; i = nextSlot(i))
{
yield return _buffer[i];
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator(); // Implement in terms of the typesafe enumerator.
}
int nextSlot(int slot)
{
return (slot + 1) % _buffer.Length;
}
int _front;
int _back;
/// <summary>The underlying buffer. This has a length one greater than the actual capacity.</summary>
readonly T[] _buffer;
}
[增编]
上面的代码是我们从. Net 3.5开始就一直在使用的代码.在 那次比一百快了一些.然而,在后来的. NET版本中,情况有所改善.
我比较了上面的CircularBuffer
和Queue<T>
上的简单扩展方法,以提供与CircularBuffer.Add()
相同的功能:
public static class QueueExt
{
public static void Add<T>(this Queue<T> self, T item, int limit)
{
if (self.Count >= limit) // Consider throwing if self.Count > limit.
self.Dequeue();
self.Enqueue(item);
}
}
测试的基准代码(有点简单化)是:
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Jobs;
namespace TestQueue;
[MemoryDiagnoser]
[SimpleJob(RuntimeMoniker.Net48)]
[SimpleJob(RuntimeMoniker.Net80)]
public class UnderTest
{
[Benchmark]
public void ViaQueue()
{
_queue.Clear();
for (int i = 0; i < 100_000; i++)
{
_queue.Add(i, 1000);
}
}
[Benchmark]
public void ViaCircularArray()
{
_buffer.Empty();
for (int i = 0; i < 100_000; i++)
{
_buffer.Add(i);
}
}
static readonly Queue<double> _queue = new Queue<double>(1000);
static readonly CircularBuffer<double> _buffer = new CircularBuffer<double>(1000);
}
在我的系统上的结果:
| Method | Runtime | Mean | Error | StdDev |
|----------------- |------------------- |---------:|--------:|--------:|
| ViaQueue | .NET 8.0 | 220.5 us | 1.35 us | 1.12 us |
| ViaCircularArray | .NET 8.0 | 380.1 us | 1.67 us | 1.56 us |
| ViaQueue | .NET Framework 4.8 | 403.6 us | 7.87 us | 7.36 us |
| ViaCircularArray | .NET Framework 4.8 | 390.5 us | 2.43 us | 2.15 us |
对于.NET 4.8,CircularArray
稍微快一些.然而,对于.NET 8.0来说,Queue<T>
速度明显快.
因此,我实际上建议您使用内置的Queue<T>
来代替(带有适当的前端).
Queue<T>
的唯一缺点是你不能访问它的内部Capacity
,所以你必须通过限制—或者你可以直接将它包装在一个包含容量的类中.