陣列、切片(以及字串): append內建函式的運作機制

類別: IT

介紹

陣列是程式語言中最常用到的功能之一. 陣列看起來是比較簡單,但在一個語言要實現一個陣列的時候,有些問題必須要解決,如::

  • 固定大小或可變大小?
  • 是型別的一部分?
  • 多為陣列的模型?
  • 空陣列的意義?

這些問題的解決影響著陣列僅是語言的一個功能還是其設計的核心部分.

在早期的Go語言發展中,在設計陣列前大約用了1年的時間來決定這些問題. 關鍵的一步就是引入片, 可以在一個固定大小的陣列上有一個靈活可擴充套件的資料結構. 是該型別的大小的一部分,新的Go程式設計師通常對片的工作原理十分困惑。也許其他程式語言對他們思想影響太深.

在這篇中將理清這些混亂. 我們將通過構建塊來解釋附加內建函式是如何工作的,以及為什麼它的工作原理是這樣的。

陣列

陣列是 Go語言的一個重要模組, 就像基礎模組一樣他們往往隱藏在一些可見元件中. 在我們轉到更有趣,功能更強大更突出的片之前,我們必須先簡單說一說這些元件。

陣列不知經常出現在  Go語言程式中,因為陣列的是他型別的一部分大小,這限制了陣列的功能.

宣告

var buffer [256]byte

宣告瞭256個位元組的變數緩衝區。這個型別的緩衝區包含它的大小,[256]位元組。用512位元組陣列是不同的型別[512]位元組。

與陣列有關的資料僅僅是一個陣列的元素。如下所示,類似陣列緩衝池在記憶體中的樣子,

buffer: byte byte byte ... 256 times ... byte byte byte
也就是說這個變數擁有256個位元組的資料,再不擁有其他任何東西了。我們可以使用熟悉的索引語法buffer[0],buffer[1]等等,直到buffer[255]來訪問其中的元素。(索引的範圍從0到255,包含有256個元素。)試圖對超過這個範圍的buffer索引獲取值將會引起程式崩潰。

有一個名字為len的內建函式,它返回的是陣列或者片段中元素的數目,還可以是幾個其他資料型別的元素的個數。對陣列來說,len返回的是什麼很明確。在我們所舉的例子裡,len(buffer)返回的是固定值256。

陣列有自己的用途-比如陣列是表示轉換矩陣的好方法-不過,Go語言中最常用的目的是替分片佔據儲存。

分片:分片頭

分片這種動作應用在哪兒呢?一個人只有準確地理解了分片是什麼和分片能做什麼的情況下才能很好的使用分片。
分片是一種資料結構,它描述的是與分片變數本身相隔離的,儲存在陣列裡的連續部分。分片不是陣列,分片描述的是一段陣列。
前一節裡我們給出了陣列變數buffer,我們建立一個分片,它通過對buffer陣列分片指定了元素100到元素150的分片(準確地說,是 100-149,包含兩端)
var slice []byte = buffer[100:150]

在這個程式碼片段中,我們使用了完整的變數宣告。變數slice是被宣告為byte[]型別,它被初始化為一個buffer陣列型別,包括100到150個slice元素。更通用的語法是丟掉型別,它通過初始化表示式進行設定。

var slice = buffer[100:150]

在一個函式我們可以使用簡短的宣告形式,

slice := buffer[100:150]

到底slice變數是什麼呢?它雖然不是非常的完整,但是我們現在覺得slice作為一個小的資料結構擁有2個元素:一個長度和一個指標陣列。你可以把它想象成是下面的樣子:

type sliceHeader struct {    Length        int    ZerothElement *byte}slice := sliceHeader{    Length:        50,    ZerothElement: &buffer[100],}

當然,上面的只是一個說明。不管怎樣這片程式碼結構對程式設計者是不可見的,元素指標的型別取決於元素的型別,但是給出了技術性的一個一般思想。

到目前為止,我們在陣列上對slice進行操作,但是我們也可以切片一個slice:

slice2 := slice[5:10]

