Help us understand the problem. What is going on with this article?

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした