Go 言語でスライスから要素を消すには
はじめに
Go 言語に躓く人の多くはスライスの操作に躓く事が多いと思います。モダンなプログラミング言語では、スライスから要素を消すのであれば
arr.remove(i)
の様に直感的な操作ができるはずです。しかし Go 言語の場合、スライスの伸長にて発生するメモリアロケーションを append 関数と代入を使う事で透過的に行える仕組みを採用しています。例えばスライスの伸長は
arr := []int{1, 2, 3}
arr = append(arr, 4)
この様に行います。C言語をかじった事のある方や、プログラミング言語の内部データ構造をご存じの方であれば、リストといった物が伸長の度にメモリを再確保する様な事をやっていない事はご存じだと思います。Go 言語のスライスも同様で、スライスには長さとキャパシティを持っており、キャパシティを超えない範囲で長さだけが増えていき、キャパシティを超えるとメモリが再確保されるという作りになっています。ですので、上記のコードであれば、スライス(実際は SliceHeader)が内部で持っているポインタ、長さ、キャパシティを、代入してやる事で上書きしています。
スライスから要素を消す
スライスの伸長と同様に、要素の削除もスライス自身を更新しなければなりません。Go 言語のリポジトリにある Wiki から参照すると、Go 言語でのスライスから要素を消すには2通り(厳密には3つ)の方法があります。
append を使う方法
a = append(a[:i], a[i+1:]...)
append は第一引数に与えたスライスに、第二引数以降の値を追加する関数です。削除対象までのスライスに、削除対象の次以降のスライスを追加し、結果を上書きします。
copy を使う方法
a = a[:i+copy(a[i:], a[i+1:])]
copy は2つの引数で与えられたスライスにて右項から左項へコピーする関数です。戻り値はコピーした個数です。これを利用して、スライスの削除対象を削除対象の次以降のスライスで上書きし、減った要素数でスライスを再割り当てします。これにより最後の要素が削られる事になります。
順を考えない削除(おまけ)
a[i] = a[len(a)-1]
a = a[:len(a)-1]
これは削除後のスライスの順が変わってしまってもいい場合に使える方法です。最後の要素を削除対象に上書きし、要素数を減らして再割り当てます。
ベンチマーク
ベンチマークを取ってみましょう。
package main_test
import (
"testing"
)
const N = 100000
func remove1(arr []int, i int) []int {
return append(arr[:i], arr[i+1:]...)
}
func remove2(arr []int, i int) []int {
return arr[:i+copy(arr[i:], arr[i+1:])]
}
func remove3(arr []int, i int) []int {
arr[i] = arr[len(arr)-1]
return arr[:len(arr)-1]
}
func BenchmarkRemove1(b *testing.B) {
arr := make([]int, N)
var tmp []int
b.ResetTimer()
for i := 0; i < b.N; i++ {
for j := 0; j < N; j++ {
tmp = remove1(arr, j)
//tmp = remove1(arr, 0)
if len(tmp) != N-1 {
b.Fatal("wrong result")
}
}
}
}
func BenchmarkRemove2(b *testing.B) {
arr := make([]int, N)
var tmp []int
b.ResetTimer()
for i := 0; i < b.N; i++ {
for j := 0; j < N; j++ {
tmp = remove2(arr, j)
//tmp = remove2(arr, 0)
if len(tmp) != N-1 {
b.Fatal("wrong result")
}
}
}
}
func BenchmarkRemove3(b *testing.B) {
arr := make([]int, N)
var tmp []int
b.ResetTimer()
for i := 0; i < b.N; i++ {
for j := 0; j < N; j++ {
tmp = remove3(arr, j)
//tmp = remove3(arr, 0)
if len(tmp) != N-1 {
b.Fatal("wrong result")
}
}
}
}
2重ループになっているのは、スライスのどの位置を消すかによってベンチマークの差異が起きるのであれば、その結果もベンチマークとして計測したいからです。スライスの先頭にある要素を消すと、残りのスライスを前にずらす必要があります。ですので先頭の要素を削除するのに掛かる時間は、最後の要素を削除するのに掛かる時間よりも長くなります。
削除後の順を保証しない remove3 はこのずらす処理が必要ないので、どの位置の要素を消しても処理速度が一定になるという事になります。
goos: windows
goarch: amd64
pkg: remove
cpu: AMD Ryzen 5 3500U with Radeon Vega Mobile Gfx
BenchmarkRemove1-8 1 1281985400 ns/op 24 B/op 3 allocs/op
BenchmarkRemove2-8 1 1453808700 ns/op 0 B/op 0 allocs/op
BenchmarkRemove3-8 19694 68062 ns/op 0 B/op 0 allocs/op
PASS
ok remove 4.767s
期待通り remove3 が速いです。上記のベンチマークのソースのコメント部分を入れ替え、常に最初の要素を消す様にした場合は以下の結果になります。
goos: windows
goarch: amd64
pkg: remove
cpu: AMD Ryzen 5 3500U with Radeon Vega Mobile Gfx
BenchmarkRemove1-8 1 4713567000 ns/op 16 B/op 2 allocs/op
BenchmarkRemove2-8 1 4537595900 ns/op 0 B/op 0 allocs/op
BenchmarkRemove3-8 18007 64091 ns/op 0 B/op 0 allocs/op
PASS
ok remove 11.220s
remove1 と remove2 は遅くなりました。もしスライスの順を気にしなくても良い様なケースであれば remove3 の方法を使うと良いでしょう。1点、注意する必要があります。メモリを確保しない様なプリミティブな型であれば問題無いのですが、例えば new を使う様なオブジェクトを保持するスライスは、サイズを縮めた最後の要素に参照が残ってしまいます。GC によりメモリを回収したい場合は
a[i] = a[len(a)-1]
a[len(a)-1] = nil
a = a[:len(a)-1]
この様にゼロ値を代入しておくと良いでしょう。
ところで append の方法は
勘のいい方は気付いたかもしれません。append の方法ですが、実はアロケーションが発生します。スライスを全要素足しこむ為に使う ... により、一時的にメモリが確保されます。多くのブログ(日本のみならず)では、この append を使う方法が書かれてしまっており、少し残念だったりします。可能であれば copy を使う方法が良いでしょう。
まとめ
Go 言語でのスライス要素の削除方法を3つご紹介しました。また順を考えなくていいスライスの場合に、パフォーマンスを良くする方法(remove3) を紹介しました。さらに append を使った方法の場合にメモリアロケーションが発生する事をご紹介しました。ぜひ皆さんのコードを一度見直し、パフォーマンスの良いコードに出来ないか検討してみて下さい。
Discussion