如何保留僅最後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個對象的列表？

回答

相關問題