emahiro/b.log

日々の勉強の記録とか育児の記録とか。

トップ > Go > Go1.18 の Generics を使って Slice の重複削除の処理を書く

Go1.18 の Generics を使って Slice の重複削除の処理を書く

Go

Overview

Go でスライスの重複処理を実装するのに Generics が使えるので実際に実装してみました。

なお、Go1.18 以前の世界ではスライスの重複を削除するには map と空の struct を使って以下のように実装する必要がありました。

ema-hiro.hatenablog.com

なお、for を1回で実装するなら以下のようになります。

arr := [string]{"a", "b", "c", "a"}
m := make(map[string]struct{}) // 空のstructを使う
uniq := [] string{}
for _, ele := range arr {
    if _, ok := m[ele]; ok {
        continue
    }
    m[ele] = struct{}{} // m["a"] = struct{}{} が二度目は同じものとみなされて重複が消える。
    uniq := append(uniq, ele)
}

golang.org/x/exp/slices を使って重複削除の実装を書く

golang.org/x/exp/slices にある実装を使って重複削除を実装できます。
使用するのは以下の3つの関数です。

  • slices.Clip ... 余分に確保してるメモリ領域を解放する。後述の Compact をかけた前後で Slice が占有してるアロケーション領域が変わらない（要素は4になるけどcapacity は 8 のまま、ということ）のでこのアロケーション領域を圧縮するのに使います。
  • slices.Sort ...予約型のスライスを昇順で Sort する。
  • slices.Compact ... 昇順でソートされているスライスの重複要素を削除する。
    ※ Compact は string 型においては Sort されている状態じゃないと重複要素を削除できません。数値型については Sort されている状態ではなくても重複削除されます。
    ref: https://go.dev/play/p/tkfgpLwGgFX

上記の条件を踏まえた上で golang.org/x/exp/slices を使って重複削除の実装は以下になります。

func Uniq[T constraints.Ordered](s []T) []T {
    slices.Sort(s)
    return slices.Clip(slices.Compact(s))
}

※ Type Parameter には Sort 可能な constrains.Ordered を使用することで slices.Sort での並び替えを使えるようにします。

ベンチマークしてみる

書き換えたところで Generics を使っていない実装よりもパフォーマンスが落ちるのであれば抽象化したところでコードの削除とパフォーマンスがトレードオフになってしまいます。そのため Generics ( golang.org/x/exp/slices 内の実装) を使った重複削除処理のベンチを取ってみます。

※ 今まで使っていた重複削除処理を比較対象とします。

検証する実装は以下

func uniq[T constraints.Ordered](s []T) []T {
    slices.Sort(s)
    return slices.Clip(slices.Compact(s))
}

func legacyUniq(s []string) []string {
    m := make(map[string]struct{}, len(s))
    uniq := s[:0]
    for _, ss := range s {
        if _, ok := m[ss]; ok {
            continue
        }
        m[ss] = struct{}{}
        uniq = append(uniq, ss)
    }
    return uniq
}

ベンチマークを取る実装は以下

func BenchmarkUniq(b *testing.B) {
    s := []string{"1", "2", "3", "10", "9", "10", "9", "8", "100", "200", "100"}
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        uniq(s)
    }
}

func BenchmarkLegacyUniq(b *testing.B) {
    s := []string{"1", "2", "3", "10", "9", "10", "9", "8", "100", "200", "100"}
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        legacyUniq(s)
    }
}

結果は以下です。

go test -bench=. -benchmem
goos: darwin
goarch: amd64
pkg: github.com/emahiro/il/go-generics-il
cpu: VirtualApple @ 2.50GHz
BenchmarkUniq-10                13086816                91.91 ns/op            0 B/op          0 allocs/op
BenchmarkLegacyUniq-10           2504686               474.2 ns/op           288 B/op          1 allocs/op
PASS
ok      github.com/emahiro/il/go-generics-il    3.260s

Generics を使った処理の方がパフォーマンスが良い、という結果になりました。

まとめ

既に公開されている slices パッケージの機能を使って、今まで Go では冗長に書かざる得なかった重複削除処理をスマートに書き直すことができました。
パフォーマンス観点でも新しい機能を使ってみた方が良い結果が得られたのも良い発見でした。

Generics をさっと触ってみて思いましたが、Go1.18 で導入された Generics を使う際には、ゴリゴリこれを使って今まで Go になかったような機能を実装するよりもまず Go ならではの冗長な実装を Generics を使って抽象化していく、あたりから始めると良さそうだなと思いました。まだ出来立てホヤホヤの機能だし必要になったら使う、くらいのモチベーションの方がいいのかもしれません。
それはそれとして慣れるために何がなんでも Generics 使って書く、みたいなのもまぁありだとは思います。