不同栈的性能比较

测试与分析由动态数组，链表实现的栈之间的性能差异

我们定义了一个 StackTest 类用来测试由 数组 和 链表实现的栈的性能差异

test 方法的逻辑非常简单, 测试 opCount 次 push 操作和 pop 操作, 并计算时间

public class StackTest {

    public  static  double test(Stack<Integer> stack, int opCount){
        long startTime =System.nanoTime();

        Random rd =new Random();

        for (int i = 0; i < opCount; i++) {
            stack.push(rd.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0; i < opCount; i++) {
            stack.pop();
        }

        long endTime =System.nanoTime();
        return (endTime-startTime)/1000000000.0;
    }

    public static void main(String[] args) {

        //测试有底层由数组和链表 实现的栈的性能差异
        LinkedListStack<Integer> stack1 = new LinkedListStack<>();
        ArrayStack<Integer> stack2= new ArrayStack<>();
        int opCount=100000;

        System.out.println("LinkedListStack花费时间:"+test(stack1,opCount)+" s.");
        System.out.println("StackArray花费时间:"+test(stack2,opCount)+" s.");

    }
}

在 100000 次push 和 pop 操作以后输出如下:

LinkedListStack花费时间:0.017644 s.
StackArray花费时间:0.0205363 s.

可以看出: 数组栈 是要比 链表栈略快的

加大数据规模

我们修改数据规模, 进行 1000000 次 push 和 pop 操作

LinkedListStack花费时间:0.363644 s.
StackArray花费时间:0.0929164 s.

我们发现加大了数据规模以后, 链表栈反而处于性能上的劣势

分析一下

数组栈的开销主要是 resize 操作. 随着数据规模的增大, resize 的频率是在不断的降低的,因为我们实现的 Array 进行 resize时一次就扩大为原来的两倍, 存储空间指数级上升.

换句话话说, 随着数据规模的增大, resize 操作的均摊开销将会越来越小.

链表栈的开销主要是每一次增加节点都需要 new 一个 新的对象. 随着数据规模的增大, 操作系统寻找一片新的空间将会越来越困难, 开销将变得越来越大.

总结一下, 数组栈 适合 大规模数据 以及 数据规模较为稳定 的场景; 链表栈 适合 小数据规模 且 数据规模不稳定 的场景.