Go
golang

sort.Sort と sort.Slice の速度比較

More than 1 year has passed since last update.

Go 言語の標準パッケージ sort には、従来からある sort.Sort 系の関数と、1.8 から追加された sort.Slice 系の関数があります。

それぞれを使った場合、コードとしては次のように記述することになります。

// 従来の sort.Sort
type ByValue []string
func (s ByValue) Len() int           { return len(s) }
func (s ByValue) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s ByValue) Less(i, j int) bool { return s[i] < s[j] }
var sslice []string = ...
sort.Sort(ByValue(sslice))

// sort.Slice
var sslice []string = ...
sort.Slice(sslice, func(i, j int) bool { return sslice[i] < sslice[j] })

スライスを対象にソートするのであれば、sort.Slice のほうが簡単そうです。

しかし、そうした場合、両者に速度差はあるのでしょうか?

結論: どっちでもよい

以下は、スライスの初期化を含むベンチマーク(単位あたりの処理速度)です。

方式 10 100 1,000 10,000
sort.Sort 385 ns/op 7145 ns/op 156903 ns/op 2274963 ns/op
sort.Slice 423 ns/op 7095 ns/op 149799 ns/op 2136996 ns/op

大差ないので、好きな方を使いましょう。

上では処理速度のみを掲載しましたが、メモリの使用度合いも大差ありませんでした。

ベンチマーク

込み入った比較や統計はせず、単純に3回実行してその中央値っぽい回の結果を使っています。

10要素
>go test -bench=. -benchmem ./...
goos: windows
goarch: amd64
pkg: my/sorthikaku
BenchmarkOldStyleSort-4          5000000               385 ns/op             192 B/op          2 allocs/op
BenchmarkSortSlice-4             3000000               423 ns/op             224 B/op          3 allocs/op
PASS
ok      my/sorthikaku   4.138s
100要素
BenchmarkOldStyleSort-4           200000              7145 ns/op            1824 B/op          2 allocs/op
BenchmarkSortSlice-4              200000              7095 ns/op            1856 B/op          3 allocs/op
1,000要素
BenchmarkOldStyleSort-4            10000            156903 ns/op           16416 B/op          2 allocs/op
BenchmarkSortSlice-4               10000            149799 ns/op           16448 B/op          3 allocs/op
10,000要素
BenchmarkOldStyleSort-4             1000           2274963 ns/op          163872 B/op          2 allocs/op
BenchmarkSortSlice-4                1000           2136996 ns/op          163904 B/op          3 allocs/op

コード

比較に使ったコードを掲載しておきます。

sort_test.go
package main

import (
    "fmt"
    "math/rand"
    "sort"
    "testing"
    "time"
)

type ByValue []string
func (s ByValue) Len() int           { return len(s) }
func (s ByValue) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s ByValue) Less(i, j int) bool { return s[i] < s[j] }

func genRamdomSeq(n int) []string {
    result := make([]string, n)

    rand.Seed(time.Now().UnixNano())
    for i := 0; i < n; i++ {
        result[i] = fmt.Sprintf("%d", rand.Int())
    }

    return result
}

const seqSize = 10000

func BenchmarkOldStyleSort(b *testing.B) {
    orig := genRamdomSeq(seqSize)
    b.ResetTimer()
    for n := 0; n < b.N; n++ {
        sslice := make([]string, len(orig))
        copy(sslice, orig)

        sort.Sort(ByValue(sslice))
    }
}

func BenchmarkSortSlice(b *testing.B) {
    orig := genRamdomSeq(seqSize)
    b.ResetTimer()
    for n := 0; n < b.N; n++ {
        sslice := make([]string, len(orig))
        copy(sslice, orig)

        sort.Slice(sslice, func(i, j int) bool { return sslice[i] < sslice[j] })
    }
}

最後に

sort.Slice は内部で reflect を使っているところがありますが、それだけ聞くと、sort.Slice の方が遅いのかなという印象がありました。
ですが、速度差が殆ど無いとなると、気兼ねなく使っていけそうですね。