Reputation: 2096

PeekRange on a stack in C#?

I have a program that needs to store data values and periodically get the last 'x' data values.

It initially thought a stack is the way to go but I need to be able to see more than just the top value - something like a PeekRange method where I can peek the last 'x' number of values.

At the moment I'm just using a list and get the last, say, 20 values like this:

var last20 = myList.Skip(myList.Count - 20).ToList();

The list grows all the time the program runs, but I only ever want the last 20 values. Could someone give some advice on a better data structure?

Upvotes: 0

Answers (5)

Dan Tao

Reputation: 128337

You said stack, but you also said you only ever want the last 20 items. I don't think these two requirements really go together.

I would say that Johannes is right about a ring buffer. It is VERY easy to implement this yourself in .NET; just use a Queue<T> and once you reach your capacity (20) start dequeuing (popping) on every enqueue (push).

If you want your PeekRange to enumerate from the most recent to least recent, you can defineGetEnumerator to do somehing likereturn _queue.Reverse().GetEnumerator();

Upvotes: 1

ollb

Reputation: 1464

Well since you mentioned the stack, I guess you only need modifications at the end of the list?

In that case the list is actually a nice solution (cache efficient and with fast insertion/removal at the end). However your way of extracting the last few items is somewhat inefficient, because IEnumerable<T> won't expose the random access provided by the List. So the Skip()-Implementation has to scan the whole List until it reaches the end (or do a runtime type check first to detect that the container implements IList<T>). It is more efficient, to either access the items directly by index, or (if you need a second array) to use List<T>.CopyTo().

If you need fast removal/insertion at the beginning, you may want to consider a ring buffer or (doubly) linked list (see LinkedList<T>). The linked list will be less cache-efficient, but it is easy and efficient to navigate and alter from both directions. The ring buffer is a bit harder to implement, but will be more cache- and space-efficient. So its probably better if only small value types or reference types are stored. Especially when the buffers size is fixed.

Upvotes: 1