正如前面的一樣,這種操作建立了一個新的slice,在這種情況下,原始slice擁有5到9(包括9)個元素,這就意味著原始陣列有105到109個元素。slice2變數的形式和下面的sliceHeader結構體一樣:

slice2 := sliceHeader{    Length:        5,    ZerothElement: &buffer[105],}

注意,這個頭仍然指向底層相同的陣列,儲存buffer陣列變數。

我們也重新切片,意思就是說我們擷取一個slice,然後把擷取後的結果返回到最初的結構中。

slice = slice[5:10]

slice變數的Headerstructure結構體看起來和slice2的一樣。你將會看到會經常重複使用它們,例如擷取一個slice。下面的擷取是去掉了第一個和最後一個元素:

slice = slice[1:len(slice)-1]

[練習,寫出上面這種形式的結構體,作為之後的作業]

你會經常聽到Go語言的程式設計師講  "slice header"因為他確實是儲存在切片變數裡. 例如, 當你呼叫一個函式,它接受一個切片作為引數,如 bytes.IndexRune,在呼叫的時候,header是傳遞給行數的,

slashPos := bytes.IndexRune(slice, '/')

切片引數被傳遞到IndexRune這個函式 , 實際上傳遞的是 "slice header".

在切片頭有更多資料,下面將會談到, 但先讓我們看看當你的程式用到了切片,切片頭有什麼意義.

給函式傳遞分片

理解這一點是很重要的:雖然片段包含指標,但是它本身卻是隻是一個值。解開這個祕密:它是一個含有指標和長度的結構的值。它不是一個指向結構的指標。

這一點非常重要。

當我們在前面的例子裡呼叫IndexRune的時候,傳遞給它的是分片頭的一個拷貝。這種行為可以得到重要的結果。

看看下面這個簡單的函式:

func AddOneToEachElement(slice []byte) {    for i := range slice {        slice[i]++    }}
它做得僅僅是函式名字所敘述那樣,(使用for range 迴圈)對一個片段的索引迭代,增大每個元素。

試試這個例子:

func main() {    slice := buffer[10:20]    for i := 0; i < len(slice); i++ {        slice[i] = byte(i)    }    fmt.Println("before", slice)    AddOneToEachElement(slice)    fmt.Println("after", slice)}
(如果你想探個究竟,那麼你可以編輯,然後重新執行這個可以執行的程式片段。)
雖然分片頭是值傳遞的,但是這個頭包含指向陣列元素的指標,因此原來的分片頭和傳遞給函式的這個頭的拷貝都指向同一個陣列。 因此,當這個函式返回的時候,已經修改的元素可以通過原來的分片變數看到修改過的元素值。

函式的引數實際上是一個拷貝,如下面的例子所示:

func SubtractOneFromLength(slice []byte) []byte {    slice = slice[0 : len(slice)-1]    return slice}func main() {    fmt.Println("Before: len(slice) =", len(slice))    newSlice := SubtractOneFromLength(slice)    fmt.Println("After:  len(slice) =", len(slice))    fmt.Println("After:  len(newSlice) =", len(newSlice))}

這時我們可以看到由函式修改的分片引數的內容,不過分片頭沒有更改。儲存在分片變數裡的長度也不能通過呼叫函式而修改,這是因為傳遞給函式的是分片頭的一個拷貝,不是原來的分片頭。因此,如果我們想編寫一個修改分片頭的函式,那麼我們必須把它當作結果引數返回,這兒我們就是這樣做的。分片變數是無法做更改的,不過返回值具有新的長度,然後把這個返回值儲存在新的分片中。

分片指標:方法中的接收者

讓函式修改分片頭的另一個方法是給這個函式傳送指標。下面是前面例子的一次修改,實現了給函式傳遞指標:

func PtrSubtractOneFromLength(slicePtr *[]byte) {    slice := *slicePtr    *slicePtr = slice[0 : len(slice)-1]}func main() {    fmt.Println("Before: len(slice) =", len(slice))    PtrSubtractOneFromLength(&slice)    fmt.Println("After:  len(slice) =", len(slice))}

在這個例子裡,這麼做似乎很笨拙,尤其是在對額外增加的中間層的處理上(臨時變數實現),不過,在這兒,你可以看到指向分片的指標卻是很常見的。對要修改分片的函式來說,使用指標實現引數接收是常見的做法。

