Posted at

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 の方が遅いのかなという印象がありました。

ですが、速度差が殆ど無いとなると、気兼ねなく使っていけそうですね。