一个被BCL遗忘的高性能集合：C# CircularBuffer<T>深度解析

大家好，在最近的一个业余项目——天体运行模拟器中，我遇到了一个有趣的需求：我需要记录每个天体最近一段时间的历史位置，从而在屏幕上为它们画出一条长长而漂亮的轨迹线。
你可能会说，用一个 List 不就行了？但问题在于，如果模拟持续运行，这个 List 会无限增长，最终会消耗大量内存，甚至可能导致程序崩溃。我真正需要的是一个“固定大小”的集合，当新数据加进来时，最老的数据能被自动丢弃。这正是“循环缓冲区”（Circular Buffer）大显身手的场景。CircularBuffer 完美地满足了我的需求。

CircularBuffer 的实现

C# 的基础类库（BCL）中并没有内置 CircularBuffer 这个类型，但这完全不妨碍我们自己动手，丰衣足食。下面就是我所使用的 CircularBuffer 的完整实现，它支持泛型，并且实现了 IEnumerable 接口，可以方便地进行遍历。

1. using System.Collections;
2. using System.Collections.Generic;
3. using System;
5. namespace Sdcb.NBody.Common;
7. /// <summary>
8. /// 表示一个固定容量的循环缓冲区（或环形列表）。
9. /// 当缓冲区满时，添加新元素会覆盖最早的元素。
10. /// </summary>
11. /// <typeparam name="T">缓冲区中元素的类型。</typeparam>
12. public class CircularBuffer<T> : IEnumerable<T>
13. {
14.     private readonly T[] _data;
15.     private int _end; // 指向下一个要写入元素的位置（尾部）
17.     /// <summary>
18.     /// 获取缓冲区中实际存储的元素数量。
19.     /// </summary>
20.     public int Count { get; private set; }
22.     /// <summary>
23.     /// 获取缓冲区的总容量。
24.     /// </summary>
25.     public int Capacity => _data.Length;
27.     /// <summary>
28.     /// 获取一个值，该值指示缓冲区是否已满。
29.     /// </summary>
30.     public bool IsFull => Count == Capacity;
32.     /// <summary>
33.     /// 计算并获取第一个元素（头部）在内部数组中的索引。
34.     /// </summary>
35.     private int HeadIndex
36.     {
37.         get
38.         {
39.             if (Count == 0) return 0;
40.             // 当 Count < Capacity 时，_end 就是 Count，结果为 0。
41.             // 当缓冲区满时 (Count == Capacity)，_end 会循环，这个公式能正确计算出头部的索引。
42.             return (_end - Count + Capacity) % Capacity;
43.         }
44.     }
46.     /// <summary>
47.     /// 初始化 <see cref="CircularBuffer{T}"/> 类的新实例。
48.     /// </summary>
49.     /// <param name="capacity">缓冲区的容量。必须为正数。</param>
50.     /// <exception cref="ArgumentException">当容量小于等于 0 时抛出。</exception>
51.     public CircularBuffer(int capacity)
52.     {
53.         if (capacity <= 0)
54.         {
55.             throw new ArgumentException("Capacity must be a positive number.", nameof(capacity));
56.         }
57.         _data = new T[capacity];
58.         _end = 0;
59.         Count = 0;
60.     }
62.     /// <summary>
63.     /// 将一个新元素添加到缓冲区的尾部。
64.     /// 如果缓冲区已满，此操作会覆盖最早的元素。
65.     /// </summary>
66.     /// <param name="item">要添加的元素。</param>
67.     public void Add(T item)
68.     {
69.         _data[_end] = item;
70.         _end = (_end + 1) % Capacity;
72.         if (Count < Capacity)
73.         {
74.             Count++;
75.         }
76.     }
78.     /// <summary>
79.     /// 清空缓冲区中的所有元素。
80.     /// </summary>
81.     public void Clear()
82.     {
83.         // 只需重置计数器和指针即可，无需清除数组数据
84.         Count = 0;
85.         _end = 0;
86.     }
88.     /// <summary>
89.     /// 获取或设置指定逻辑索引处的元素。
90.     /// 索引 0 是最早的元素，索引 Count-1 是最新的元素。
91.     /// </summary>
92.     /// <param name="index">元素的逻辑索引。</param>
93.     /// <exception cref="IndexOutOfRangeException">当索引超出范围时抛出。</exception>
94.     public T this[int index]
95.     {
96.         get
97.         {
98.             if (index < 0 || index >= Count)
99.             {
100.                 throw new IndexOutOfRangeException("Index is out of the valid range of the buffer.");
101.             }
102.             int actualIndex = (HeadIndex + index) % Capacity;
103.             return _data[actualIndex];
104.         }
105.         set
106.         {
107.             if (index < 0 || index >= Count)
108.             {
109.                 throw new IndexOutOfRangeException("Index is out of the valid range of the buffer.");
110.             }
111.             int actualIndex = (HeadIndex + index) % Capacity;
112.             _data[actualIndex] = value;
113.         }
114.     }
116.     /// <summary>
117.     /// 获取缓冲区中的第一个（最早的）元素。
118.     /// </summary>
119.     /// <exception cref="InvalidOperationException">当缓冲区为空时抛出。</exception>
120.     public T First
121.     {
122.         get
123.         {
124.             if (Count == 0) throw new InvalidOperationException("Buffer is empty.");
125.             return _data[HeadIndex];
126.         }
127.     }
129.     /// <summary>
130.     /// 获取缓冲区中的最后一个（最新的）元素。
131.     /// </summary>
132.     /// <exception cref="InvalidOperationException">当缓冲区为空时抛出。</exception>
133.     public T Last
134.     {
135.         get
136.         {
137.             if (Count == 0) throw new InvalidOperationException("Buffer is empty.");
138.             // _end 指向下一个要写入的位置，所以上一个写入的位置是 (_end - 1)
139.             int lastIndex = (_end - 1 + Capacity) % Capacity;
140.             return _data[lastIndex];
141.         }
142.     }
144.     /// <summary>
145.     /// 返回一个循环访问集合的枚举器。
146.     /// </summary>
147.     public IEnumerator<T> GetEnumerator()
148.     {
149.         int head = HeadIndex;
150.         for (int i = 0; i < Count; i++)
151.         {
152.             yield return _data[(head + i) % Capacity];
153.         }
154.     }
156.     /// <summary>
157.     /// 返回一个循环访问集合的枚举器。
158.     /// </summary>
159.     IEnumerator IEnumerable.GetEnumerator()
160.     {
161.         return GetEnumerator();
162.     }
163. }

