Làm cách nào để giữ một danh sách chỉ các đối tượng n cuối cùng?

Question

Tôi muốn làm một số đo lường hiệu suất của một phương pháp cụ thể, nhưng tôi muốn trung bình thời gian cần để hoàn thành. (Đây là ứng dụng C# Winforms, nhưng câu hỏi này cũng có thể áp dụng cho các khung công tác khác.)

Tôi có Đồng hồ bấm giờ để đặt lại ở đầu phương thức và dừng ở cuối. Tôi muốn lưu trữ 10 giá trị cuối cùng trong danh sách hoặc mảng. Mỗi giá trị mới được thêm vào sẽ đẩy giá trị cũ nhất ra khỏi danh sách.

Định kỳ, tôi sẽ gọi một phương thức khác sẽ trung bình tất cả các giá trị được lưu trữ.

Tôi có đúng khi nghĩ rằng cấu trúc này là bộ đệm tròn không?

Làm cách nào để tạo bộ đệm như vậy với hiệu suất tối ưu? Ngay bây giờ tôi có những điều sau đây:

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

Điều này dường như không hiệu quả bằng cách nào đó, nhưng có lẽ không.

Đề xuất?

Answer 1

Bạn có thể tạo ra một bộ sưu tập tùy chỉnh:

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(); 
    } 
} 

giải pháp hiện tại của bạn hoạt động, nhưng nó không hiệu quả, bởi vì loại bỏ các mục đầu tiên của một List<T> là tốn kém.

Answer 2

Dường như tôi không sao. Điều gì về việc sử dụng một LinkedList thay thế? Khi sử dụng Danh sách, nếu bạn loại bỏ mục đầu tiên, tất cả các mục khác phải được quay trở lại một mục. Với LinkedList, bạn có thể thêm hoặc xóa các mục ở bất kỳ đâu trong danh sách với chi phí rất ít. Tuy nhiên, tôi không biết có bao nhiêu sự khác biệt này, vì chúng ta chỉ nói về mười vật phẩm.

Việc cân bằng danh sách được liên kết là bạn không thể truy cập hiệu quả các phần tử ngẫu nhiên trong danh sách, vì danh sách được liên kết về cơ bản phải "đi bộ" dọc theo danh sách, chuyển từng mục cho đến khi nó đến nhu cầu. Nhưng đối với truy cập tuần tự, danh sách liên kết là tốt.

Answer 3

Để có hiệu suất tối ưu, bạn có thể chỉ cần sử dụng một chuỗi thời lượng dài thay vì danh sách.

Chúng tôi đã có yêu cầu tương tự tại một thời điểm để triển khai trình ước tính thời gian tải xuống và chúng tôi đã sử dụng bộ đệm tròn để lưu tốc độ trên mỗi N giây cuối cùng.

Chúng tôi không quan tâm đến tốc độ tải xuống trong toàn bộ thời gian, chỉ mất khoảng thời gian dự kiến ​​dựa trên hoạt động gần đây nhưng không phải là số vì vậy gần đây. chẳng hạn như nếu chúng ta chỉ sử dụng giây cuối cùng để tính toán nó).

Lý do chúng tôi không quan tâm đến toàn bộ khung thời gian là tải xuống có thể 1M/s trong nửa giờ sau đó chuyển lên 10M/giây trong mười phút tiếp theo. Nửa giờ đầu tiên đó sẽ giảm tốc độ trung bình khá nghiêm trọng, mặc dù thực tế bạn đang tải xuống khá nhanh.

Chúng tôi đã tạo bộ đệm tròn với mỗi ô giữ số tiền được tải xuống trong khoảng thời gian 1 giây. Kích thước bộ đệm tròn là 300, cho phép 5 phút dữ liệu lịch sử, và mỗi ô được khởi tạo bằng không. Trong trường hợp của bạn, bạn sẽ chỉ cần mười tế bào.

Chúng tôi cũng duy trì tổng số (tổng của tất cả các mục trong bộ đệm, do đó ban đầu là 0) và số đếm (ban đầu bằng không, rõ ràng).

Mỗi giây, chúng ta sẽ tìm ra bao nhiêu dữ liệu đã được tải về từ giây cuối cùng và sau đó:

• trừ ô hiện từ tổng số.
• đặt hình hiện tại vào ô đó và tiến lên con trỏ của ô.
• thêm con số hiện tại đó vào tổng số.
• tăng số lượng nếu nó không phải là 300.
• cập nhật hình được hiển thị cho người dùng, dựa trên tổng số/số.

Về cơ bản, trong pseudo-code:

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. 

Điều đó sẽ dễ dàng thích nghi với yêu cầu riêng của bạn. Tổng hợp là một tính năng tuyệt vời cho thông tin "bộ nhớ cache" có thể làm cho mã của bạn nhanh hơn. Ý tôi là: nếu bạn cần tính tổng hoặc trung bình, bạn chỉ có thể làm việc khi dữ liệu thay đổi và sử dụng các phép tính cần thiết tối thiểu.

Phương án thay thế sẽ là một hàm được cộng tất cả mười số khi được yêu cầu, cái gì đó sẽ chậm hơn số đơn trừ/thêm khi tải giá trị khác vào bộ đệm.

Answer 4

Thay vào đó, bạn có thể muốn sử dụng cấu trúc dữ liệu Hàng đợi. Bạn có thể sử dụng một danh sách tuyến tính đơn giản, nhưng nó hoàn toàn không hiệu quả. Một mảng tròn có thể được sử dụng nhưng sau đó bạn phải thay đổi kích thước nó liên tục. Vì vậy, tôi đề nghị bạn đi với hàng đợi.

Answer 5

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

Đây là cấu trúc hình tròn đơn giản. Điều này không yêu cầu sao chép mảng hoặc thu gom rác của các nút danh sách liên kết mà các giải pháp khác có.

Answer 6

Tôi cần giữ 5 điểm cuối cùng trong một mảng và tôi đã đưa ra giải pháp đơn giản này. Hy vọng nó sẽ giúp một số.

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