[Go] Slice 長さと容量って何？

## はじめに
　こちらは、[RetailAI Adventurers Advent Calendar 2023](https://qiita.com/advent-calendar/2023/rai-adventurers)の15日目の記事です。
 
https://qiita.com/advent-calendar/2023/rai-adventurers
 
　昨日は[tanabe_shogo](https://qiita.com/tanabe_shogo)さんの『[GCPでDuet AI使ってみた](https://qiita.com/tanabe_shogo/items/243729c1657f0db67385)』でした。

　この記事では、Goでよく使われる[Slice](https://go.dev/tour/moretypes/7)の仕組みについてご紹介しようと思います。ここで書く内容は、『[100 Go Mistakes and How to Avoid Them](https://www.manning.com/books/100-go-mistakes-and-how-to-avoid-them)』の『**#20: Not understanding slice length and capacity**』の章を読んで個人的に噛み砕いたものになります。

 https://www.manning.com/books/100-go-mistakes-and-how-to-avoid-them
 
 　筆者の裏の意図としては、Sliceに関する本書での内容を復習して自分なりの理解をアウトプットするためのものです。そのため、自分の理解が足りない点などありましてもどうかご容赦ください。できたらコメント等で教えていただけると大変有り難いです :bow: 
  
 　（本書の日本語の翻訳書『[Go言語 100Tips - ありがちなミスを把握し、実装を最適化する](https://book.impress.co.jp/books/1122101133)』も今年出版されています！著者さんには他のGoの翻訳書でも大変お世話になっております。ここでお礼を:bow:)
  

## Sliceとは？
　Sliceとは、複数の要素を持つことができるデータ構造ですが、長さが固定された[Array](https://go.dev/tour/moretypes/6)とは異なり、長さを動的に変更できます。
　しかしながら、Sliceに格納するデータは、実際には裏のArray（backing array: 基底配列）に格納されており、Slice自体が持っているデータは以下の3つです。

1. backing arrayへのポインタ
2. 長さ(length)：そのSliceが（プログラマーに対して明示的に）含んでいる要素の数
3. 容量(capacity)：そのSliceを裏で支えるbacking arrayの要素の数


　以下は、簡単なコードとイメージ図をもとに、さらに詳細へと進めていきます。

## 初期化
以下のコードは、長さは3、容量は6のSliceを初期化します。
```go
// sample 1
s := make([]int, 3, 6)
```
図にすると以下のような感じです。
長さで指定した要素には宣言した型(type)の[ゼロ値(zero value)](https://go.dev/tour/basics/12)で初期化されます。ここでは`int`型なので、`0`が入ります。
```text
sample 1のイメージ図
slice (s)
+-----+-----+-----+
| ptr | len | cap |
+-----+-----+-----+
|  *  |  3  |  6  |
+-----+-----+-----+
   |
   |   backing array
   |   +-----+-----+-----+-----+-----+-----+
    -> |  0  |  0  |  0  |     |     |     |
       +-----+-----+-----+-----+-----+-----+
```

## 要素への代入
以下のように、要素に値を代入して上書くことができます。
```go
// sample 2
s[1] = 1
```
```text
sample 2のイメージ図
slice (s)
+-----+-----+-----+
| ptr | len | cap |
+-----+-----+-----+
|  *  |  3  |  6  |
+-----+-----+-----+
   |
   |   backing array
   |   +-----+-----+-----+-----+-----+-----+
    -> |  0  |  1  |  0  |     |     |     |
       +-----+-----+-----+-----+-----+-----+
```
一方で、容量は6ですが、長さは3で初期化されているため、
長さの範囲外の要素へアクセスして代入しようとすると、以下のようにpanicが発生します。
```go
s[3] = 0
```
```text
panic: runtime error: index out of range [3] with length 3
```
では、せっかくメモリ（容量）は6まで確保されているのに、どうやったら使えるのでしょうか？
その方法の一つが、組み込み関数の[appned](https://go.dev/tour/moretypes/15)です。
## appendによる追加
以下のように、`append`によって要素を追加することができます。
```go
// sample 3
s = append(s, 2)
```
```text
sample 3のイメージ図
slice (s)
+-----+-----+-----+
| ptr | len | cap |
+-----+-----+-----+
|  *  |  3  |  6  |
+-----+-----+-----+
   |
   |   backing array
   |   +-----+-----+-----+-----+-----+-----+
    -> |  0  |  1  |  0  |  2  |     |     |
       +-----+-----+-----+-----+-----+-----+
```

## appendによる追加; 容量を超える場合
さらに、容量である`6`を超える数の要素を追加します。
```go
// sample 4
s = append(s, 3, 4, 5)
```
すると、内部的に、Goは、2倍の容量である`12`を確保した別のarrayを生成し、そこに元のarrayから値をすべてコピーし、新しいarrayを参照するポインタに変更し、最後に新しい要素の値`5`を代入します。
```text
sample 4のイメージ図
slice (s)
+-----+-----+-----+
| ptr | len | cap |
+-----+-----+-----+
|  *  |  3  |  12 |
+-----+-----+-----+
   |
   |   original array
   |   +-----+-----+-----+-----+-----+-----+
   |   |  0  |  1  |  0  |  2  |  3  |  4  |
   |   +-----+-----+-----+-----+-----+-----+
   |                     |
 switch                 copy
   |                     |
   |                     V
   |   new backing array                   | 2x added ->
   |   +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
    - >|  0  |  1  |  0  |  2  |  3  |  4  |  5  |     |     |     |     |     |
       +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
```
もう参照されなくなった元のarrayは、ヒープ(heap)上に割り当てられている場合、ガーベージコレクション(GC)により最終的に開放されます。

このように、実は、Goでは自動的に、Sliceの要素数が`1024`になるまで、容量が`2倍`ずつ増え、それ以降は`25%`ずつ増えていきます。
（要素数が`1024`以降は`25%`ずつ増加という記述は、翻訳書や[go projectのcommit](https://github.com/golang/go/commit/2dda92ff6f9f07eeb110ecbf0fc2d7a0ddd27f9d)から見つけました:eyes:）

つまり、この処理は、容量が確保されていない限り、appendが呼ばれる度に行われてしまいます。
そのため、予めsliceに格納するデータの最大数が分かっている場合は、以下のように、容量を指定してsliceを初期化することが推奨されています。
```go
s := make([]int, 0, 7)
```
（本書では、『**#21: Inefficient slice initialization**』の中で、詳しく説明されています）

## Slice化(slicing)
 slicingとは、あるslice（またはarray）の要素を部分的に操作する方法です。
 以下のように、1つ目のインデックスの要素は含まれ、2つ目のインデックスの要素は含まれない部分集合的なsliceを作ることができます。
```go
// sample 5
s1 := make([]int, 3, 6)
s2 := s1[1:3]
```
slicingした`s2`の長さは指定した範囲に含まれる要素の数=`2`になりますが、容量は`5`となります。
つまり、あくまで同じbacking arrayを参照していることが分かります。
```text
sample 5のイメージ図
slice (s1)               slice (s2)
+-----+-----+-----+      +-----+-----+-----+
| ptr | len | cap |      | ptr | len | cap |
+-----+-----+-----+      +-----+-----+-----+
|  *  |  3  |  6  |      |  *  |  2  |  5  |
+-----+-----+-----+      +-----+-----+-----+
   |                        |
   |                        |
   +------+     +-----------+
          |     |
          V     V
       +-----+-----+-----+-----+-----+-----+
       |  0  |  0  |  0  |     |     |     |
       +-----+-----+-----+-----+-----+-----+
       backing array
```
そのため、`s1`と`s2`でインデックスは異なりますが、両方のSliceに含まれている要素の値を変更すると、どちらも変更されているのが分かります。
```go
// sample 6
s1[1] = 100
fmt.Printf("s1: %v\n", s1)
fmt.Printf("s2: %v\n", s2)
```
```text
s1: [0 100 0]
s2: [100 0]    # s2[0]の値も変更されている
```
```text
sample 6のイメージ図
slice (s1)               slice (s2)
+-----+-----+-----+      +-----+-----+-----+
| ptr | len | cap |      | ptr | len | cap |
+-----+-----+-----+      +-----+-----+-----+
|  *  |  3  |  6  |      |  *  |  2  |  5  |
+-----+-----+-----+      +-----+-----+-----+
   |                        |
   +------+     +-----------+
          |     |
          V     V
       +-----+-----+-----+-----+-----+-----+
       |  0  | 100 |  0  |     |     |     |
       +-----+-----+-----+-----+-----+-----+
       ^  backing array  ^ 
       |                 |      
       +--s1 & s2 lens --+ 
```

ここで、`s2`に新しい要素`2`を追加します。
```go
// sample 7
s2 = append(s2, 2)
fmt.Printf("s1: %v, len: %d, cap: %d\n", s1, len(s1), cap(s1))
fmt.Printf("s2: %v, len: %d, cap: %d\n", s2, len(s2), cap(s2))
```
`s1`の長さは`3`のままであるため、`s1`はbacking arrayの1番目から3番目までしか参照しません。
そのため、今回backing arrayの4番目に追加された`2`は出力されません。
```text
s1: [0 100 0], len: 3, cap: 6 # s1への追加の影響は無い
s2: [100 0 2], len: 3, cap: 5
```
```text
sample 7のイメージ図
slice (s1)               slice (s2)
+-----+-----+-----+      +-----+-----+-----+
| ptr | len | cap |      | ptr | len | cap |
+-----+-----+-----+      +-----+-----+-----+
|  *  |  3  |  6  |      |  *  |  3  |  5  |
+-----+-----+-----+      +-----+-----+-----+
   |                        |
   +------+     +-----------+
          |     |
          V     V
       +-----+-----+-----+-----+-----+-----+
       |  0  | 100 |  0  |  2  |     |     |
       +-----+-----+-----+-----+-----+-----+
       ^     ^           ^     ^
       |     |           |     |
       +-----|--s1's len-+     |
             |                 |
             +--------s2's len-+
```

さらに、`s2`に対してbacking arrayの容量(`5`)を超えるまで要素を追加します。
```go
// sample 8
s2 = append(s2, 3)
s2 = append(s2, 4)
s2 = append(s2, 5)
```
すると、前回と同様で、容量が2倍の新しいarrayを生成し、それに対して今までの値をコピーし、ポインタを切り替え、最後の新しい要素を追加します。
```text
s1: [0 100 0], len: 3, cap: 6
s2: [100 0 2 3 4 5], len: 6, cap: 10
```
```text
sample 8のイメージ図
slice (s1)
+-----+-----+-----+
| ptr | len | cap |
+-----+-----+-----+
|  *  |  3  |  6  |
+-----+-----+-----+
   |
   +------+
          |
          V　 original backing array for s1
       +-----+-----+-----+-----+-----+-----+
       |  0  | 100 |  0  |  2  |  3  |  4  |
       +-----+-----+-----+-----+-----+-----+
       ^                 ^                 |
       |                 |           +-copy+
       +----s1's len-----+           |
                                     |
       new backing array for s2      V 2x added ->
       +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
       | 100 |  0  |  2  |  3  |  4  |  5  |     |     |     |     |
       +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
          ^
  swtich  |
  +-------+
  |
slice (s2)
+-----+-----+-----+
| ptr | len | cap |
+-----+-----+-----+
|  *  |  6  | 10  |
+-----+-----+-----+
```

以上、sliceの長さと容量についての説明となります。
sliceを操作する上で2つの値がどういう関係にあるのか、少しでも理解が深まりましたら幸いです。

## まとめ
　本書『[100 Go Mistakes and How to Avoid Them](https://www.manning.com/books/100-go-mistakes-and-how-to-avoid-them)』では、今回のようなslice自体の構造の説明だけではなく、それに基づいて、実装上気をつけるべきTipsについてもいくつか紹介されています。また、Slice以外にGo言語に関する様々なテーマを、100つのTipsとして網羅的に紹介しています。
 
　個人的に、Go言語の文法はさらっと学習して、プロジェクトで実際に使い始めた初中級者のGopherの方には、めちゃくちゃオススメです。自分もまだじっくり読み進めている最中で、年末までに終わらせたいです:book:

## 最後に
　ちょっと宣伝させていただくと、弊社[Retail AI](https://www.retail-ai.jp/)は、小売業向けのITソリューションを提供する会社でして、そのうちの一つが『[Skip Cart](https://www.retail-ai.jp/solution/Ssc/)』というプロダクト（兼ソリューション？）になります。

 https://www.retail-ai.jp/solution/Ssc/

 　Skip Cartのプロダクト開発のチームがありまして、バックエンドのメイン言語は`Go` (+ `Python` for 機械学習系)で、プロダクト開発のチームの大半が外国籍のメンバーなので、英語でのコミュニケーションがメインです（メンバーによってはフルリモート勤務）。

  　私も今年の2月から、Skip Cartのバックエンドの開発チームに加わって、カタコトの英語を日々改善しながら、何とか息してます。他社さんでもあんまり無い、面白い環境だとは個人的には思っています。もしご興味のある方がいらっしゃれば、気軽にご連絡ください〜 :bow:


   明日は、同じSkip Cart開発チームのフロントエンドのリーダーの[Caique Almeida(カイケ)
](https://qiita.com/caique_almeida)の記事です！お楽しみ〜 :clap:  

## 参考
- 原書『[100 Go Mistakes and How to Avoid Them](https://www.manning.com/books/100-go-mistakes-and-how-to-avoid-them)』

https://www.manning.com/books/100-go-mistakes-and-how-to-avoid-them

- 日本語翻訳書『[Go言語 100Tips ありがちなミスを把握し、実装を最適化する](https://book.impress.co.jp/books/1122101133)』

https://book.impress.co.jp/books/1122101133

- [A Tour of Go](https://go.dev/tour/list)

https://go.dev/tour/list


- [go (GitHub)](https://github.com/golang/go)

https://github.com/golang/go