Source file src/sort/sort_test.go

     1  // Copyright 2009 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     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  	// Ensure that sort.Sort does not panic when Less returns inconsistent results.
   146  	// See https://golang.org/issue/14377.
   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 // number of swaps allowed
   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  						// Ints is known to be correct
   412  						// because mode Sort runs after mode _Copy.
   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  					// Uncomment if you are trying to improve the number of compares/swaps.
   424  					//t.Logf("%s: ncmp=%d, nswp=%d", desc, d.ncmp, d.nswap)
   425  
   426  					// If we were testing C qsort, we'd have to make a copy
   427  					// of the slice and sort it ourselves and then compare
   428  					// x against it, to ensure that qsort was only permuting
   429  					// the data, not (for example) overwriting it with zeros.
   430  					//
   431  					// In go, we don't have to be so paranoid: since the only
   432  					// mutating method Sort can call is TestingData.swap,
   433  					// it suffices here just to check that the final slice is sorted.
   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  // This is based on the "antiquicksort" implementation by M. Douglas McIlroy.
   456  // See https://www.cs.dartmouth.edu/~doug/mdmspe.pdf for more info.
   457  type adversaryTestingData struct {
   458  	t         *testing.T
   459  	data      []int // item values, initialized to special gas value and changed by Less
   460  	maxcmp    int   // number of comparisons allowed
   461  	ncmp      int   // number of comparisons (calls to Less)
   462  	nsolid    int   // number of elements that have been set to non-gas values
   463  	candidate int   // guess at current pivot
   464  	gas       int   // special value for unset elements, higher than everything else
   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  			// freeze i
   478  			d.data[i] = d.nsolid
   479  			d.nsolid++
   480  		} else {
   481  			// freeze j
   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            // large enough to distinguish between O(n^2) and O(n*log(n))
   511  	maxcmp := size * lg(size) * 4 // the factor 4 was found by trial and error
   512  	d := newAdversaryTestingData(t, size, maxcmp)
   513  	Sort(d) // This should degenerate to heapsort.
   514  	// Check data is fully populated and sorted.
   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  // IntPairs compare on a only.
   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  // Record initial order in B.
   540  func (d intPairs) initB() {
   541  	for i := range d {
   542  		d[i].b = i
   543  	}
   544  }
   545  
   546  // InOrder checks if a-equal elements were not reordered.
   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  	// random distribution
   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  	// already sorted
   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  	// sorted reversed
   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