title: 【転載】スライス操作のテクニック
date: 2021-08-11 10:47:54
comment: false
toc: true
category:
- Golang
tags: - 転載
- Go
- スライス
- 操作
この記事は転載元：[訳] スライス操作のテクニック | 李文周のブログです。
この記事は公式 wiki から翻訳され、Go 言語におけるスライス操作のいくつかのテクニックを整理しました。
備考：文の流れ上、一部の詳細が原文と若干異なる場合があります。
スライス操作の一般的なテクニック#
コピー#
スライス a の要素をスライス b にコピーします。
最も簡単で一般的な方法は、組み込みのcopy関数を使用することです。
b = make([]T, len(a)) // 一度にメモリを確保
copy(b, a)
組み込みのcopy関数を使用する以外にも、以下の 2 つのappend関数を使用してスライスをコピーする方法があります。
b = append([]T(nil), a...)
b = append(a[:0:0], a...)
これらの 2 つの方法は通常、copy関数を使用する方法よりも遅くなりますが、コピー後に b に追加する要素が多い場合は、効率が高くなります。
カット#
スライス a のインデックス i〜j の位置の要素をカットします。
以下のように、append関数を使用して完了できます。
a = append(a[:i], a[j:]...)
削除#
スライス a のインデックス位置 i の要素を削除します。
上記のカットの方法と同様に、append関数を使用して削除操作を完了できます。
a = append(a[:i], a[i+1:]...)
または、copy関数とスライス式を組み合わせて削除操作を完了できます。
a = a[:i+copy(a[i:], a[i+1:])]
さらに、インデックス i の要素だけを削除し、スライスの要素の元の順序を保持する必要がない場合は、以下のような簡単な方法で削除できます。
a[i] = a[len(a)-1] // 最後の要素をインデックスiに移動
a = a[:len(a)-1] // 最後の要素を切り取る
カットまたは削除操作によるメモリリークの可能性#
特に注意が必要です。スライス a の要素がポインタ型またはポインタフィールドを含む構造体型（ガベージコレクションが必要）である場合、上記のカットおよび削除のサンプルコードには潜在的なメモリリークの問題があります：いくつかの値を持つ要素がスライス a によって参照され続けるため、ガベージコレクションメカニズムによって回収されません。以下のコードはこの問題を解決できます。
カット#
copy(a[i:], a[j:])
for k, n := len(a)-j+i, len(a); k < n; k++ {
a[k] = nil // または型Tのゼロ値
}
a = a[:len(a)-j+i]
削除#
copy(a[i:], a[i+1:])
a[len(a)-1] = nil // または型Tのゼロ値
a = a[:len(a)-1]
元の順序を保持せずに削除#
a[i] = a[len(a)-1]
a[len(a)-1] = nil
a = a[:len(a)-1]
内部拡張#
スライス a のインデックス i の後に j 個の要素を拡張します。
2 つのappend関数を使用して、まずインデックス i の後の要素を長さ j のスライスに追加し、その後このスライスのすべての要素をスライス a のインデックス i の後に追加します。
a = append(a[:i], append(make([]T, j), a[i:]...)...)
拡張されたこの部分の要素は T 型のゼロ値です。
尾部拡張#
スライス a の尾部を j 個の要素のスペースで拡張します。
a = append(a, make([]T, j)...)
拡張されたこの部分の要素も同様に T 型のゼロ値です。
フィルタリング#
一定のルールに従ってスライス a の要素をインプレースでフィルタリングします。
ここでは、フィルタリング条件がkeep関数としてカプセル化されていると仮定し、for rangeを使用してスライス a のすべての要素を一つずつkeep関数でフィルタリングします。
n := 0
for _, x := range a {
if keep(x) {
a[n] = x // この要素を保持
n++
}
}
a = a[:n] // 保持する必要のある要素をスライスから切り取る
挿入#
要素 x をスライス a のインデックス i に挿入します。
やはり 2 つのappend関数を使用して x の挿入操作を完了します。
a = append(a[:i], append([]T{x}, a[i:]...)...)
2 番目のappend関数は、自分自身の基底配列を持つ新しいスライスを作成し、a[i:]の要素をそのスライスにコピーし、最初のappend関数によってこれらの要素がスライス a にコピーされます。
新しいスライスの作成（およびそれに伴うメモリのゴミ）と 2 回目のコピーを回避するために、別の方法を使用できます：
a = append(a, 0 /* ここでは要素タイプのゼロ値を使用するべき */)
copy(a[i+1:], a[i:])
a[i] = x
追加#
要素 x をスライス a の最後に追加します。
ここではappend関数を使用します。
a = append(a, x)
ポップ#
スライス a の最後の要素をポップします。
ここではスライス式を使用してポップ操作を完了します。
x, a = a[len(a)-1], a[:len(a)-1]
スライス a の最初の要素をポップします。
x, a = a[0], a[1:]
前挿入#
要素 x をスライス a の先頭に前挿入します。
a = append([]T{x}, a...)
その他のテクニック#
メモリを割り当てずにフィルタリング#
このテクニックは、スライス b が元のスライス a と同じ基底配列と容量を共有しているという事実を利用しているため、元のストレージスペースがフィルタリングされたスライスに再利用されます。もちろん、元のスライスの内容は変更されます。
b := a[:0]
for _, x := range a {
if f(x) {
b = append(b, x)
}
}
ガベージコレクションが必要な要素については、上記の操作を完了した後に以下のコードを追加できます：
for i := len(b); i < len(a); i++ {
a[i] = nil // またはT型のゼロ値
}
反転#
スライス a の要素の順序を反転します。
2 つの要素を交互に入れ替えることで完了します。
for i := len(a)/2-1; i >= 0; i-- {
opp := len(a)-1-i
a[i], a[opp] = a[opp], a[i]
}
同様の操作：
for left, right := 0, len(a)-1; left < right; left, right = left+1, right-1 {
a[left], a[right] = a[right], a[left]
}
シャッフル#
スライス a の要素の順序を乱します。
Fisher–Yates アルゴリズム：
for i := len(a) - 1; i > 0; i-- {
j := rand.Intn(i + 1)
a[i], a[j] = a[j], a[i]
}
go1.10 以降、math/rand.Shuffleを使用できます。
rand.Shuffle(len(a), func(i, j int) {
a[i], a[j] = a[j], a[i]
})
最小割り当てを使用したバッチ処理#
大きなスライス a の要素をバッチ処理する場合に便利です。
actions := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
batchSize := 3
batches := make([][]int, 0, (len(actions) + batchSize - 1) / batchSize)
for batchSize < len(actions) {
actions, batches = actions[batchSize:], append(batches, actions[0:batchSize:batchSize])
}
batches = append(batches, actions)
得られる効果は次の通りです：
[[0 1 2] [3 4 5] [6 7 8] [9]]
インプレースで重複要素を削除（要素は比較可能）#
import "sort"
in := []int{3,2,1,4,3,2,1,4,1} // スライスの要素は任意のソート可能な型
sort.Ints(in)
j := 0
for i := 1; i < len(in); i++ {
if in[j] == in[i] {
continue
}
j++
// 元のデータを保持する必要がある場合
// in[i], in[j] = in[j], in[i]
// 必要なデータだけを保持する場合
in[j] = in[i]
}
result := in[:j+1]
fmt.Println(result) // [1 2 3 4]
存在すれば前に移動し、存在しなければ前に挿入#
与えられた要素がスライスに存在する場合は、その要素をスライスの先頭に移動し、存在しない場合はその要素をスライスの先頭に挿入します。
// moveToFront はneedleをhaystackの前に移動または追加します
func moveToFront(needle string, haystack []string) []string {
if len(haystack) != 0 && haystack[0] == needle {
return haystack
}
prev := needle
for i, elem := range haystack {
switch {
case i == 0:
haystack[0] = needle
prev = elem
case elem == needle:
haystack[i] = prev
return haystack
default:
haystack[i] = prev
prev = elem
}
}
return append(haystack, prev)
}
haystack := []string{"a", "b", "c", "d", "e"} // [a b c d e]
haystack = moveToFront("c", haystack) // [c a b d e]
haystack = moveToFront("f", haystack) // [f c a b d e]
スライディングウィンドウ#
スライス input からサイズのスライディングウィンドウを生成します。
func slidingWindow(size int, input []int) [][]int {
// 引数のスライスを最初の要素として返す
if len(input) <= size {
return [][]int{input}
}
// 必要な正確なサイズでスライスを割り当てる
r := make([][]int, 0, len(input)-size+1)
for i, j := 0, size; j <= len(input); i, j = i+1, j+1 {
r = append(r, input[i:j])
}
return r
}
例：
a := []int{1, 2, 3, 4, 5}
res := slidingWindow(2, a)
fmt.Println(res)
出力：
[[1 2] [2 3] [3 4] [4 5]]