Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
2
Help us understand the problem. What is going on with this article?
@chimatter

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

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

2
Help us understand the problem. What is going on with this article?
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.
Sign Up
If you already have a Qiita account Login
2
Help us understand the problem. What is going on with this article?