复制代码

原理浅析

这个类的核心思想非常巧妙：

• 内部存储：它内部使用一个固定长度的数组 _data 作为元素的物理存储空间。
  
• 指针管理：它使用一个 _end 指针来标记下一个新元素应该插入的位置（尾部），以及一个 Count 属性来记录当前存储的元素数量。
  
• 循环的奥秘：HeadIndex 这个计算属性是关键，它通过 _end 和 Count 的位置动态计算出“逻辑上”第一个元素（头部）在物理数组中的实际索引。取模运算 % Capacity 保证了无论是 _end 指针的移动还是 HeadIndex 的计算，都能在数组的边界内“循环”。
  
• 添加与覆盖：当你调用 Add 方法时，新元素会被放到 _end 指向的位置。如果缓冲区还没满 (Count < Capacity)，Count 会加一。如果已经满了，Count 不再变化，而旧的头部元素就会被自然而然地覆盖掉。整个过程对于调用者来说是无感的。
  

骚操作之：在天体模拟中使用

得益于 CircularBuffer 的优雅设计，在我的天体模拟器中使用它变得异常简单。我只需要关心一件事：把新的位置点加进去。
这就是它在我的模拟循环中的样子：每当一个天体的位置变化超过了2个像素（为了避免轨迹点过于密集），我就把它新的坐标 Add 到它的轨迹历史记录 TrackingHistory 中。

1. // _system.MoveNext();
2. // _acc += _system.Current.Timestamp - _lastSnapshot.Timestamp;
4. for (int i = 0; i < _system.Current.Bodies.Length; ++i)
5. {
6.     BodySnapshot star = _system.Current.Bodies[i];
7.     BodyUIProps props = _uiProps[i];
9.     Vector2 now = new(star.Px, star.Py);
10.     // 如果历史轨迹中有数据，则判断距离
11.     if (props.TrackingHistory.Count > 0)
12.     {
13.         Vector2 old = props.TrackingHistory.Last;
14.         float dist = Vector2.Distance(old, now);
15.         // 只有当移动距离超过阈值时才添加新点
16.         if (dist > 2 / _scale.Value)
17.         {
18.             props.TrackingHistory.Add(now);
19.         }
20.     }
21.     else
22.     {
23.         // 如果是第一个点，直接添加
24.         props.TrackingHistory.Add(now);
25.     }
26. }

