玩转数据结构（五）数组栈和链表栈性能对比

分手后的思念是犯贱 2022-05-21 08:28 193阅读 0赞

在之前的博客中，分别实现了基于数组的栈和基于链表的栈。

下面来使用代码对比我们自己实现的栈的性能差异：

private static double testStack(Stack<Integer> s, int opCnt) {
            long startTime = System.nanoTime();
    
            for (int i = 0; i < opCnt; i++) {
                s.push(i);
            }
    
            for (int i = 0; i < opCnt; i++) {
                s.pop();
            }
    
            long endTime = System.nanoTime();
    
            return (endTime - startTime) / 1000000000.0;
        }

上面的代码实现：对栈进行opCnt次入栈和出栈操作，记录所消耗的时间。(注：nonoTime的单位是ns，将结果转换为s，除以10的9次方)

首先将opCnt设置为10 0000 来看看性能差异：

public static void main(String[] args) {
            ArrayStack<Integer> arrayStack = new ArrayStack<Integer>();
            LinkedStack<Integer> linkedStack = new LinkedStack<Integer>();
            int opCnt = 100000;
            double time1 = testStack(arrayStack, opCnt);
            double time2 = testStack(linkedStack, opCnt);
            System.out.println("arrayStack:" + time1 + "s");
            System.out.println("linkedStack:" + time2 + "s");
    
        }

结果：

arrayStack:0.020232116s
    linkedStack:0.016551687s

将opCnt设置为100 0000：

结果：

arrayStack:0.094751187s
    linkedStack:0.657009347s

将opCnt设置为1000 0000：

arrayStack:3.780388172s
    linkedStack:9.333468302s

总结：

基于数组的栈是在数组尾部进行入栈和出栈操作，因此实现复杂度为O（1）；

基于链表的栈是在链表头部进行入栈和出栈操作，因此实现复杂度也为O（1）；

因此两者的性能不会差很多，在opCnt=1000 0000时，arrayStack的性能比linkedStack性能要好。原因是linkedStack要进行大量的new操作，在opCnt较小的情况下，体现不出性能差异；而在操作次数大时，arrayStack性能优势就体现出来了。

当前这种性能的比较还是比较粗糙的，但是也能粗略的反映问题。