午夜人妻人人操,4455永久

? 剛?cè)腴TGo語言，發(fā)現(xiàn)Go本身并沒有像Java那樣提供比如Stack，或是LinkedList的實(shí)現(xiàn)，于是基于切片的特點(diǎn)，封裝了棧、隊(duì)列、雙向隊(duì)列。棧也可以基于鏈表來實(shí)現(xiàn)，那到底誰的性能會(huì)更優(yōu)呢，于是便有了這篇性能對(duì)比。

?本文將對(duì)比基于Go語言切片實(shí)現(xiàn)的棧和基于鏈表實(shí)現(xiàn)的棧的性能，文中會(huì)涉及簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)、Go語言interface、slice、基準(zhǔn)測(cè)試等知識(shí)點(diǎn)。

?文中有不對(duì)的地方還望大家指出

1、棧、隊(duì)列、雙向隊(duì)列

?棧（Stack）是一種常見的數(shù)據(jù)結(jié)構(gòu)，具有先進(jìn)后出（FILO）的特點(diǎn)，只可以在棧頂進(jìn)行插入、刪除、查詢操作。定義棧的接口如下：

img

type Stack interface {
    //往棧中插入一個(gè)元素
    Push(int)
    
    //取出棧頂元素，如果棧為空，err!=nil
    Pop() (int, error)

    //獲取棧頂元素，如果棧為空，err!=nil
    Peek() (int, error)

    //獲取當(dāng)前棧的大小
    GetSze() int
}

?隊(duì)列（Queue）具有先進(jìn)先出（FIFO）的特點(diǎn)，只可以從隊(duì)尾插入元素，從隊(duì)頭取出元素。定義棧的接口如下：

img

type Queue interface {
   //對(duì)尾入隊(duì)一個(gè)元素
   Enqueue(int)

   //對(duì)頭出隊(duì)一個(gè)元素，如果隊(duì)為空，err!=nil
   Dequeue() (int, error)

   //獲取隊(duì)頭元素，如果隊(duì)為空，err!=nil
   Front() (int, error)

   //獲取當(dāng)前隊(duì)的大小
   GetSize() int
}

?本文在實(shí)現(xiàn)的時(shí)候是實(shí)現(xiàn)了一個(gè)雙向隊(duì)列，讓雙向隊(duì)列繼承了棧和隊(duì)列的接口，這樣就可以把雙向隊(duì)列當(dāng)做棧和隊(duì)列使用啦。

?具體的，SliceList是基于Slice實(shí)現(xiàn)的雙向隊(duì)列，LinkedList是一個(gè)基于鏈表實(shí)現(xiàn)的雙向隊(duì)列，繼承關(guān)系如下圖所示。

繼承關(guān)系圖.png

2、SliceList簡(jiǎn)析

type SliceList struct {
   data []int
}

?切片是 Go 中的一種基本的數(shù)據(jù)結(jié)構(gòu)，使用這種結(jié)構(gòu)可以用來管理數(shù)據(jù)集合。切片常見的操作有 append、copy。與此同時(shí)，切片還具有可索引，可迭代的優(yōu)秀特性。

?切片的結(jié)構(gòu)體由3部分構(gòu)成，array 是指向一個(gè)數(shù)組的指針，len 代表當(dāng)前切片的長(zhǎng)度，cap 是當(dāng)前切片的容量。cap 總是大于等于 len 的。

?切片在append的時(shí)候，達(dá)到了切片的容量，會(huì)產(chǎn)生擴(kuò)容，擴(kuò)容的詳細(xì)解析見參考1、2。簡(jiǎn)單描述的話，也就是切片的容量小于 1024 個(gè)元素，擴(kuò)容為原來的2倍；容量大于等于1024，每次增加原來的0.25倍。擴(kuò)容會(huì)首先開辟一片內(nèi)存區(qū)域，然后把舊的數(shù)據(jù)拷貝過來，array指針指向新的內(nèi)存區(qū)域。

?所以在用切片來實(shí)現(xiàn)SliceList時(shí)，在初始化SliceList的時(shí)候，可以預(yù)先指定SliceList切片數(shù)據(jù)的容量，那么之后插入數(shù)據(jù)就可以避免切片擴(kuò)容而造成了額外的時(shí)間和空間的消耗。

slice.jpg

3、LinkedList簡(jiǎn)析

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

?本文的LinkedList的實(shí)現(xiàn)參考了Java中LinkedList的實(shí)現(xiàn)。

?基于鏈表實(shí)現(xiàn)的雙向隊(duì)列，每一個(gè)節(jié)點(diǎn)不僅需要保留數(shù)據(jù)，還需要保留前驅(qū)和后繼節(jié)點(diǎn)的指針，所以在空間上會(huì)比基于切片的實(shí)現(xiàn)消耗更多，另外在插入新的數(shù)據(jù)的時(shí)候，需要新建Node節(jié)點(diǎn)，對(duì)比于切片直接在地址上賦值，時(shí)間上也會(huì)有更多的消耗。

img

4、性能測(cè)試

?本文是基于Go testing包進(jìn)行測(cè)試的，具體的測(cè)試方法教程見參考3、4、5。

?為了更細(xì)致的對(duì)比LinkedList和SliceList的性能，本文進(jìn)行了兩方面的測(cè)試。一個(gè)是順序測(cè)試，也就是先Push一定數(shù)量的數(shù)據(jù)，然后再Peek、Pop直到棧為空；另一個(gè)是隨機(jī)測(cè)試，也就是Push、Peek、Pop是隨機(jī)執(zhí)行的，當(dāng)然棧為空的時(shí)候Peek、Pop是會(huì)返回error的，這里僅測(cè)試性能，就不做處理了。

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

//順序測(cè)試：Push、Peek、Pop依次執(zhí)行
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()
      }
   }
}

//隨機(jī)測(cè)試：Push、Peek、Pop隨機(jī)執(zhí)行
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()
      }
   }
}

?如圖所示，是測(cè)試結(jié)果的截圖，本文關(guān)注了第三列 ns/op，第四列 B/op。