复制代码

我完全不需要写 if (list.Count > MAX_COUNT) { list.RemoveAt(0); } 这样的代码。CircularBuffer 自动为我处理了覆盖最早元素逻辑，代码因此变得更加简洁和高效。
骚操作之：遍历与渲染

当需要绘制轨迹线时，由于 CircularBuffer 实现了 IEnumerable 接口，我可以直接使用 foreach 循环来遍历其中的所有点，并将它们连接成线。下面的代码片段使用 Direct2D 来绘制几何路径：

1. if (prop.TrackingHistory.Count < 2) continue;
3. using ID2D1PathGeometry1 path = XResource.Direct2DFactory.CreatePathGeometry();
4. using ID2D1GeometrySink sink = path.Open();
6. // 将画笔移动到轨迹的第一个点
7. sink.BeginFigure(prop.TrackingHistory.First, FigureBegin.Hollow);
9. // 遍历并连接后续的点
10. foreach (Vector2 pt in prop.TrackingHistory.Skip(1))
11. {
12.     sink.AddLine(pt);
13. }
15. sink.EndFigure(FigureEnd.Open);
16. sink.Close();
18. // 绘制几何路径
19. ctx.DrawGeometry(path, XResource.GetColor(prop.Color), 0.02f);

复制代码

这里的 foreach 会按照元素添加的先后顺序，从最早的（头部）到最新的（尾部）依次返回，完美符合我绘制轨迹的需求。
性能分析：为什么它如此高效？

我们实现的这个 CircularBuffer 不仅用起来方便，其性能也相当出色。让我们来分析一下它主要操作的时间复杂度：

• 插入 (Add): O(1)。添加一个新元素仅涉及一次数组写入和一次指针（_end）的算术运算，无论缓冲区有多大，耗时都是固定的。
  
• 获取元素数量 (Count): O(1)。这只是返回一个字段的值，是瞬时操作。
  
• 索引访问 (this[index]): O(1)。通过索引获取元素，需要经过 HeadIndex 的 O(1) 计算来定位实际的数组下标，然后进行一次数组访问，总体仍然是 O(1)。
  
• 获取头/尾元素 (First/Last): O(1)。与索引访问类似，都是通过计算直接定位，无需遍历。
  
• 查找/遍历 (foreach): O(n)。和大多数集合一样，如果要查找一个不确定位置的元素或完整遍历，需要访问所有 n 个元素。
  

现在，让我们来对比一下，如果使用 List 并手动在列表满时执行 list.RemoveAt(0) 来模拟这个行为，会发生什么。
List.RemoveAt(0) 是一个非常昂贵的操作，其时间复杂度为 O(n)。这是因为它需要将索引 0 之后的所有元素在内存中向前移动一位来填补空缺。如果你的缓冲区很大（比如存储几千个历史点），每次添加新元素都可能触发一次大规模的内存复制，这会带来巨大的性能开销。
相比之下，我们的 CircularBuffer 仅仅通过移动一个整数指针就巧妙地“移除”了最旧的元素，整个 Add 操作的复杂度始终是 O(1)。在这种需要固定大小并频繁读写的场景下，其效率比 List 的模拟方案好得不知道哪里去了，性能简直是天壤之别。
总结

虽然 C# 基础类库里没有提供 CircularBuffer，但它无疑是一个非常实用的数据结构。它在需要固定容量、自动淘汰旧数据的场景下表现出色。
除了今天演示的天体运行轨迹记录，它还可以广泛应用于：

• 日志记录：只保留最近的 N 条日志。
  
• 性能监控：记录最近一段时间的 CPU 或内存使用率。
  
• 实时数据流处理：缓存最新的数据点用于分析。
  
• 轮询调度（Round-Robin）：在多个任务或资源间循环切换。
  

希望这个 CircularBuffer 的实现能对你有所启发。
感谢阅读到这里，如果感觉本文对您有帮助，请不吝评论和点赞，这也是我持续创作的动力！
也欢迎加入我的 .NET骚操作 QQ群：495782587，一起交流.NET 和 AI 的各种有趣玩法！

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！