数组栈、链表栈谁的性能更优【Go语言测试】

  刚入门Go语言，发现Go本身并没有像Java那样提供比如Stack，或是LinkedList的实现，于是基于切片的特点，封装了栈、队列、双向队列。栈也可以基于链表来实现，那到底谁的性能会更优呢，于是便有了这篇性能对比。

 本文将对比基于Go语言切片实现的栈和基于链表实现的栈的性能，文中会涉及简单的数据结构、Go语言interface、slice、基准测试等知识点。

 文中有不对的地方还望大家指出

1、栈、队列、双向队列

 栈（Stack）是一种常见的数据结构，具有先进后出（FILO）的特点，只可以在栈顶进行插入、删除、查询操作。定义栈的接口如下：

img

type Stack interface {
    //往栈中插入一个元素
    Push(int)
    
    //取出栈顶元素，如果栈为空，err!=nil
    Pop() (int, error)

    //获取栈顶元素，如果栈为空，err!=nil
    Peek() (int, error)

    //获取当前栈的大小
    GetSze() int
}

 队列（Queue）具有先进先出（FIFO）的特点，只可以从队尾插入元素，从队头取出元素。定义栈的接口如下：

img

type Queue interface {
   //对尾入队一个元素
   Enqueue(int)

   //对头出队一个元素，如果队为空，err!=nil
   Dequeue() (int, error)

   //获取队头元素，如果队为空，err!=nil
   Front() (int, error)

   //获取当前队的大小
   GetSize() int
}

 本文在实现的时候是实现了一个双向队列，让双向队列继承了栈和队列的接口，这样就可以把双向队列当做栈和队列使用啦。

 具体的，SliceList是基于Slice实现的双向队列，LinkedList是一个基于链表实现的双向队列，继承关系如下图所示。

继承关系图.png

2、SliceList简析

type SliceList struct {
   data []int
}

 切片是 Go 中的一种基本的数据结构，使用这种结构可以用来管理数据集合。切片常见的操作有 append、copy。与此同时，切片还具有可索引，可迭代的优秀特性。

 切片的结构体由3部分构成，array 是指向一个数组的指针，len 代表当前切片的长度，cap 是当前切片的容量。cap 总是大于等于 len 的。

 切片在append的时候，达到了切片的容量，会产生扩容，扩容的详细解析见参考1、2。简单描述的话，也就是切片的容量小于 1024 个元素，扩容为原来的2倍；容量大于等于1024，每次增加原来的0.25倍。扩容会首先开辟一片内存区域，然后把旧的数据拷贝过来，array指针指向新的内存区域。

 所以在用切片来实现SliceList时，在初始化SliceList的时候，可以预先指定SliceList切片数据的容量，那么之后插入数据就可以避免切片扩容而造成了额外的时间和空间的消耗。

slice.jpg

3、LinkedList简析

type LinkedList struct {
   size  int
   first *Node
   last  *Node
}
type Node struct {
    val  int
    prev *Node
    next *Node
}

 本文的LinkedList的实现参考了Java中LinkedList的实现。

 基于链表实现的双向队列，每一个节点不仅需要保留数据，还需要保留前驱和后继节点的指针，所以在空间上会比基于切片的实现消耗更多，另外在插入新的数据的时候，需要新建Node节点，对比于切片直接在地址上赋值，时间上也会有更多的消耗。

img

4、性能测试

 本文是基于Go testing包进行测试的，具体的测试方法教程见参考3、4、5。

 为了更细致的对比LinkedList和SliceList的性能，本文进行了两方面的测试。一个是顺序测试，也就是先Push一定数量的数据，然后再Peek、Pop直到栈为空；另一个是随机测试，也就是Push、Peek、Pop是随机执行的，当然栈为空的时候Peek、Pop是会返回error的，这里仅测试性能，就不做处理了。

//测试命令： go test -bench=.  -benchmem  -count=1 -benchtime=1s
func TestFunc(stack utils.Stack, fun func(stack utils.Stack)) {
   fun(stack)
}

//顺序测试：Push、Peek、Pop依次执行
func orderTestStack(stack utils.Stack) {
   for i := 0; i < 10; i++ {
      for j := 0; j < 10000; j++ {
         stack.Push(j)
      }
      for stack.GetSize() > 0 {
         stack.Peek()
         stack.Pop()
      }
   }
}

//随机测试：Push、Peek、Pop随机执行
func randomTestStack(stack utils.Stack) {
   for i := 0; i < 3*10*10000; i++ {
      switch r := rand.Intn(1000); r % 3 {
      case 0:
         stack.Push(r)
      case 1:
         stack.Peek()
      case 2:
         stack.Pop()
      }
   }
}

 如图所示，是测试结果的截图，本文关注了第三列 ns/op，第四列 B/op。

• 第三列表示每次操作需要的时间，单位是纳秒，可以基于此列来对算法的时间性能进行对比；

• 第四列表示每次操作需要的内存大小，单位是Byte，可以基于此列来对算法的空间性能进行对比。

基准测试.png

 下图是利用iData平台对以上数据进行简单分析可视化的结果。通过对比实验可以看出：

• 在顺序测试和随机测试中，LinkedList 的时间消耗和空间消耗都会比 SliceList 多得多。
• 有初始化容量的SliceList 会比没有初始化容量的SliceList 在时间、空间上更有优势。

order.png

random.png

5、总结

 通过本文的简单对比实验可以发现SliceList在时间和空间上的性能都是优于LinkedList；

 有初始化容量的SliceList的性能会优于没有初始化容量的SliceList，所以在使用Slice的时候可以注意初始化容量这一点，对性能提升会有帮助；

 LinkedList不需要连续的内存空间、SliceList需要连续的内存空间，当SliceList容量增加时，需要大的连续内存，这也是需要考虑的。

6、参考

1、go Slice 底层实现

2、go slice扩容分析

3、go test 基准测试

4、【Go API 开发实战 21】进阶 7：go test 测试你的代码

5、https://golang.org/cmd/go/#hdr-Testing_flags

6、SliceTricks

7、Stacks and Queues

有疑问加站长微信联系（非本文作者）