Performance : which is faster calling reverse on a stack or popping items into an array

Question

Hi,

I was wondering which implementation would have better performance:

I need to clear all items out of a stack except the first 10 at the head.

These 10 must then be placed into the stack in their orginal order.

I thought of 2 approaches

the first:

FilterRecord[] records = new FilterRecord[10];

       for (int i = 0; i < records.Length; i++)
       {
           records[i] = _InternalCollection.Pop();
       }

       _InternalCollection.Clear();

       for (int i = records.Length - 1; i >= 0; i--)
       {
           _InternalCollection.Push(records[i]);
       }

The second:

int count = _InternalCollection.Count - 10;
               _InternalCollection.Reverse();


               for (int i = 0; i < count; i++)
               {
                   _InternalCollection.Pop();
               }

               _InternalCollection.Reverse();

Any help or guidelines or other impemenations would be welcome.

Answer 1

That depends, you're assuming that the Reverse() method isn't doing exactly that. Only two ways to know: 1.) run your code and tell us 2.) look up the implementation of Reverse().

Answer 2

Your first algorithm has two for-loops, so O(2N). Your second algorithm has one for loop, but we have to assume that internally Reverse() is an O(N) operation, so its O(3N).

I'm not sure if the Clear() call is O(N) or O(C) in your first algorithm.

Answer 3

Its often hard to tell on these types of things. Just make an insanely large stack, call both and time them. Then you'll know.

Answer 4

It depends. There's two things you can do:

• test it by running it for a couple hundred iterations (less or more depending on the size)
• look at their implementations

Analyzing the method in which a stack is implemented (conceptually), using reverse would be the slowest as it would have to pop everything of the stack, and then pop them back in, in the opposite order. If internally, it just selects a different starting index of where to start popping, it could be faster.

Either way, simply put, using Reverse() seems inefficient as you're performing that operation twice.

Answer 5

I would suggest taking a look at the actual implementation of Reverse() - you may find the .Net Reflector useful for that.

Answer 6

If there are few items in the stack, there will be so little difference that it's not worth optimising.

If there are many items in the stack, this would be the fastest:

FilterRecord[] records = new FilterRecord[10];

for (int i = 0; i < records.Length; i++) {
   records[i] = _InternalCollection.Pop();
}

_InternalCollection = new Stack<FilterRecord>();

for (int i = records.Length - 1; i >= 0; i--) {
   _InternalCollection.Push(records[i]);
}

I.e. just throw away the current stack after you get the items that you want to keep, and let the garbage collector take care of it. If you use the Clear method, that will remove the references from the stack but it will keep it's capacity.

As you only touch ten of the items in the stack regardless of how many there are, this is an O(1) operation instead of an O(n) operation.

(Note that you use the size of the array when you declare it, not the hightest index.)

Answer 7

I think that avoiding popping items off the stack will improve your code's performance more than the alternative between the two approaches you suggest. I would recommend allocating a new stack with the contents of the last item on the stack using linq like so:

var newStack = new Stack<FilterRecord>( 
   _InternalCollection.Take( 10 )
                      .Reverse() );

_InternalCollection = newStack;

If you're not using generics, you can do the same with the built in iterator:

var iterator = _InternalCollection.GetEnumerator();
int i = 9;
while( iterator.MoveNext() && i-- >= 0 )
{
   newStack.Push( iterator.Current );
}
_InternalCollection = newStack;

Answer 8

How about not using a stack in the first place? How about wrapping a LinkedList and then use the RemoveLast method to do what you need?

Some rough code, needs more work, but you get the basic idea:

    public class CustomStack<T>
    {
        private LinkedList<T> list;

        public CustomStack()
        {
            list = new LinkedList<T>();
        }

        public void Push(T item)
        {
            list.AddFirst(item);
        }

        public T Pop()
        {

            var result = list.First.Value;
            list.RemoveFirst();
            return result;
        }

        public void TrimLast(int amountToLeave)
        {
            while (list.Count > amountToLeave)
            {
                list.RemoveLast();
            }
        }
    }

Answer 9

I think that you can pretty much count on the Double reverse being slower. Your running time for 1) is constant (O(1)) in terms of _InternalCollection.Length (assuming Clear is constant time) and O(n) in terms of the number of elements you want to keep. 2) will get slower, linearly the bigger _InternalCollection is (O(n))

You might also want to consider changing your _InternalCollection into a Deque (Double ended queue). A Deque supports O(1) amortized time to add/remove items from either end. Of course (AFAIK) there isn't a standard implementation so you would have to roll your own or use a third party implementation.

Answer 10

memcpy the last 10 items on the stack to where you want them to be.

Then declare the stack to be 10 items long.