partial/sort_test.go at master · viterin/partial · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
package partial

import (
	"fmt"
	"math/rand"
	"sort"
	"testing"

	"golang.org/x/exp/slices"
)

func TestSort(t *testing.T) {
	cases := []testCase[int]{
		{[]int{}, 0},
		{[]int{2}, 1},
		{[]int{2, 1}, 1},
		{[]int{2, 1}, 2},
		{[]int{1, 1, 1}, 2},
		{[]int{5, 0, 0, 0, 1}, 2},
		{[]int{5, 0, 0, 0, 1}, 5},
	}
	rand.Seed(2)
	big := make([]int, 100_000)
	for i := 0; i < 100_000; i++ {
		big[i] = rand.Intn(10_000)
	}
	cases = append(cases, testCase[int]{big, 10_000})
	for _, c := range cases {
		Sort(c.x, c.k)
		if !slices.IsSorted(c.x[:c.k]) {
			t.Errorf("Not sorted, out=%v, k=%v", c.x, c.k)
		}
	}
}

func TestSortFunc(t *testing.T) {
	cases := []testCase[person]{
		{[]person{{"bob", 45}, {"jane", 31}}, 1},
		{[]person{{"bob", 45}, {"jane", 31}}, 2},
		{[]person{{"bob", 45}, {"jane", 31}, {"karl", 39}}, 2},
		{[]person{{"bob", 45}, {"jane", 31}, {"karl", 39}}, 3},
	}
	cmp := func(x, y person) int { return x.age - y.age }
	for _, c := range cases {
		SortFunc(c.x, c.k, cmp)
		if !slices.IsSortedFunc(c.x[:c.k], cmp) {
			t.Errorf("Not sorted, out=%v, k=%v", c.x, c.k)
		}
	}
}

func TestSortOutOfBounds(t *testing.T) {
	cmp := func(x, y int) int { return x - y }

	x := []int{9, 2, 5}

	Sort(x, -1)
	if !slices.Equal(x, []int{9, 2, 5}) {
		t.Errorf("Negative k should be treated as zero and sort nothing")
	}

	y := []int{9, 2, 5}
	SortFunc(y, 5, cmp)
	if !slices.Equal(y, []int{2, 5, 9}) {
		t.Errorf("Entire slice should be sorted when k is greater than len")
	}
}

func BenchmarkSort(b *testing.B) {
	sizes := []int{1_000, 10_000, 100_000}
	k := 100
	for _, size := range sizes {
		var x []int
		for i := 0; i < size; i++ {
			x = append(x, rand.Intn(size/10))
		}
		b.Run(fmt.Sprintf("sort.Slice_%d", size), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				b.StopTimer()
				y := slices.Clone(x)
				b.StartTimer()
				sort.Slice(y, func(i, j int) bool { return y[i] < y[j] })
			}
		})
		b.Run(fmt.Sprintf("slices.Sort_%d", size), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				b.StopTimer()
				y := slices.Clone(x)
				b.StartTimer()
				slices.Sort(y)
			}
		})
		b.Run(fmt.Sprintf("slices.SortFunc_%d", size), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				b.StopTimer()
				y := slices.Clone(x)
				b.StartTimer()
				slices.SortFunc(y, func(i, j int) int { return i - j })
			}
		})
		b.Run(fmt.Sprintf("partial.Sort_%d", size), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				b.StopTimer()
				y := slices.Clone(x)
				b.StartTimer()
				Sort(y, k)
			}
		})
		b.Run(fmt.Sprintf("partial.SortFunc_%d", size), func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				b.StopTimer()
				y := slices.Clone(x)
				b.StartTimer()
				SortFunc(y, k, func(i, j int) int { return i - j })
			}
		})
	}
}