如何保留仅包含最后n个对象的列表？

Question

我想对一个特定的方法进行一些性能测量，但我想要计算完成该方法所需时间的平均值。（这是一个 C# Winforms 应用程序，但这个问题也同样适用于其他框架） 我有一个 Stopwatch 对象，在方法开始时重置，结束时停止。我想将最后 10 个时间值存储到列表或数组中，每添加一个新值就会将最旧的值推出列表。

然后，我会定期调用另一个方法来计算所有存储值的平均值。

我是否正确地认为这个结构是一个循环缓冲区？

如何创建具有最佳性能的缓冲区？目前我的代码如下：

List<long> PerfTimes = new List<long>(10);

// ...

private void DoStuff()
{
    MyStopWatch.Restart();
    // ...
    MyStopWatch.Stop();
    PerfTimes.Add(MyStopWatch.ElapsedMilliseconds);
    if (PerfTimes.Count > 10) PerfTimes.RemoveAt(0);
}

这些代码看起来有点低效，但也许并不是。

有什么建议吗？

- JYelton

---

使用分析器有什么问题吗？ - Brandon Moretz

@Brandon，我计划使用平均值来向用户展示一个指标，即解析对象需要多长时间。这是图形翻译工具的一部分。 - JYelton

Answer 1

您可以创建一个自定义集合：

class SlidingBuffer<T> : IEnumerable<T>
{
    private readonly Queue<T> _queue;
    private readonly int _maxCount;

    public SlidingBuffer(int maxCount)
    {
        _maxCount = maxCount;
        _queue = new Queue<T>(maxCount);
    }

    public void Add(T item)
    {
        if (_queue.Count == _maxCount)
            _queue.Dequeue();
        _queue.Enqueue(item);
    }

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

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

您目前的解决方案可以工作，但效率较低，因为删除 List<T> 的第一个项目是昂贵的。

- Thomas Levesque

---

简短而优美。 - Andrew

优美的代码永远令人愉悦，很高兴看到这样优雅的代码 :) - Martin

Answer 2

private int ct = 0;
private long[] times = new long[10];

void DoStuff ()
{
   ...
   times[ct] = MyStopWatch.ElapsedMilliseconds;
   ct = (ct + 1) % times.Length; // Wrap back around to 0 when we reach the end.
}

这是一个简单的循环结构。与其他解决方案需要进行数组复制或链表节点的垃圾收集不同，这种方法没有这些问题。

- agent-j

---

我得抽时间来实现这个，之前在看到你的回答之前已经实现了一个队列，但是你提到的这个肯定能避免一些性能问题。 - JYelton

一个小细节，您将“times”初始化为零长度，显然这个数字应更改为缓冲区应具有的深度。 - JYelton

@JYelton 多年后，我将这个实现与我的 答案 中的队列实现结合起来。 - Cohen

Answer 3

为了获得最佳性能，您可以使用长整型数组而不是列表。

我们曾经有一个类似的需求，需要实现一个下载时间估算器，我们使用循环缓冲区来存储过去每个秒钟的速度。

我们并不关心整个时间内下载速度有多快，只是根据最近的活动大致估计需要多长时间完成下载，但是又不要太近，否则数据会跳动（例如如果我们只使用最后一秒钟进行计算）。

我们不关心整个时间范围的原因是，下载可能在半个小时内以1M/s的速度进行，然后在接下来的十分钟内切换到10M/s。那前半个小时将会严重拉低平均速度，尽管你现在下载速度很快。

我们创建了一个循环缓冲区，每个单元格都保存了在1秒钟内下载的数量。循环缓冲区大小为300，允许5分钟的历史数据，并且每个单元格最初都初始化为零。在您的情况下，您只需要十个单元格。

我们还维护了一个总数（缓冲区中所有条目的总和，因此最初也为零）和计数（最初为零，显然）。

每秒钟，我们会计算自上次以来下载了多少数据，然后：

- 从总数中减去当前单元格。 - 将当前数字放入该单元格并将单元格指针向前移动。 - 将当前数字添加到总数中。 - 如果计数不是300，则增加计数。 - 根据总数/计数更新向用户显示的数字。

基本上，伪代码如下：

def init (sz):
    buffer = new int[sz]
    for i = 0 to sz - 1:
        buffer[i] = 0 
    total = 0
    count = 0
    index = 0
    maxsz = sz

def update (kbps):
    total = total - buffer[index] + kbps   # Adjust sum based on deleted/inserted values.
    buffer[index] = kbps                   # Insert new value.
    index = (index + 1) % maxsz            # Update pointer.
    if count < maxsz:                      # Update count.
        count = count + 1
    return total / count                   # Return average.

这应该很容易适应您自己的要求。总和是一种很好的功能，可以“缓存”信息，这可能会使您的代码更快。我的意思是：如果您需要计算总和或平均值，则仅在数据发生更改时才能计算出来，并且使用最少的必要计算。

另一种选择是在请求时添加全部十个数字的函数，这比加载另一个值到缓冲区时进行单个减法/加法的速度慢。

- paxdiablo

Answer 4

你可能想要考虑使用队列数据结构。你可以使用简单的线性列表，但这是完全低效的。可以使用循环数组，但那样你必须不断地调整大小。因此，我建议你选择队列。

- user195488

---

+1 感谢队列建议，这正是我最终使用的。@Thomas 还提供了一些代码示例，我觉得非常有帮助。 - JYelton

Answer 5

我需要在数组中保留最近的5个分数，我想出了这个简单的解决方案。希望能对某些人有所帮助。

void UpdateScoreRecords(int _latestScore){
        latestScore = _latestScore;
        for (int cnt = 0; cnt < scoreRecords.Length; cnt++) {
            if (cnt == scoreRecords.Length - 1) {
                scoreRecords [cnt] = latestScore;
            } else {
                scoreRecords [cnt] = scoreRecords [cnt+1];
            }
        }
    }

- Saulius

Answer 6

多年后，当我寻找同样的解决方案时，我偶然发现了这个问题的最新答案。我最终采用了上述答案的组合，特别是 agent-j 的循环方法 和 Thomas Levesque 的队列方法。

public class SlidingBuffer<T> : IEnumerable<T>
{
    protected T[] items;
    protected int index = -1;
    protected bool hasCycled = false;

    public SlidingBuffer(int windowSize) 
    {
        items = new T[windowSize];
    }

    public void Add(T item)
    {
        index++;
        if (index >= items.Length) {
            hasCycled = true;
            index %= items.Length;
        }

        items[index] = item;
    }

    public IEnumerator<T> GetEnumerator()
    {
        if (index == -1)
            yield break;

        for (int i = index; i > -1; i--)
        {
            yield return items[i];
        }

        if (hasCycled) 
        {
            for (int i = items.Length-1; i > index; i--)
            {
                yield return items[i];
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

我不得不放弃j-agent非常优雅的一行代码：ct = (ct + 1) % times.Length;，因为我需要检测当我们通过hasCycled回到起点时，枚举器能够正常工作。请注意，枚举器返回从最近到最旧的值。

- Cohen

Answer 7

对我来说看起来还不错。那么使用LinkedList呢？当使用List时，如果删除第一个项目，则所有其他项目都必须向后移动一个项目。使用LinkedList，您可以在列表中的任何位置添加或删除项目，成本非常低。但是，我不知道这会有多大的差异，因为我们只谈论十个项目。

链表的权衡是，您无法有效地访问列表的随机元素，因为链表必须基本上“遍历”整个列表，传递每个项目，直到它到达您需要的项目。但对于顺序访问，链表很好。

- Ord

Answer 8

对于Java来说，可能是这样的

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class SlidingBuffer<T> implements Iterable<T>{
    private Queue<T> _queue;
    private int _maxCount;

    public SlidingBuffer(int maxCount) {
        _maxCount = maxCount;
        _queue =  new LinkedList<T>();
    }

    public void Add(T item) {
        if (_queue.size() == _maxCount)
            _queue.remove();
        _queue.add(item);
    }

    public Queue<T> getQueue() {
        return _queue;
    }

    public Iterator<T> iterator() {
        return  _queue.iterator();
    }
}

可以这样开始

public class ListT {

    public static void main(String[] args) {
        start();
    }

    private static void start() {
        SlidingBuffer<String> sb = new SlidingBuffer<>(5);
        sb.Add("Array1");
        sb.Add("Array2");
        sb.Add("Array3");
        sb.Add("Array4");
        sb.Add("Array5");
        sb.Add("Array6");
        sb.Add("Array7");
        sb.Add("Array8");
        sb.Add("Array9");

        //Test printout
        for (String s: sb) {
            System.out.println(s);
        }
    }
}

结果是

数组5

数组6

数组7

数组8

数组9

- Guenter Metzner