Go でスライスに挿入する例として Go の Wiki に以下の物が記載されている。
作ろうしているツールで、
— ゴリラ@バナナバナナバナナバナナバナナバナナバナナバナナバナナバナナバナナバナナバナナバナナバナナ (@gorilla0513) April 4, 2020
Goのスライスのinsertをする必要があって、
スライスの動きを理解するために、自分で実装したあとに、Goの公式Wikiを見て頭いいなと思ったhttps://t.co/vmonuxbjOl
a = append(a[:i], append([]T{x}, a[i:]...)...)
しかしこのコードは、挿入されるスライスから部分スライスを取り出し、そこに挿入するスライスを append に割り当てる為に展開し、さらに残りの部分スライスも append に割り当てる展開を行っている。なので実装コードとしては短いが、実際に実行されるオペレーションコードが冗長になる。また、スライスの伸長はおよそ2倍ずつ増える。なので例えば 5000 個のスライスに 1000 個のアイテムを挿入すると、キャパシティはおよそ 12000 近くになる。Go ではこういったスライスの操作も、基本的には自身で make によりメモリを確保し、ループで値を割り当てるのが良い(面倒かもしれないがその方がメモリも節約され速い)とされている。
以下、ベンチマークを取ってみる。
package main_test
import (
"reflect"
"testing"
)
type T int
func BenchmarkAppend(b *testing.B) {
b.ResetTimer()
input := make([]int, 5000)
for i := 0; i < 5000; i++ {
input[i] = i
}
insert := make([]int, 1000)
for i := 0; i < 1000; i++ {
insert[i] = i
}
expected := make([]int, 6000)
for i := 0; i < 6000; i++ {
if i < 1000 {
expected[i] = i
} else if i < 2000 {
expected[i] = i - 1000
} else {
expected[i] = i - 1000
}
}
n := 1000
var output []int
b.ResetTimer()
for i := 0; i < b.N; i++ {
output = append(input[:n], append(insert, input[n:]...)...)
}
b.StopTimer()
if !reflect.DeepEqual(output, expected) {
b.Fatal("bad insertion")
}
}
func BenchmarkNormal(b *testing.B) {
input := make([]int, 5000)
for i := 0; i < 5000; i++ {
input[i] = i
}
insert := make([]int, 1000)
for i := 0; i < 1000; i++ {
insert[i] = i
}
expected := make([]int, 6000)
for i := 0; i < 6000; i++ {
if i < 1000 {
expected[i] = i
} else if i < 2000 {
expected[i] = i - 1000
} else {
expected[i] = i - 1000
}
}
n := 1000
var output []int
b.ResetTimer()
for i := 0; i < b.N; i++ {
output = make([]int, len(input)+len(insert))
for l := 0; l < n; l++ {
output[l] = input[l]
}
for l := 0; l < len(insert); l++ {
output[l+n] = insert[l]
}
for l := n; l < len(input); l++ {
output[l+len(insert)] = input[l]
}
}
b.StopTimer()
if !reflect.DeepEqual(output, expected) {
b.Fatal("bad insertion")
}
}
func BenchmarkCopy(b *testing.B) {
input := make([]int, 5000)
for i := 0; i < 5000; i++ {
input[i] = i
}
insert := make([]int, 1000)
for i := 0; i < 1000; i++ {
insert[i] = i
}
expected := make([]int, 6000)
for i := 0; i < 6000; i++ {
if i < 1000 {
expected[i] = i
} else if i < 2000 {
expected[i] = i - 1000
} else {
expected[i] = i - 1000
}
}
n := 1000
var output []int
b.ResetTimer()
for i := 0; i < b.N; i++ {
output = make([]int, len(input)+len(insert))
copy(output, input[:n])
copy(output[n:], insert)
copy(output[n+len(insert):], input[n:])
}
b.StopTimer()
if !reflect.DeepEqual(output, expected) {
b.Fatal("bad insertion")
}
}
BenchmarkAppend-8 42700 26185 ns/op
BenchmarkNormal-8 70170 18005 ns/op
BenchmarkCopy-8 90902 15787 ns/op
Wiki に載っているコードは、手動でスライスを挿入するコードの1.5～2倍遅い。copy を使うともう少し速い。
