| // Copyright 2023 The Go Authors. All rights reserved. | |
| // Use of this source code is governed by a BSD-style | |
| // license that can be found in the LICENSE file. | |
| package sort_test | |
| import ( | |
| "math/rand" | |
| "slices" | |
| . "sort" | |
| "strconv" | |
| stringspkg "strings" | |
| "testing" | |
| ) | |
| // Benchmarks comparing sorting from the slices package with functions from | |
| // the sort package (avoiding functions that are just forwarding to the slices | |
| // package). | |
| func makeRandomInts(n int) []int { | |
| rand.Seed(42) | |
| ints := make([]int, n) | |
| for i := 0; i < n; i++ { | |
| ints[i] = rand.Intn(n) | |
| } | |
| return ints | |
| } | |
| func makeSortedInts(n int) []int { | |
| ints := make([]int, n) | |
| for i := 0; i < n; i++ { | |
| ints[i] = i | |
| } | |
| return ints | |
| } | |
| func makeReversedInts(n int) []int { | |
| ints := make([]int, n) | |
| for i := 0; i < n; i++ { | |
| ints[i] = n - i | |
| } | |
| return ints | |
| } | |
| func makeSortedStrings(n int) []string { | |
| x := make([]string, n) | |
| for i := 0; i < n; i++ { | |
| x[i] = strconv.Itoa(i) | |
| } | |
| Strings(x) | |
| return x | |
| } | |
| const N = 100_000 | |
| func BenchmarkSortInts(b *testing.B) { | |
| for i := 0; i < b.N; i++ { | |
| b.StopTimer() | |
| ints := makeRandomInts(N) | |
| b.StartTimer() | |
| Sort(IntSlice(ints)) | |
| } | |
| } | |
| func BenchmarkSlicesSortInts(b *testing.B) { | |
| for i := 0; i < b.N; i++ { | |
| b.StopTimer() | |
| ints := makeRandomInts(N) | |
| b.StartTimer() | |
| slices.Sort(ints) | |
| } | |
| } | |
| func BenchmarkSortIsSorted(b *testing.B) { | |
| for i := 0; i < b.N; i++ { | |
| b.StopTimer() | |
| ints := makeSortedInts(N) | |
| b.StartTimer() | |
| IsSorted(IntSlice(ints)) | |
| } | |
| } | |
| func BenchmarkSlicesIsSorted(b *testing.B) { | |
| for i := 0; i < b.N; i++ { | |
| b.StopTimer() | |
| ints := makeSortedInts(N) | |
| b.StartTimer() | |
| slices.IsSorted(ints) | |
| } | |
| } | |
| // makeRandomStrings generates n random strings with alphabetic runes of | |
| // varying lengths. | |
| func makeRandomStrings(n int) []string { | |
| rand.Seed(42) | |
| var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ") | |
| ss := make([]string, n) | |
| for i := 0; i < n; i++ { | |
| var sb stringspkg.Builder | |
| slen := 2 + rand.Intn(50) | |
| for j := 0; j < slen; j++ { | |
| sb.WriteRune(letters[rand.Intn(len(letters))]) | |
| } | |
| ss[i] = sb.String() | |
| } | |
| return ss | |
| } | |
| func BenchmarkSortStrings(b *testing.B) { | |
| for i := 0; i < b.N; i++ { | |
| b.StopTimer() | |
| ss := makeRandomStrings(N) | |
| b.StartTimer() | |
| Sort(StringSlice(ss)) | |
| } | |
| } | |
| func BenchmarkSlicesSortStrings(b *testing.B) { | |
| for i := 0; i < b.N; i++ { | |
| b.StopTimer() | |
| ss := makeRandomStrings(N) | |
| b.StartTimer() | |
| slices.Sort(ss) | |
| } | |
| } | |
| func BenchmarkSortStrings_Sorted(b *testing.B) { | |
| ss := makeSortedStrings(N) | |
| b.ResetTimer() | |
| for i := 0; i < b.N; i++ { | |
| Sort(StringSlice(ss)) | |
| } | |
| } | |
| func BenchmarkSlicesSortStrings_Sorted(b *testing.B) { | |
| ss := makeSortedStrings(N) | |
| b.ResetTimer() | |
| for i := 0; i < b.N; i++ { | |
| slices.Sort(ss) | |
| } | |
| } | |
| // These benchmarks compare sorting a slice of structs with sort.Sort vs. | |
| // slices.SortFunc. | |
| type myStruct struct { | |
| a, b, c, d string | |
| n int | |
| } | |
| type myStructs []*myStruct | |
| func (s myStructs) Len() int { return len(s) } | |
| func (s myStructs) Less(i, j int) bool { return s[i].n < s[j].n } | |
| func (s myStructs) Swap(i, j int) { s[i], s[j] = s[j], s[i] } | |
| func makeRandomStructs(n int) myStructs { | |
| rand.Seed(42) | |
| structs := make([]*myStruct, n) | |
| for i := 0; i < n; i++ { | |
| structs[i] = &myStruct{n: rand.Intn(n)} | |
| } | |
| return structs | |
| } | |
| func TestStructSorts(t *testing.T) { | |
| ss := makeRandomStructs(200) | |
| ss2 := make([]*myStruct, len(ss)) | |
| for i := range ss { | |
| ss2[i] = &myStruct{n: ss[i].n} | |
| } | |
| Sort(ss) | |
| slices.SortFunc(ss2, func(a, b *myStruct) int { return a.n - b.n }) | |
| for i := range ss { | |
| if *ss[i] != *ss2[i] { | |
| t.Fatalf("ints2 mismatch at %d; %v != %v", i, *ss[i], *ss2[i]) | |
| } | |
| } | |
| } | |
| func BenchmarkSortStructs(b *testing.B) { | |
| for i := 0; i < b.N; i++ { | |
| b.StopTimer() | |
| ss := makeRandomStructs(N) | |
| b.StartTimer() | |
| Sort(ss) | |
| } | |
| } | |
| func BenchmarkSortFuncStructs(b *testing.B) { | |
| cmpFunc := func(a, b *myStruct) int { return a.n - b.n } | |
| for i := 0; i < b.N; i++ { | |
| b.StopTimer() | |
| ss := makeRandomStructs(N) | |
| b.StartTimer() | |
| slices.SortFunc(ss, cmpFunc) | |
| } | |
| } |