Go Wiki: SliceTricks

append組み込み関数の導入以来、Go 1で削除されたcontainer/vectorパッケージのほとんどの機能は、appendとcopyを使用して複製できます。

ジェネリクスの導入以来、これらの関数のいくつかのジェネリック実装がgolang.org/x/exp/slicesパッケージで利用可能です。

以下は、ベクターメソッドとそのスライス操作のアナログです

AppendVector

a = append(a, b...)

コピー

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

// These two are often a little slower than the above one,
// but they would be more efficient if there are more
// elements to be appended to b after copying.
b = append([]T(nil), a...)
b = append(a[:0:0], a...)

// This one-line implementation is equivalent to the above
// two-line make+copy implementation logically. But it is
// actually a bit slower (as of Go toolchain v1.16).
b = append(make([]T, 0, len(a)), a...)

カット

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

削除

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

順序を保持しない削除

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

注意 要素の型がポインタまたはポインタフィールドを持つ構造体であり、ガベージコレクションが必要な場合、上記のCutとDeleteの実装には、潜在的なメモリリークの問題があります。値を持ついくつかの要素が、スライスaの基になる配列によってまだ参照されていますが、スライスでは「表示」されていません。「削除」された値は基になる配列で参照されているため、値はコードで参照できませんが、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]

削除

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

順序を保持しない削除

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

拡張

位置iにn個の要素を挿入

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

拡張

n個の要素を追加

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

容量拡張

再割り当てせずにn個の要素を追加するスペースがあることを確認します

if cap(a)-len(a) < n {
    a = append(make([]T, 0, len(a)+n), a...)
}

フィルター（インプレース）

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

挿入

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

注意: 2番目のappendは、独自の基盤となるストレージを持つ新しいスライスを作成し、a[i:]の要素をそのスライスにコピーします。そして、これらの要素はスライスaにコピーされます（最初のappendによって）。新しいスライス（したがってメモリガベージ）の作成と2番目のコピーは、別の方法を使用することで回避できます

挿入

s = append(s, 0 /* use the zero value of the element type */)
copy(s[i+1:], s[i:])
s[i] = x

InsertVector

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

// The above one-line way copies a[i:] twice and
// allocates at least once.
// The following verbose way only copies elements
// in a[i:] once and allocates at most once.
// But, as of Go toolchain 1.16, due to lacking of
// optimizations to avoid elements clearing in the
// "make" call, the verbose way is not always faster.
//
// Future compiler optimizations might implement
// both in the most efficient ways.
//
// Assume element type is int.
func Insert(s []int, k int, vs ...int) []int {
    if n := len(s) + len(vs); n <= cap(s) {
        s2 := s[:n]
        copy(s2[k+len(vs):], s[k:])
        copy(s2[k:], vs)
        return s2
    }
    s2 := make([]int, len(s) + len(vs))
    copy(s2, s[:k])
    copy(s2[k:], vs)
    copy(s2[k+len(vs):], s[k:])
    return s2
}

a = Insert(a, i, b...)

プッシュ

a = append(a, x)

ポップ

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

先頭にプッシュ/unshift

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

先頭からポップ/シフト

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

追加のトリック

割り当てなしでフィルタリング

このトリックは、スライスが元のスライスと同じバッキング配列と容量を共有するという事実を利用しているため、ストレージはフィルター処理されたスライスに再利用されます。もちろん、元の内容は変更されます。

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 // or the zero value of T
}

反転

スライスの内容を、同じ要素で逆順に置き換える

for i := len(a)/2-1; i >= 0; i-- {
    opp := len(a)-1-i
    a[i], a[opp] = a[opp], a[i]
}

同じことですが、2つのインデックスを使用します

for left, right := 0, len(a)-1; left < right; left, right = left+1, right-1 {
    a[left], a[right] = a[right], a[left]
}

シャッフル

フィッシャー–イェーツアルゴリズム

go1.10以降、これはmath/rand.Shuffleで利用可能です

for i := len(a) - 1; i > 0; i-- {
    j := rand.Intn(i + 1)
    a[i], a[j] = a[j], a[i]
}

最小限の割り当てでのバッチ処理

大きなスライスでバッチ処理を行いたい場合に便利です。

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} // any item can be sorted
sort.Ints(in)
j := 0
for i := 1; i < len(in); i++ {
    if in[j] == in[i] {
        continue
    }
    j++
    // preserve the original data
    // in[i], in[j] = in[j], in[i]
    // only set what is required
    in[j] = in[i]
}
result := in[:j+1]
fmt.Println(result) // [1 2 3 4]

可能な場合は、先頭に移動するか、存在しない場合は先頭に追加します。

// moveToFront moves needle to the front of haystack, in place if possible.
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]

スライディングウィンドウ

func slidingWindow(size int, input []int) [][]int {
    // returns the input slice as the first element
    if len(input) <= size {
        return [][]int{input}
    }

    // allocate slice at the precise size we need
    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
}

このコンテンツは、Go Wikiの一部です。

go.devは、サービスの品質を提供および向上させ、トラフィックを分析するために、GoogleからのCookieを使用しています。 詳しくはこちら。