LoginSignup
6
2

More than 5 years have passed since last update.

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

Posted at

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 の方が遅いのかなという印象がありました。
ですが、速度差が殆ど無いとなると、気兼ねなく使っていけそうですね。

6
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
6
2