この記事はGo7 Advent Calendar 2019の記事です。

Go には Java や Ruby などのモダン言語のような slice を操作する関数は用意されていません。 Go では built-in 関数のappend()やcopy() と for 構文を組み合わせることで、他の言語にあるような slice 操作を実装できます。 この記事ではそれぞれの slice 操作を図解で解説します。

元ネタは Go 公式 Wiki にあるGo SliceTricks - golang/go Wikiです。

Slice の連結

a = append(a, b...)

コピー先 a にコピー元の b の全ての要素をコピーします。 連結後の長さが cap(a) を超える場合は、新たな slice が作成されて a、bともにコピーします。

以降はappend()のコピー先には十分なcapがあるという前提で進めます。

複製

slice a から新たな slice b を複製します。 以下のいずれかの方法で複製できます。

b = make([]T, len(a))
copy(b, a)

b = append([]T(nil), a...)

コピー元 a が空か nil かを区別する場合は、以下のように書きます。 a が nil の場合はbが nil になり、aが空の場合はbが空になります。

b = append(a[:0:0], a...)

範囲の削除

a = append(a[:i], a[j:]...)

範囲を指定して削除します。 a[:i] までを切り出して、a[j:] の各要素を a[i] 以降にコピーします。

単一要素の削除

a = append(a[:i], a[i+1:]...)

a = a[:i+copy(a[i:], a[i+1:])]

a[:i] を切り出して、a[i+1:] の各要素を a[i] 以降にコピーします。

順序保証しない単一要素の削除

a[i] = a[len(a)-1]
a = a[:len(a)-1]

要素の順序が重要じゃない場合は、末尾の要素を削除対象の要素にコピーできます。 この方法は「単一要素の削除」と比較して、コピーが 1 回で済みます。

範囲の削除 (GC)

copy(a[i:], a[j:])
for k, n := len(a)-j+i, len(a); k < n; k++ {
	a[k] = nil // or the zero value of T
}
a = a[:len(a)-j+i]

要素がポインタ、またはポインタを持つ struct の場合、上記の「範囲の削除」でメモリリークが発生します。 なぜならコピー前に末尾にあった要素がポインタへの参照を持ち続け、garbage collection (GC) が働かないためです。 これを回避するために、要素のコピー後に使わなくなった要素に nil またはゼロ値で参照を消します。

単一要素の削除 (GC)

if i < len(a)-1 {
	copy(a[i:], a[i+1:])
}
a[len(a)-1] = nil // or the zero value of T
a = a[:len(a)-1]

「単一要素の削除」も同様に、使わなくなった要素を nil またはゼロ値で参照を消します。

順序保証しない単一要素の削除 (GC)

a[i] = a[len(a)-1]
a[len(a)-1] = nil
a = a[:len(a)-1]

「順序保証しない単一要素の削除」も同様に、使わなくなった要素を nil またはゼロ値で参照を消します。

途中に要素を追加

a = append(a[:i], append(make([]T, j), a[i:]...)...)

途中に要素を追加して要素を拡張します。 新たに長さ j の slice を作成し、その末尾にa[i:] を追加します。 その結果を a[i] 以降にコピーします。

末尾に要素を追加

a = append(a, make([]T, j)...)

末尾に要素を追加して要素を拡張します。 新たに長さ j の slice を作成し a の末尾に追加します。

フィルター(in place)

n := 0
for _, x := range a {
 if keep(x) {
  a[n] = x
  n++
 }
}
a = a[:n]

条件のマッチする要素のみを残します。 新たな slice を作るのではなく、マッチする要素を sliec の先頭から詰めて、最後に長さを切り詰めます。

要素の挿入

a = append(a[:i], append([]T{x}, a[i:]...)...)

途中に要素を挿入します。 要素xのみを含む長さ 1 の slice の末尾に a[i:] を連結し、それをa[i]以降にコピーします。

slice の挿入

a = append(a[:i], append(b, a[i:]...)...)

途中に slice を挿入します。 挿入する slice b の末尾に a[i:] を連結し、それを a[i] 以降にコピーします。

Push

a = append(a, x)

末尾に要素 x を追加します。

Pop

x, a = a[len(a)-1], a[:len(a)-1]

末尾の要素を取り出し、長さを 1 つ切り詰めます。

Push Front/Unshift

a = append([]T{x}, a...)

追加する要素を持つ長さ 1 の slice の末尾に a を連結したのを、新たな a とします。

Pop Front/Shift

x, a = a[0], a[1:]

先頭の要素を取り出し、a{1:] を新たな a とします。

おわりに

以上Go SliceTricks - golang/go Wikiの図解による解説でした。 Go には GC があるとはいえ、C と同じようにポインタを意識したほうが、よりよい Go のコードが記述できます。 そのとき、この slice 操作はコピーが発生するのか否かを考えられると、ハイパフォーマンスなプログラムが作れます。 解説した操作と図は、以下のサイトにチートシートとしてまとめてあります。

• Go Slice Tricks Cheat Sheet