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

Question

我想对特定方法进行一些性能测量，但我想平均完成所需的时间。 （这是一个 C# Winforms 应用程序，但这个问题很可能适用于其他框架。）

我有一个秒表，我在方法开始时重置它并在方法结束时停止。 我想将最后 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);
}

这似乎在某种程度上效率低下，但也许事实并非如此。

建议？

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 的第一项的成本很高。

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

这是一个简单的圆形结构。
这不需要其他解决方案所具有的数组复制或链表节点的垃圾收集。

Answer 3

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

我们曾经有过类似的要求来实现下载时间估计器，并且我们使用循环缓冲区来存储最后 N 秒中每一秒的速度。

我们对整个时间的下载速度不感兴趣，只是根据最近的活动预计大约需要多长时间，但不是最近的活动，以至于数字会到处乱跳。 （例如，如果我们只使用最后一秒来计算它）。

我们对整个时间范围不感兴趣的原因是下载速度可能在半小时内达到 1M/s，然后在接下来的 10 分钟内切换到 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.

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

另一种方法是在请求时将所有十个数字相加的函数，当将另一个值加载到缓冲区中时，该函数会比单个减法/加法慢。

Answer 4

您可能想考虑使用队列数据结构。您可以使用简单的线性列表，但效率很低。可以使用圆形数组，但必须不断调整它的大小。因此，我建议您选择队列。

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];
            }
        }
    }

Answer 6

对我来说似乎没问题。改用 LinkedList 怎么样？使用列表时，如果删除第一个项目，则所有其他项目都必须退回到一个项目。使用 LinkedList，您可以以很少的成本在列表中的任何位置添加或删除项目。然而，我不知道这会产生多大的差异，因为我们只讨论十个项目。

链表的缺点是您无法有效地访问列表的随机元素，因为链表本质上必须沿着列表“行走”，传递每个项目，直到到达您需要的项目。但对于顺序访问，链表就可以了。

Answer 7

对于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);
        }
    }
}

结果是

Array5

Array6

Array7

Array8

Array9

Answer 8

最新答案多年后，我在寻找相同的解决方案时偶然发现了这个问题。我以上述答案的组合结束，尤其是以下答案之一： cycling by 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）以获得一个表现良好的枚举器。请注意，枚举器返回从最新到最旧值的值。