讓我們說說我們需要一個在最後一個斜槓處截短分片的方法。我們如下編寫:

type path []bytefunc (p *path) TruncateAtFinalSlash() {    i := bytes.LastIndex(*p, []byte("/"))    if i >= 0 {        *p = (*p)[0:i]    }}func main() {    pathName := path("/usr/bin/tso") // Conversion from string to path.    pathName.TruncateAtFinalSlash()    fmt.Printf("%s\n", pathName)}
如果你執行這個例子,你會看到程式得到正確的執行,對呼叫者的分片完成了更改。

[練習:改變接收者的型別為一個數值而不是一個指標,然後繼續執行。解釋一下發生了什麼]

另一方面,如果我們想要寫一個方法來處理路徑並把ASCII字母變為大寫(忽視非英文名稱),這個方法可能是一個數值,因為數值接收者將仍然指向同一個陣列。

type path []bytefunc (p path) ToUpper() {    for i, b := range p {        if 'a' <= b && b <= 'z' {            p[i] = b + 'A' - 'a'        }    }}func main() {    pathName := path("/usr/bin/tso")    pathName.ToUpper()    fmt.Printf("%s\n", pathName)}

ToUpper方法在for迴圈構造器中用了兩個變數來獲得索引和切片元素。迴圈的形式防止在函式體中給p[i]中多次寫值。

[練習:將ToUpper方法改變為用指標接收值,看看結果是否變化了]

[高階練習:口說夢話ToUpper方法改變為處理Unicode字元,而不只是ASCII]

容量

下面的函式通過傳入一個元素擴充套件它的slice引數:

func Extend(slice []int, element int) []int {    n := len(slice)    slice = slice[0 : n+1]    slice[n] = element    return slice}

(為什麼它需要返回一個已經修改過的slice呢?)現在執行它:

func main() {    var iBuffer [10]int    slice := iBuffer[0:0]    for i := 0; i < 20; i++ {        slice = Extend(slice, i)        fmt.Println(slice)    }}

檢視slice的值是怎麼變化的。

是時候談論切片頭的第三個元件了:它的容量。除了陣列指標和長度,切片頭還儲存它的容量:

type sliceHeader struct {    Length        int    Capacity      int    ZerothElement *byte}
Capacity欄位記錄陣列實際使用了多少的空間。這是Length能達到的最大值。試著增加slice的長度並超過它的容量,慢慢超過陣列長度的限制,將會觸發可怕的後果。

在我們的例子中slice是通過下面的方式建立的:

slice := iBuffer[0:0]

它的頭部像下面的樣子:

slice := sliceHeader{    Length:        0,    Capacity:      10,    ZerothElement: &iBuffer[0],}

Capacity欄位和底層陣列的長度減去slice的第一個元素的陣列索引值是相等的(0在這種情況下存在)。如果你想探究一個slice的容量,使用cap函式:

if cap(slice) == len(slice) {    fmt.Println("slice is full!")}

Make方法

如果我們想增大分片,卻超出分片本身的容量,怎麼辦呢?你不能這麼做。根據分片的定義,容量限制了分片的增長。不過,你可以通過新建立一個陣列,把分片資料拷貝到陣列,然後修改分片使其指向新的陣列而得到相同的結果。

讓我們開始建立陣列 。我們可以使用內建函式new來建立一個更大一點的陣列,然後對所得的陣列進行分片。不過實現這個更簡單的方法是使用內建的make函式替代new函式。這個函式建立了一個新陣列,然後建立了一個指向陣列的分片頭,所有這些一次完成。make函式使用了三個引數:分片型別,分片初始長度和make建立的用來儲存分片資料的陣列的長度,即分片容量。下面的呼叫建立了一個長度為10,且多餘5個空間(10-15)的分片,執行它,你就會看到結果:

slice := make([]int, 10, 15)fmt.Printf("len: %d, cap: %d\n", len(slice), cap(slice))
下面的程式片段對int分片的容量實現了倍增,而其長度卻保持不變:
slice := make([]int, 10, 15)fmt.Printf("len: %d, cap: %d\n", len(slice), cap(slice))newSlice := make([]int, len(slice), 2*cap(slice))for i := range slice {newSlice[i] = slice[i]}slice = newSlicefmt.Printf("len: %d, cap: %d\n", len(slice), cap(slice))

執行這段程式碼後,slice在需要重新分配之前擁有更多的增長空間。

當建立slices的時候,slice的長度和它的容量是相同的。通用情況下在make內建一個陣列。引數的長度預設就是它的容量,所有你可以把它們設定為相同的值。

gophers := make([]Gopher, 10)
gophers sclice的長度和容量都同時被設定為了10。

複製

當我們把上一節中的slice的容量擴大兩倍的時候,我們寫了一個迴圈把以前的資料複製到新的slice中。Go有一個內建的copy函式,使這個實現更加簡單。它的引數有2個sclice,它把右邊引數的資料複製到左邊引數中來。下面是使用copy函式寫的一個例子:

newSlice := make([]int, len(slice), 2*cap(slice))copy(newSlice, slice)

copy函式很好用。它只複製它能夠複製的,請注意兩個引數的長度。換句話說,它複製的元素數量是兩個slice中長度最小的那個。這可以節省一點效率。另外,copy函式會返回一個整數值,代表複製元素的數量。儘管它並不值得時時去檢測。

在源分片和目的分片出現交叉時,copy函式仍然可以進行正確地拷貝,這意味著可以用copy函式實現耽擱分片中元素的移動。下面展示瞭如何使用copy函式向分片中間插入一個值。
// Insert向分片的指定位置插入值,// 位置必須在有效範圍內.// 分片必須有空間增加新元素.func Insert(slice []int, index, value int) []int {    // 給分片增加一個元素的空間.    slice = slice[0 : len(slice)+1]    //使用copy函式移動分片的前面部分,開啟一個缺口.    copy(slice[index+1:], slice[index:])    // 儲存新值.    slice[index] = value    // 返回結果    return slice}

上面的函式中有兩點要注意。第一點當然是這個函式必須返回已經更新的分片,因為分片的長度已經更改。第二點是這個函式使用了很方便的簡寫。表示式

slice[i:]
準確地講等同於:
slice[i:len(slice)]
另外,儘管我們仍然沒有使用過這個小技巧,不過我們仍然可以保持分片表示式的第一個元素為空;這個元素的預設值為零。因此表示式:
slice[:]

就意味著整個分片,這在對整個陣列進行分片時很有用。這個表示式是說明“指向整個陣列元素的分片”:

array[:]
的最簡寫方式。

現在,所有的問題已經說明白了,讓我們執行一下Insert函式。


slice := make([]int, 10, 20) //注意:容量要大於長度,這樣才有空間增加新元素.for i := range slice {slice[i] = i}fmt.Println(slice)slice = Insert(slice, 5, 99)fmt.Println(slice)

Append:一個例子

在前面幾節中,我們通過一個元素,寫了一個擴充套件函式來擴充套件slice。儘管它有點問題,因為如果slice的容量太小的時候,這個函式就會崩潰。(我們內建的例子也有這個問題)。現在我們有方法來修復它,讓我們為整數slices寫一個健壯的實現。

func Extend(slice []int, element int) []int {    n := len(slice)    if n == cap(slice) {        // Slice is full; must grow.        // We double its size and add 1, so if the size is zero we still grow.        newSlice := make([]int, len(slice), 2*len(slice)+1)        copy(newSlice, slice)        slice = newSlice    }    slice = slice[0 : n+1]    slice[n] = element    return slice}

這種情況下,返回slice特別的重要,因為當重新分配結果slice的時候,描述了一個完全不同的陣列。下面的一小片程式碼展示在slice填滿的時候發生了什麼。

slice := make([]int, 0, 5)for i := 0; i < 10; i++ {	slice = Extend(slice, i)	fmt.Printf("len=%d cap=%d slice=%v\n", len(slice), cap(slice), slice)	fmt.Println("address of 0th element:", &slice[0])}

要注意到當初始化一個大小為5的一個陣列時空間已經重新分配了。當新的陣列被分配後,其容量和首元素地址都會改變。

在健壯的Extend函式的指導下我們可以寫出一個更好的可以讓我們按照多元素的方式擴充套件切片。為了能實現這個目標,我們用Go的特性將函式引數列表轉換為一個切片。這就是我們運用了Go函式多變的技巧。

讓我呼叫Append函式吧。在第一個版本中,我們可以只重複呼叫Extend來清除variadic函式機制。Append的簽名方式如下:

func Append(slice []int, items ...int) []int

有人說Append有一個引數,而一個切片擁有0個或者更多的整形引數。那些引數是一個整形切片並實現了Append所關注的,如下面的形式:

// 給切片追加元素// 第一個版本:迴圈呼叫Extendfunc Append(slice []int, items ...int) []int {    for _, item := range items {        slice = Extend(slice, item)    }    return slice}

注意在引數列表元素中迴圈迭代的範圍,它是隱式[]int型別。也要注意用了一個空白的標識_拋棄迴圈的索引,這個例子中我們不需要這個標識。

試試下面這段程式碼:
slice := []int{0, 1, 2, 3, 4}fmt.Println(slice)slice = Append(slice, 5, 6, 7, 8)fmt.Println(slice)
在這個例子裡出現了另一個技術:通過複合文字常量初始化分片,複合文字常量是由分片型別,緊跟著包括在大括號內的 分片各項的值組成:

由於下面的原因,其中的Append函式也讓我們很感興趣。我們不僅僅可以用它來新增分片中的元素,而且還可以通過在呼叫處使用...符號給分片“激增”引數方法給分片增加第二個分片:

slice1 := []int{0, 1, 2, 3, 4}slice2 := []int{55, 66, 77}fmt.Println(slice1)slice1 = Append(slice1, slice2...) //“...”很重要!fmt.Println(slice1)

當然,我們還可以讓Append更高效,在函式內部進行擴充套件,對其一次性分配足夠的空間:

// Append給分片增加元素.// 高效版本.func Append(slice []int, elements ...int) []int {    n := len(slice)    total := len(slice) + len(elements)    if total > cap(slice) {        //重新分配空間,擴充套件為新給定大小的1.5倍,這樣我們讓然可以再對它進行擴充套件.        newSize := total*3/2 + 1        newSlice := make([]int, total, newSize)        copy(newSlice, slice)        slice = newSlice    }    slice = slice[:total]    copy(slice[n:], elements)    return slice}
注意:這兒我們呼叫了copy兩次,第一次是把分片資料拷貝到新分配的記憶體,然後再拷貝要繼續新增的各項到前面資料的後邊。

試試下面這段程式碼;它的執行結果與前面提到的那段程式碼相同:

slice1 := []int{0, 1, 2, 3, 4}slice2 := []int{55, 66, 77}fmt.Println(slice1)slice1 = Append(slice1, slice2...) // "..."很重要!fmt.Println(slice1)

Append:內建函式

至此,我們已經明白設計append內建函式的動機。這個內建函式所要做的確實如上面的Append例子那樣,而且同樣高效,不過它可對任何分片型別操作。

Go語言的一個弱點是任何泛型別的操作只有在執行時才能確定。終有一天這會得到更改,不過,迄今為止 ,為了更容易地對分片進行操作,Go語言必須給出內建的泛型append函式。它就像我們上面的int型分片那樣執行,不過它針對的是任何分片型別。

記住:由於在呼叫append的時候總是更改了分片的頭,因此你必須在呼叫之後儲存返回的分片。事實上,如果沒有儲存返回結果的話,編譯器是不會讓你呼叫append的。

下面的幾段混合有print語句。試試這幾段程式碼,編輯,然後看看執行結果:

// 建立兩個最初的分片.slice := []int{1, 2, 3}slice2 := []int{55, 66, 77}fmt.Println("Start slice: ", slice)fmt.Println("Start slice2:", slice2)// 給一個分片新增元素.slice = append(slice, 4)fmt.Println("Add one item:", slice)// 繼續新增另一個分片.slice = append(slice, slice2...)fmt.Println("Add one slice:", slice)// 拷貝(int型)分片.slice3 := append([]int(nil), slice...)fmt.Println("Copy a slice:", slice3)// 把分片拷貝到自己的尾部.fmt.Println("Before append to self:", slice)slice = append(slice, slice...)fmt.Println("After append to self:", slice)
花點時間考慮上面這幾段程式碼中的最後一段細節是值得的,這樣就能夠理解如何設計分片才可能使簡單的呼叫得到正確的結果。

在由社團構建的"分片使用技巧“維客頁面裡, 還有許多append、copy和其他使用分片方法的例子。

Nil

另外,發現這樣一個知識點:我們要明白nil分片是如何表示的。很自然,它的分片頭為零:

sliceHeader{    Length:        0,    Capacity:      0,    ZerothElement: nil,}
或者僅如下面表示:
sliceHeader{}
關鍵的地方是元素指標也指向了nil。由
array[0:0]
建立的分片具有零長度(也許還具有零容量),不過它的指標指的不是nil,因此它不是nil分片。

應當很清晰了,空分片可以增大(假設它又非零的容量),而nil分片沒有存放元素值得陣列,而且從不會為了存放元素而增長。

也就是說,nil分片功能上等同於零長度的分片,不同的是它不指向任何東西。它具有零長度,但可以給其分配空間,新增元素。就像上面例子裡那樣,你可以看看通過給nil分片新增而實現分片拷貝的那一段。

字串

現在我們在介紹分片的這段中插入一段對Go語言字串的簡短介紹。

字串實際上很簡單:它只是Go語言在句法上有一點額外支援的只讀的位元組分片。

由於字串是隻讀的,因此它沒有容量(你就不能對它進行擴充套件),然而,在大多數情況下,你只要把它當作只讀的位元組片段看待。

對初學者來說,我們可以通過索引來訪問某一個位元組:

slash := "/usr/ken"[0] //生成位元組值為'/'.
我們也可以對字串分片,用來獲取子字串:
usr := "/usr/ken"[0:4] //生成字串"/usr"
現在,當我們對字串分片的時候,其背後是如何執行的應該是很明瞭的。

我們還可以多通常的位元組分片進行操作,可以使用簡單的轉換由位元組分片建立字串:

str := string(slice)
而且還可以進行相反方向的轉換:
slice := []byte(usr)
我們還可以看到隱藏在字串下面的陣列;除了使用字串訪問陣列內容外,沒有其他辦法可以訪問了。這就意味著當我們做 上面的任何一種轉換的時候,這個陣列一定得到了拷貝。很顯然,Go非常關心這一點,因此,你不需要做任何事情。執行上面 兩種轉換的任一一種都會修改位元組分片底層的陣列,這不會影響到對應的字串。

切片的一個重要結果就和給字串設計了求子字串函式一樣的效果。所有要做的只是建立一個含有2個詞的字串頭。應為字串是隻讀的,原始字串和經過切片處理的字串可以共同安全的分享同一個陣列。

經驗之談:最先實現的是字串的分配,但是當給語言新增切片時,它提供了一種有效處理字串的模式。從一些基準測試中可以看出它的速度是很快的。

關於字串還有很多,當然,這些只能放到另一篇文章裡講了。

結論

瞭解切片是如何工作的, 有助於瞭解他們是怎麼實現的. 有一點資料結構,切片頭,是與切片關聯的專案,在開頭也說了陣列的獨立分配.當我們傳遞切片值, 切片頭會被複制一份,但它指向的陣列是共享的.

一旦你明白它們是如何工作的,切片會非常簡單易用, 但是功能強大,尤其是對於需要複製和附加的內建函式

更多閱讀

有很多在網上找到關於Go語言分片的文章,正如前面提到的 "Slice Tricks" 有很多例子.關於 Go Slices的部落格描述了記憶體佈局圖清晰的細節. Russ Cox's Go 數結構 文章包括討論分片以及一些其他的Go語言的的內部資料結構。.

還有更多的資料,但是最好的學習方式是使用它。

作者 Rob Pike

陣列、切片(以及字串): append內建函式的運作機制原文請看這裡