CODEWITHSUNDEEP
javaalgorithmperformancecollectionsstack
Siddharth
Siddharth

Reputation: 2254

Efficiency of Java's Collection Stack data structure

Today I was writing code to implement a Stack data structure using ArrayList in Java. I extended my code to compare the efficiency of the Stack I implemented against the Stack in Collection library and result surprised me a bit. I mean I was sure that my code would be far less efficient but there were many cases where my simple code performed better (if I understand correctly). Following is the code I wrote :-

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Stack;

import customexceptions.StackUnderflowException;

public class StackArray<T> {
    private int top=-1;
    private List<T> array = new ArrayList<T>();

    public void push(T object) {
        array.add(object);
        top++;
    }

    public T pop() throws StackUnderflowException {
        if (top == -1) {
            throw new StackUnderflowException();
        }
        return array.remove(top--);
    }

    public T peek() throws StackUnderflowException {
        if (top == -1) {
            throw new StackUnderflowException();
        }
        return array.get(top);
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public static void main(String[] args) throws StackUnderflowException {
        Random random = new Random();
        for (int pow=1; pow<25; pow++) {
            StackArray<Integer> intStack = new StackArray<>();
            int size = 1<<pow;
            int i;
            int randomInt = random.nextInt(10);
            long startTime = System.currentTimeMillis();
            for(i=1; i<=size; i++) {
                intStack.push(i * randomInt);
            }
            i--;

            while(!intStack.isEmpty()) {
                int popedValue = intStack.pop();
                assert popedValue == (i * randomInt);
                i--;
            }
            assert i == 0;
            intStack = null;
            long endTime = System.currentTimeMillis();
            System.out.println("Time taken StackArray for 2^" + pow 
                    + " ints = " + (endTime - startTime) + " ms") ;

            randomInt = random.nextInt(10);
            startTime = System.currentTimeMillis();
            Stack<Integer> collectionStack = new Stack<>();
            for(i=1; i<=size; i++) {
                collectionStack.push(i * randomInt);
            }
            i--;

            while(!collectionStack.isEmpty()) {
                int popedValue = collectionStack.pop();
                assert popedValue == (i * randomInt);
                i--;
            }
            assert i == 0;
            endTime = System.currentTimeMillis();
            System.out.println("Time taken by Collection Stack for 2^" +
                    pow + " int = " + (endTime - startTime) + " ms");
        }
    }
}

And below is the output I got for the same :-

Time taken StackArray for 2^1 ints = 0 ms
Time taken by Collection Stack for 2^1 int = 0 ms
Time taken StackArray for 2^2 ints = 0 ms
Time taken by Collection Stack for 2^2 int = 0 ms
Time taken StackArray for 2^3 ints = 0 ms
Time taken by Collection Stack for 2^3 int = 0 ms
Time taken StackArray for 2^4 ints = 0 ms
Time taken by Collection Stack for 2^4 int = 0 ms
Time taken StackArray for 2^5 ints = 1 ms
Time taken by Collection Stack for 2^5 int = 0 ms
Time taken StackArray for 2^6 ints = 0 ms
Time taken by Collection Stack for 2^6 int = 0 ms
Time taken StackArray for 2^7 ints = 0 ms
Time taken by Collection Stack for 2^7 int = 0 ms
Time taken StackArray for 2^8 ints = 0 ms
Time taken by Collection Stack for 2^8 int = 1 ms
Time taken StackArray for 2^9 ints = 0 ms
Time taken by Collection Stack for 2^9 int = 1 ms
Time taken StackArray for 2^10 ints = 0 ms
Time taken by Collection Stack for 2^10 int = 1 ms
Time taken StackArray for 2^11 ints = 0 ms
Time taken by Collection Stack for 2^11 int = 1 ms
Time taken StackArray for 2^12 ints = 2 ms
Time taken by Collection Stack for 2^12 int = 1 ms
Time taken StackArray for 2^13 ints = 3 ms
Time taken by Collection Stack for 2^13 int = 3 ms
Time taken StackArray for 2^14 ints = 5 ms
Time taken by Collection Stack for 2^14 int = 5 ms
Time taken StackArray for 2^15 ints = 3 ms
Time taken by Collection Stack for 2^15 int = 7 ms
Time taken StackArray for 2^16 ints = 9 ms
Time taken by Collection Stack for 2^16 int = 15 ms
Time taken StackArray for 2^17 ints = 12 ms
Time taken by Collection Stack for 2^17 int = 22 ms
Time taken StackArray for 2^18 ints = 7 ms
Time taken by Collection Stack for 2^18 int = 21 ms
Time taken StackArray for 2^19 ints = 16 ms
Time taken by Collection Stack for 2^19 int = 51 ms
Time taken StackArray for 2^20 ints = 28 ms
Time taken by Collection Stack for 2^20 int = 94 ms
Time taken StackArray for 2^21 ints = 58 ms
Time taken by Collection Stack for 2^21 int = 201 ms
Time taken StackArray for 2^22 ints = 111 ms
Time taken by Collection Stack for 2^22 int = 318 ms
Time taken StackArray for 2^23 ints = 2338 ms
Time taken by Collection Stack for 2^23 int = 2189 ms
Time taken StackArray for 2^24 ints = 5940 ms
Time taken by Collection Stack for 2^24 int = 3748 ms

In the above example you can find so many cases where my algorithm for Stack took less time in pushing and popping operation. Is there any specific reason for it? Or this is an erratic result? Or may be there is scope of improvement in Collection library?

Upvotes: 2

Views: 735

Answers (1)

Nicolas Filotto
Nicolas Filotto

Reputation: 44965

Your implementation is faster simply because Stack is thread safe and your implementation is not, so you have the overhead added by the synchronized blocks that you have in the class Stack that you don't have in your class.

Upvotes: 2

Related Questions