Source file
src/sort/sort_test.go
Documentation: sort
1
2
3
4
5 package sort_test
6
7 import (
8 "fmt"
9 "internal/testenv"
10 "math"
11 "math/rand"
12 . "sort"
13 "strconv"
14 stringspkg "strings"
15 "testing"
16 )
17
18 var ints = [...]int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586}
19 var float64s = [...]float64{74.3, 59.0, math.Inf(1), 238.2, -784.0, 2.3, math.NaN(), math.NaN(), math.Inf(-1), 9845.768, -959.7485, 905, 7.8, 7.8}
20 var strings = [...]string{"", "Hello", "foo", "bar", "foo", "f00", "%*&^*&^&", "***"}
21
22 func TestSortIntSlice(t *testing.T) {
23 data := ints
24 a := IntSlice(data[0:])
25 Sort(a)
26 if !IsSorted(a) {
27 t.Errorf("sorted %v", ints)
28 t.Errorf(" got %v", data)
29 }
30 }
31
32 func TestSortFloat64Slice(t *testing.T) {
33 data := float64s
34 a := Float64Slice(data[0:])
35 Sort(a)
36 if !IsSorted(a) {
37 t.Errorf("sorted %v", float64s)
38 t.Errorf(" got %v", data)
39 }
40 }
41
42 func TestSortStringSlice(t *testing.T) {
43 data := strings
44 a := StringSlice(data[0:])
45 Sort(a)
46 if !IsSorted(a) {
47 t.Errorf("sorted %v", strings)
48 t.Errorf(" got %v", data)
49 }
50 }
51
52 func TestInts(t *testing.T) {
53 data := ints
54 Ints(data[0:])
55 if !IntsAreSorted(data[0:]) {
56 t.Errorf("sorted %v", ints)
57 t.Errorf(" got %v", data)
58 }
59 }
60
61 func TestFloat64s(t *testing.T) {
62 data := float64s
63 Float64s(data[0:])
64 if !Float64sAreSorted(data[0:]) {
65 t.Errorf("sorted %v", float64s)
66 t.Errorf(" got %v", data)
67 }
68 }
69
70 func TestStrings(t *testing.T) {
71 data := strings
72 Strings(data[0:])
73 if !StringsAreSorted(data[0:]) {
74 t.Errorf("sorted %v", strings)
75 t.Errorf(" got %v", data)
76 }
77 }
78
79 func TestSlice(t *testing.T) {
80 data := strings
81 Slice(data[:], func(i, j int) bool {
82 return data[i] < data[j]
83 })
84 if !SliceIsSorted(data[:], func(i, j int) bool { return data[i] < data[j] }) {
85 t.Errorf("sorted %v", strings)
86 t.Errorf(" got %v", data)
87 }
88 }
89
90 func TestSortLarge_Random(t *testing.T) {
91 n := 1000000
92 if testing.Short() {
93 n /= 100
94 }
95 data := make([]int, n)
96 for i := 0; i < len(data); i++ {
97 data[i] = rand.Intn(100)
98 }
99 if IntsAreSorted(data) {
100 t.Fatalf("terrible rand.rand")
101 }
102 Ints(data)
103 if !IntsAreSorted(data) {
104 t.Errorf("sort didn't sort - 1M ints")
105 }
106 }
107
108 func TestReverseSortIntSlice(t *testing.T) {
109 data := ints
110 data1 := ints
111 a := IntSlice(data[0:])
112 Sort(a)
113 r := IntSlice(data1[0:])
114 Sort(Reverse(r))
115 for i := 0; i < len(data); i++ {
116 if a[i] != r[len(data)-1-i] {
117 t.Errorf("reverse sort didn't sort")
118 }
119 if i > len(data)/2 {
120 break
121 }
122 }
123 }
124
125 type nonDeterministicTestingData struct {
126 r *rand.Rand
127 }
128
129 func (t *nonDeterministicTestingData) Len() int {
130 return 500
131 }
132 func (t *nonDeterministicTestingData) Less(i, j int) bool {
133 if i < 0 || j < 0 || i >= t.Len() || j >= t.Len() {
134 panic("nondeterministic comparison out of bounds")
135 }
136 return t.r.Float32() < 0.5
137 }
138 func (t *nonDeterministicTestingData) Swap(i, j int) {
139 if i < 0 || j < 0 || i >= t.Len() || j >= t.Len() {
140 panic("nondeterministic comparison out of bounds")
141 }
142 }
143
144 func TestNonDeterministicComparison(t *testing.T) {
145
146
147 defer func() {
148 if r := recover(); r != nil {
149 t.Error(r)
150 }
151 }()
152
153 td := &nonDeterministicTestingData{
154 r: rand.New(rand.NewSource(0)),
155 }
156
157 for i := 0; i < 10; i++ {
158 Sort(td)
159 }
160 }
161
162 func BenchmarkSortString1K(b *testing.B) {
163 b.StopTimer()
164 unsorted := make([]string, 1<<10)
165 for i := range unsorted {
166 unsorted[i] = strconv.Itoa(i ^ 0x2cc)
167 }
168 data := make([]string, len(unsorted))
169
170 for i := 0; i < b.N; i++ {
171 copy(data, unsorted)
172 b.StartTimer()
173 Strings(data)
174 b.StopTimer()
175 }
176 }
177
178 func BenchmarkSortString1K_Slice(b *testing.B) {
179 b.StopTimer()
180 unsorted := make([]string, 1<<10)
181 for i := range unsorted {
182 unsorted[i] = strconv.Itoa(i ^ 0x2cc)
183 }
184 data := make([]string, len(unsorted))
185
186 for i := 0; i < b.N; i++ {
187 copy(data, unsorted)
188 b.StartTimer()
189 Slice(data, func(i, j int) bool { return data[i] < data[j] })
190 b.StopTimer()
191 }
192 }
193
194 func BenchmarkStableString1K(b *testing.B) {
195 b.StopTimer()
196 unsorted := make([]string, 1<<10)
197 for i := range unsorted {
198 unsorted[i] = strconv.Itoa(i ^ 0x2cc)
199 }
200 data := make([]string, len(unsorted))
201
202 for i := 0; i < b.N; i++ {
203 copy(data, unsorted)
204 b.StartTimer()
205 Stable(StringSlice(data))
206 b.StopTimer()
207 }
208 }
209
210 func BenchmarkSortInt1K(b *testing.B) {
211 b.StopTimer()
212 for i := 0; i < b.N; i++ {
213 data := make([]int, 1<<10)
214 for i := 0; i < len(data); i++ {
215 data[i] = i ^ 0x2cc
216 }
217 b.StartTimer()
218 Ints(data)
219 b.StopTimer()
220 }
221 }
222
223 func BenchmarkStableInt1K(b *testing.B) {
224 b.StopTimer()
225 unsorted := make([]int, 1<<10)
226 for i := range unsorted {
227 unsorted[i] = i ^ 0x2cc
228 }
229 data := make([]int, len(unsorted))
230 for i := 0; i < b.N; i++ {
231 copy(data, unsorted)
232 b.StartTimer()
233 Stable(IntSlice(data))
234 b.StopTimer()
235 }
236 }
237
238 func BenchmarkStableInt1K_Slice(b *testing.B) {
239 b.StopTimer()
240 unsorted := make([]int, 1<<10)
241 for i := range unsorted {
242 unsorted[i] = i ^ 0x2cc
243 }
244 data := make([]int, len(unsorted))
245 for i := 0; i < b.N; i++ {
246 copy(data, unsorted)
247 b.StartTimer()
248 SliceStable(data, func(i, j int) bool { return data[i] < data[j] })
249 b.StopTimer()
250 }
251 }
252
253 func BenchmarkSortInt64K(b *testing.B) {
254 b.StopTimer()
255 for i := 0; i < b.N; i++ {
256 data := make([]int, 1<<16)
257 for i := 0; i < len(data); i++ {
258 data[i] = i ^ 0xcccc
259 }
260 b.StartTimer()
261 Ints(data)
262 b.StopTimer()
263 }
264 }
265
266 func BenchmarkSortInt64K_Slice(b *testing.B) {
267 b.StopTimer()
268 for i := 0; i < b.N; i++ {
269 data := make([]int, 1<<16)
270 for i := 0; i < len(data); i++ {
271 data[i] = i ^ 0xcccc
272 }
273 b.StartTimer()
274 Slice(data, func(i, j int) bool { return data[i] < data[j] })
275 b.StopTimer()
276 }
277 }
278
279 func BenchmarkStableInt64K(b *testing.B) {
280 b.StopTimer()
281 for i := 0; i < b.N; i++ {
282 data := make([]int, 1<<16)
283 for i := 0; i < len(data); i++ {
284 data[i] = i ^ 0xcccc
285 }
286 b.StartTimer()
287 Stable(IntSlice(data))
288 b.StopTimer()
289 }
290 }
291
292 const (
293 _Sawtooth = iota
294 _Rand
295 _Stagger
296 _Plateau
297 _Shuffle
298 _NDist
299 )
300
301 const (
302 _Copy = iota
303 _Reverse
304 _ReverseFirstHalf
305 _ReverseSecondHalf
306 _Sorted
307 _Dither
308 _NMode
309 )
310
311 type testingData struct {
312 desc string
313 t *testing.T
314 data []int
315 maxswap int
316 ncmp, nswap int
317 }
318
319 func (d *testingData) Len() int { return len(d.data) }
320 func (d *testingData) Less(i, j int) bool {
321 d.ncmp++
322 return d.data[i] < d.data[j]
323 }
324 func (d *testingData) Swap(i, j int) {
325 if d.nswap >= d.maxswap {
326 d.t.Fatalf("%s: used %d swaps sorting slice of %d", d.desc, d.nswap, len(d.data))
327 }
328 d.nswap++
329 d.data[i], d.data[j] = d.data[j], d.data[i]
330 }
331
332 func min(a, b int) int {
333 if a < b {
334 return a
335 }
336 return b
337 }
338
339 func lg(n int) int {
340 i := 0
341 for 1<<uint(i) < n {
342 i++
343 }
344 return i
345 }
346
347 func testBentleyMcIlroy(t *testing.T, sort func(Interface), maxswap func(int) int) {
348 sizes := []int{100, 1023, 1024, 1025}
349 if testing.Short() {
350 sizes = []int{100, 127, 128, 129}
351 }
352 dists := []string{"sawtooth", "rand", "stagger", "plateau", "shuffle"}
353 modes := []string{"copy", "reverse", "reverse1", "reverse2", "sort", "dither"}
354 var tmp1, tmp2 [1025]int
355 for _, n := range sizes {
356 for m := 1; m < 2*n; m *= 2 {
357 for dist := 0; dist < _NDist; dist++ {
358 j := 0
359 k := 1
360 data := tmp1[0:n]
361 for i := 0; i < n; i++ {
362 switch dist {
363 case _Sawtooth:
364 data[i] = i % m
365 case _Rand:
366 data[i] = rand.Intn(m)
367 case _Stagger:
368 data[i] = (i*m + i) % n
369 case _Plateau:
370 data[i] = min(i, m)
371 case _Shuffle:
372 if rand.Intn(m) != 0 {
373 j += 2
374 data[i] = j
375 } else {
376 k += 2
377 data[i] = k
378 }
379 }
380 }
381
382 mdata := tmp2[0:n]
383 for mode := 0; mode < _NMode; mode++ {
384 switch mode {
385 case _Copy:
386 for i := 0; i < n; i++ {
387 mdata[i] = data[i]
388 }
389 case _Reverse:
390 for i := 0; i < n; i++ {
391 mdata[i] = data[n-i-1]
392 }
393 case _ReverseFirstHalf:
394 for i := 0; i < n/2; i++ {
395 mdata[i] = data[n/2-i-1]
396 }
397 for i := n / 2; i < n; i++ {
398 mdata[i] = data[i]
399 }
400 case _ReverseSecondHalf:
401 for i := 0; i < n/2; i++ {
402 mdata[i] = data[i]
403 }
404 for i := n / 2; i < n; i++ {
405 mdata[i] = data[n-(i-n/2)-1]
406 }
407 case _Sorted:
408 for i := 0; i < n; i++ {
409 mdata[i] = data[i]
410 }
411
412
413 Ints(mdata)
414 case _Dither:
415 for i := 0; i < n; i++ {
416 mdata[i] = data[i] + i%5
417 }
418 }
419
420 desc := fmt.Sprintf("n=%d m=%d dist=%s mode=%s", n, m, dists[dist], modes[mode])
421 d := &testingData{desc: desc, t: t, data: mdata[0:n], maxswap: maxswap(n)}
422 sort(d)
423
424
425
426
427
428
429
430
431
432
433
434 if !IntsAreSorted(mdata) {
435 t.Fatalf("%s: ints not sorted\n\t%v", desc, mdata)
436 }
437 }
438 }
439 }
440 }
441 }
442
443 func TestSortBM(t *testing.T) {
444 testBentleyMcIlroy(t, Sort, func(n int) int { return n * lg(n) * 12 / 10 })
445 }
446
447 func TestHeapsortBM(t *testing.T) {
448 testBentleyMcIlroy(t, Heapsort, func(n int) int { return n * lg(n) * 12 / 10 })
449 }
450
451 func TestStableBM(t *testing.T) {
452 testBentleyMcIlroy(t, Stable, func(n int) int { return n * lg(n) * lg(n) / 3 })
453 }
454
455
456
457 type adversaryTestingData struct {
458 t *testing.T
459 data []int
460 maxcmp int
461 ncmp int
462 nsolid int
463 candidate int
464 gas int
465 }
466
467 func (d *adversaryTestingData) Len() int { return len(d.data) }
468
469 func (d *adversaryTestingData) Less(i, j int) bool {
470 if d.ncmp >= d.maxcmp {
471 d.t.Fatalf("used %d comparisons sorting adversary data with size %d", d.ncmp, len(d.data))
472 }
473 d.ncmp++
474
475 if d.data[i] == d.gas && d.data[j] == d.gas {
476 if i == d.candidate {
477
478 d.data[i] = d.nsolid
479 d.nsolid++
480 } else {
481
482 d.data[j] = d.nsolid
483 d.nsolid++
484 }
485 }
486
487 if d.data[i] == d.gas {
488 d.candidate = i
489 } else if d.data[j] == d.gas {
490 d.candidate = j
491 }
492
493 return d.data[i] < d.data[j]
494 }
495
496 func (d *adversaryTestingData) Swap(i, j int) {
497 d.data[i], d.data[j] = d.data[j], d.data[i]
498 }
499
500 func newAdversaryTestingData(t *testing.T, size int, maxcmp int) *adversaryTestingData {
501 gas := size - 1
502 data := make([]int, size)
503 for i := 0; i < size; i++ {
504 data[i] = gas
505 }
506 return &adversaryTestingData{t: t, data: data, maxcmp: maxcmp, gas: gas}
507 }
508
509 func TestAdversary(t *testing.T) {
510 const size = 10000
511 maxcmp := size * lg(size) * 4
512 d := newAdversaryTestingData(t, size, maxcmp)
513 Sort(d)
514
515 for i, v := range d.data {
516 if v != i {
517 t.Fatalf("adversary data not fully sorted")
518 }
519 }
520 }
521
522 func TestStableInts(t *testing.T) {
523 data := ints
524 Stable(IntSlice(data[0:]))
525 if !IntsAreSorted(data[0:]) {
526 t.Errorf("nsorted %v\n got %v", ints, data)
527 }
528 }
529
530 type intPairs []struct {
531 a, b int
532 }
533
534
535 func (d intPairs) Len() int { return len(d) }
536 func (d intPairs) Less(i, j int) bool { return d[i].a < d[j].a }
537 func (d intPairs) Swap(i, j int) { d[i], d[j] = d[j], d[i] }
538
539
540 func (d intPairs) initB() {
541 for i := range d {
542 d[i].b = i
543 }
544 }
545
546
547 func (d intPairs) inOrder() bool {
548 lastA, lastB := -1, 0
549 for i := 0; i < len(d); i++ {
550 if lastA != d[i].a {
551 lastA = d[i].a
552 lastB = d[i].b
553 continue
554 }
555 if d[i].b <= lastB {
556 return false
557 }
558 lastB = d[i].b
559 }
560 return true
561 }
562
563 func TestStability(t *testing.T) {
564 n, m := 100000, 1000
565 if testing.Short() {
566 n, m = 1000, 100
567 }
568 data := make(intPairs, n)
569
570
571 for i := 0; i < len(data); i++ {
572 data[i].a = rand.Intn(m)
573 }
574 if IsSorted(data) {
575 t.Fatalf("terrible rand.rand")
576 }
577 data.initB()
578 Stable(data)
579 if !IsSorted(data) {
580 t.Errorf("Stable didn't sort %d ints", n)
581 }
582 if !data.inOrder() {
583 t.Errorf("Stable wasn't stable on %d ints", n)
584 }
585
586
587 data.initB()
588 Stable(data)
589 if !IsSorted(data) {
590 t.Errorf("Stable shuffled sorted %d ints (order)", n)
591 }
592 if !data.inOrder() {
593 t.Errorf("Stable shuffled sorted %d ints (stability)", n)
594 }
595
596
597 for i := 0; i < len(data); i++ {
598 data[i].a = len(data) - i
599 }
600 data.initB()
601 Stable(data)
602 if !IsSorted(data) {
603 t.Errorf("Stable didn't sort %d ints", n)
604 }
605 if !data.inOrder() {
606 t.Errorf("Stable wasn't stable on %d ints", n)
607 }
608 }
609
610 var countOpsSizes = []int{1e2, 3e2, 1e3, 3e3, 1e4, 3e4, 1e5, 3e5, 1e6}
611
612 func countOps(t *testing.T, algo func(Interface), name string) {
613 sizes := countOpsSizes
614 if testing.Short() {
615 sizes = sizes[:5]
616 }
617 if !testing.Verbose() {
618 t.Skip("Counting skipped as non-verbose mode.")
619 }
620 for _, n := range sizes {
621 td := testingData{
622 desc: name,
623 t: t,
624 data: make([]int, n),
625 maxswap: 1<<31 - 1,
626 }
627 for i := 0; i < n; i++ {
628 td.data[i] = rand.Intn(n / 5)
629 }
630 algo(&td)
631 t.Logf("%s %8d elements: %11d Swap, %10d Less", name, n, td.nswap, td.ncmp)
632 }
633 }
634
635 func TestCountStableOps(t *testing.T) { countOps(t, Stable, "Stable") }
636 func TestCountSortOps(t *testing.T) { countOps(t, Sort, "Sort ") }
637
638 func bench(b *testing.B, size int, algo func(Interface), name string) {
639 if stringspkg.HasSuffix(testenv.Builder(), "-race") && size > 1e4 {
640 b.Skip("skipping slow benchmark on race builder")
641 }
642 b.StopTimer()
643 data := make(intPairs, size)
644 x := ^uint32(0)
645 for i := 0; i < b.N; i++ {
646 for n := size - 3; n <= size+3; n++ {
647 for i := 0; i < len(data); i++ {
648 x += x
649 x ^= 1
650 if int32(x) < 0 {
651 x ^= 0x88888eef
652 }
653 data[i].a = int(x % uint32(n/5))
654 }
655 data.initB()
656 b.StartTimer()
657 algo(data)
658 b.StopTimer()
659 if !IsSorted(data) {
660 b.Errorf("%s did not sort %d ints", name, n)
661 }
662 if name == "Stable" && !data.inOrder() {
663 b.Errorf("%s unstable on %d ints", name, n)
664 }
665 }
666 }
667 }
668
669 func BenchmarkSort1e2(b *testing.B) { bench(b, 1e2, Sort, "Sort") }
670 func BenchmarkStable1e2(b *testing.B) { bench(b, 1e2, Stable, "Stable") }
671 func BenchmarkSort1e4(b *testing.B) { bench(b, 1e4, Sort, "Sort") }
672 func BenchmarkStable1e4(b *testing.B) { bench(b, 1e4, Stable, "Stable") }
673 func BenchmarkSort1e6(b *testing.B) { bench(b, 1e6, Sort, "Sort") }
674 func BenchmarkStable1e6(b *testing.B) { bench(b, 1e6, Stable, "Stable") }
675
View as plain text