Skip to content

Instantly share code, notes, and snippets.

@Deleplace
Created November 7, 2022 15:30
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save Deleplace/941082b82d4b2922c638b06c98aed5e4 to your computer and use it in GitHub Desktop.
How much overhead for a STABLE sort of 1000 lowercase letters (26 possible values per letter), compared to a standard sort?
package stablesort
import (
"math/rand"
"sort"
"testing"
)
const (
M = 500
SIZE = 1000
)
func TestSlice(t *testing.T) {
r := rand.New(rand.NewSource(42))
data := randData(r)
comparisons := 0
for k := range data {
sort.Slice(data[k], func(i, j int) bool {
comparisons++
return data[k][i] < data[k][j]
})
}
t.Logf("sort.Slice: %d comparisons", comparisons)
}
func TestSliceStable(t *testing.T) {
r := rand.New(rand.NewSource(42))
data := randData(r)
comparisons := 0
for k := range data {
sort.SliceStable(data[k], func(i, j int) bool {
comparisons++
return data[k][i] < data[k][j]
})
}
t.Logf("sort.SliceStable: %d comparisons", comparisons)
}
func randLetter(r *rand.Rand) rune {
return 'a' + rune(r.Intn(26))
}
func randData(r *rand.Rand) [][]rune {
data := make([][]rune, M)
for i := range data {
data[i] = make([]rune, SIZE)
for j := range data[i] {
data[i][j] = randLetter(r)
}
}
return data
}
func TestData(t *testing.T) {
r := rand.New(rand.NewSource(42))
data := randData(r)
t.Log(string(data[0][:60])) // Okay this looks like "hrukpttuezptneuvunhuksqvgzadxlgghejkmvezjpmkqakmtrgkfbswyjun"
}
@Deleplace
Copy link
Author

    stablesort_test.go:25: sort.Slice: 3203928 comparisons
    stablesort_test.go:39: sort.SliceStable: 5340823 comparisons

-> 66% overhead in number of comparisons, when calling sort.SliceStable.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment