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

我想做一些特定方法的性能测量，但我想平均完成所需的时间。 （这是一个C＃Winforms应用程序，但是这个问题很可能适用于其他框架。）如何保留仅最后n个对象的列表？

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

这看起来效率不高，但也许不是这样。

对此提出建议？

来源

2011-06-17 JYelton

使用探查器有什么问题？ –

@Brandon，我计划使用平均值显示给用户，作为解析对象所用时间的指示器。这是图形翻译工具的一部分。 – JYelton

您可以创建自定义集合：

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>的第一个项目是昂贵的。

来源

2011-06-17 22:54:34

短而美丽。 – Andrew

似乎对我来说没问题。那么如何使用LinkedList呢？使用列表时，如果您删除第一个项目，则所有其他项目都必须向后退一个项目。使用LinkedList，您可以以极低的成本在列表中的任何位置添加或移除项目。但是，我不知道这会造成多大的差异，因为我们只谈十个项目。

链接列表的折衷是你不能有效地访问列表中的随机元素，因为链表必须沿列表“走动”，传递每个项目，直到它到达一个你需要。但对于顺序访问，链接列表很好。

来源

2011-06-17 22:49:44 Ord

为了获得最佳性能，您可以只使用一个long数组而不是一个列表。

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

我们对整个时间的下载速度没有兴趣，根据最近的活动大概需要多长时间，但不是那么最近数字会跳到所有的地方（例如，如果我们只是用最后一秒来计算它）。

我们对整个时间段不感兴趣的原因是，下载可能会在一个半小时内达到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.

这应该是很容易适应自己的需求。总和是一个很好的功能来“缓存”信息，这可能会让你的代码更快。我的意思是：如果你需要计算总和或平均值，那么只有当数据发生变化时，才能解决这个问题，并使用最少的必要计算。

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

来源

2011-06-17 22:55:06 paxdiablo

您可能想要考虑使用Queue数据结构。你可以使用简单的线性列表，但它是完全没有效率的。可以使用圆形阵列，但必须不断调整大小。所以，我建议你和Queue一起去。

来源

2011-06-17 22:57:03

+1感谢Queue的建议，这是我最终使用的。 @Thomas有一些代码示例可以使用它，这让我感到很多帮助。 – JYelton

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

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

来源

2011-06-17 23:33:00

我必须执行一段时间，在我看到您的答案之前，我已经实现了一个队列，但是这绝对是为了避免您提到的一些性能问题。 – JYelton

一个小问题，你将'times'初始化为零长度，显然这个数字应该改变为缓冲区应该有的深度。 – JYelton

我需要在数组中保留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]; 
      } 
     } 
    }

来源

2017-05-28 14:10:00 Saulius

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

回答

相关问题