How do I keep a list of only the last n objects?

Question

I want to do some performance measuring of a particular method, but I'd like to average the time it takes to complete. (This is a C# Winforms application, but this question could well apply to other frameworks.)

I have a Stopwatch which I reset at the start of the method and stop at the end. I'd like to store the last 10 values in a list or array. Each new value added should push the oldest value off the list.

Periodically I will call another method which will average all stored values.

Am I correct in thinking that this construct is a circular buffer?

How can I create such a buffer with optimal performance? Right now I have the following:

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

This seems inefficient somehow, but perhaps it's not.

Suggestions?

Dinothere

What's wrong with using the profiler? – Colombes

@Brandon, I plan on using the averaged value to display to users, as an indicator of how long parsing an object is taking. This is part of a graphic translation utility. – Dinothere

Answer 1

You could create a custom collection:

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

Your current solution works, but it's inefficient, because removing the first item of a List<T> is expensive.

Morice

Short and beautiful. – Guertin

A thing of beauty is a joy for ever, so happy to see such elegant code :) – Koblas

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

Here is a simple circular structure. This requires none of the array copying or garbage collection of linked list nodes that the other solutions have.

Suicide

I'll have to implement this some time, I already implemented a queue before I saw your answer, but this definitely looks to avoid some performance hits as you mention. – Dinothere

One minor point, you initialize times to a zero length, obviously this number should be changed to whatever depth the buffer should have. – Dinothere

@Dinothere years later I combined this one with the queue implementation in my answer – Wondering

Answer 3

For optimal performance, you can probably just use an array of longs rather than a list.

We had a similar requirement at one point to implement a download time estimator, and we used a circular buffer to store the speed over each of the last N seconds.

We weren't interested in how fast the download was over the entire time, just roughly how long it was expected to take based on recent activity but not so recent that the figures would be jumping all over the place (such as if we just used the last second to calculate it).

The reason we weren't interested in the entire time frame was that a download could so 1M/s for half an hour then switch up to 10M/s for the next ten minutes. That first half hour will drag down the average speed quite severely, despite the fact that you're now downloading quite fast.

We created a circular buffer with each cell holding the amount downloaded in a 1-second period. The circular buffer size was 300, allowing for 5 minutes of historical data, and every cell was initialised to zero. In your case, you would only need ten cells.

We also maintained a total (the sum of all entries in the buffer, so also initially zero) and the count (initially zero, obviously).

Every second, we would figure out how much data had been downloaded since the last second and then:

• subtract the current cell from the total.
• put the current figure into that cell and advance the cell pointer.
• add that current figure to the total.
• increase the count if it wasn't already 300.
• update the figure displayed to the user, based on total / count.

Basically, in 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.

That should be easily adaptable to your own requirements. The sum is a nice feature to "cache" information which may make your code even faster. By that I mean: if you need to work out the sum or average, you can work it out only when the data changes, and using the minimal necessary calculations.

The alternative would be a function which added up all ten numbers when requested, something that would be slower than the single subtract/add when loading another value into the buffer.

Inbred

Answer 4

You may want to look at using the Queue data structure instead. You could use a simple linear List, but it is wholly inefficient. A circular array could be used but then you must resize it constantly. Therefore, I suggest you go with the Queue.

Protecting

+1 thanks for the suggestion of Queue, it's what I wound up using. @Thomas had some code examples to go with it, which I felt helped a lot. – Dinothere

Answer 5

I needed to keep 5 last scores in a array and I came up with this simple solution. Hope it will help some one.

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

Leavening

Answer 6

Seems okay to me. What about using a LinkedList instead? When using a List, if you remove the first item, all of the other items have to be bumped back one item. With a LinkedList, you can add or remove items anywhere in the list at very little cost. However, I don't know how much difference this would make, since we're only talking about ten items.

The trade-off of a linked list is that you can't efficiently access random elements of the list, because the linked list must essentially "walk" along the list, passing each item, until it gets to the one you need. But for sequential access, linked lists are fine.

Ardyth

Answer 7

For java, it could be that way

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

It could be started that way

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

The result is

Array5

Array6

Array7

Array8

Array9

Hassi

Answer 8

Years after the latest answer I stumbled on this questions while looking for the same solution. I ended with a combination of the above answers especially the one of: cycling by agent-j and of using a queue by 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();
}

I had to forego the very elegant one-liner of j-agent: ct = (ct + 1) % times.Length; because I needed to detect when we circled back (through hasCycled) to have a well behaving enumerator. Note that the enumerator returns values from most-recent to oldest value.

Wondering