LEFT | RIGHT |
(no file at all) | |
1 // Copyright 2009 The Go Authors. All rights reserved. | 1 // Copyright 2009 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 package sort | 5 package sort |
6 | 6 |
7 import ( | 7 import ( |
8 "fmt" | 8 "fmt" |
9 "rand" | 9 "rand" |
10 "strconv" | 10 "strconv" |
(...skipping 28 matching lines...) Expand all Loading... |
39 func TestSortStringSlice(t *testing.T) { | 39 func TestSortStringSlice(t *testing.T) { |
40 data := strings | 40 data := strings |
41 a := StringSlice(data[0:]) | 41 a := StringSlice(data[0:]) |
42 Sort(a) | 42 Sort(a) |
43 if !IsSorted(a) { | 43 if !IsSorted(a) { |
44 t.Errorf("sorted %v", strings) | 44 t.Errorf("sorted %v", strings) |
45 t.Errorf(" got %v", data) | 45 t.Errorf(" got %v", data) |
46 } | 46 } |
47 } | 47 } |
48 | 48 |
49 func TestSortInts(t *testing.T) { | 49 func TestInts(t *testing.T) { |
50 data := ints | 50 data := ints |
51 » SortInts(data[0:]) | 51 » Ints(data[0:]) |
52 if !IntsAreSorted(data[0:]) { | 52 if !IntsAreSorted(data[0:]) { |
53 t.Errorf("sorted %v", ints) | 53 t.Errorf("sorted %v", ints) |
54 t.Errorf(" got %v", data) | 54 t.Errorf(" got %v", data) |
55 } | 55 } |
56 } | 56 } |
57 | 57 |
58 func TestSortFloat64s(t *testing.T) { | 58 func TestFloat64s(t *testing.T) { |
59 data := float64s | 59 data := float64s |
60 » SortFloat64s(data[0:]) | 60 » Float64s(data[0:]) |
61 if !Float64sAreSorted(data[0:]) { | 61 if !Float64sAreSorted(data[0:]) { |
62 t.Errorf("sorted %v", float64s) | 62 t.Errorf("sorted %v", float64s) |
63 t.Errorf(" got %v", data) | 63 t.Errorf(" got %v", data) |
64 } | 64 } |
65 } | 65 } |
66 | 66 |
67 func TestSortStrings(t *testing.T) { | 67 func TestStrings(t *testing.T) { |
68 data := strings | 68 data := strings |
69 » SortStrings(data[0:]) | 69 » Strings(data[0:]) |
70 if !StringsAreSorted(data[0:]) { | 70 if !StringsAreSorted(data[0:]) { |
71 t.Errorf("sorted %v", strings) | 71 t.Errorf("sorted %v", strings) |
72 t.Errorf(" got %v", data) | 72 t.Errorf(" got %v", data) |
73 } | 73 } |
74 } | 74 } |
75 | 75 |
76 func TestSortLarge_Random(t *testing.T) { | 76 func TestSortLarge_Random(t *testing.T) { |
77 n := 1000000 | 77 n := 1000000 |
78 if testing.Short() { | 78 if testing.Short() { |
79 n /= 100 | 79 n /= 100 |
80 } | 80 } |
81 data := make([]int, n) | 81 data := make([]int, n) |
82 for i := 0; i < len(data); i++ { | 82 for i := 0; i < len(data); i++ { |
83 data[i] = rand.Intn(100) | 83 data[i] = rand.Intn(100) |
84 } | 84 } |
85 if IntsAreSorted(data) { | 85 if IntsAreSorted(data) { |
86 t.Fatalf("terrible rand.rand") | 86 t.Fatalf("terrible rand.rand") |
87 } | 87 } |
88 » SortInts(data) | 88 » Ints(data) |
89 if !IntsAreSorted(data) { | 89 if !IntsAreSorted(data) { |
90 t.Errorf("sort didn't sort - 1M ints") | 90 t.Errorf("sort didn't sort - 1M ints") |
91 } | 91 } |
92 } | 92 } |
93 | 93 |
94 func BenchmarkSortString1K(b *testing.B) { | 94 func BenchmarkSortString1K(b *testing.B) { |
95 b.StopTimer() | 95 b.StopTimer() |
96 for i := 0; i < b.N; i++ { | 96 for i := 0; i < b.N; i++ { |
97 data := make([]string, 1<<10) | 97 data := make([]string, 1<<10) |
98 for i := 0; i < len(data); i++ { | 98 for i := 0; i < len(data); i++ { |
99 data[i] = strconv.Itoa(i ^ 0x2cc) | 99 data[i] = strconv.Itoa(i ^ 0x2cc) |
100 } | 100 } |
101 b.StartTimer() | 101 b.StartTimer() |
102 » » SortStrings(data) | 102 » » Strings(data) |
103 b.StopTimer() | 103 b.StopTimer() |
104 } | 104 } |
105 } | 105 } |
106 | 106 |
107 func BenchmarkSortInt1K(b *testing.B) { | 107 func BenchmarkSortInt1K(b *testing.B) { |
108 b.StopTimer() | 108 b.StopTimer() |
109 for i := 0; i < b.N; i++ { | 109 for i := 0; i < b.N; i++ { |
110 data := make([]int, 1<<10) | 110 data := make([]int, 1<<10) |
111 for i := 0; i < len(data); i++ { | 111 for i := 0; i < len(data); i++ { |
112 data[i] = i ^ 0x2cc | 112 data[i] = i ^ 0x2cc |
113 } | 113 } |
114 b.StartTimer() | 114 b.StartTimer() |
115 » » SortInts(data) | 115 » » Ints(data) |
116 b.StopTimer() | 116 b.StopTimer() |
117 } | 117 } |
118 } | 118 } |
119 | 119 |
120 func BenchmarkSortInt64K(b *testing.B) { | 120 func BenchmarkSortInt64K(b *testing.B) { |
121 b.StopTimer() | 121 b.StopTimer() |
122 for i := 0; i < b.N; i++ { | 122 for i := 0; i < b.N; i++ { |
123 data := make([]int, 1<<16) | 123 data := make([]int, 1<<16) |
124 for i := 0; i < len(data); i++ { | 124 for i := 0; i < len(data); i++ { |
125 data[i] = i ^ 0xcccc | 125 data[i] = i ^ 0xcccc |
126 } | 126 } |
127 b.StartTimer() | 127 b.StartTimer() |
128 » » SortInts(data) | 128 » » Ints(data) |
129 b.StopTimer() | 129 b.StopTimer() |
130 } | 130 } |
131 } | 131 } |
132 | 132 |
133 const ( | 133 const ( |
134 _Sawtooth = iota | 134 _Sawtooth = iota |
135 _Rand | 135 _Rand |
136 _Stagger | 136 _Stagger |
137 _Plateau | 137 _Plateau |
138 _Shuffle | 138 _Shuffle |
(...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
234 for i := 0; i < n/2; i++ { | 234 for i := 0; i < n/2; i++ { |
235 mdata[i] = data[i] | 235 mdata[i] = data[i] |
236 } | 236 } |
237 for i := n / 2; i < n; i++ { | 237 for i := n / 2; i < n; i++ { |
238 mdata[i] = data[n-(i-n/2
)-1] | 238 mdata[i] = data[n-(i-n/2
)-1] |
239 } | 239 } |
240 case _Sorted: | 240 case _Sorted: |
241 for i := 0; i < n; i++ { | 241 for i := 0; i < n; i++ { |
242 mdata[i] = data[i] | 242 mdata[i] = data[i] |
243 } | 243 } |
244 » » » » » » // SortInts is known to be corre
ct | 244 » » » » » » // Ints is known to be correct |
245 // because mode Sort runs after
mode _Copy. | 245 // because mode Sort runs after
mode _Copy. |
246 » » » » » » SortInts(mdata) | 246 » » » » » » Ints(mdata) |
247 case _Dither: | 247 case _Dither: |
248 for i := 0; i < n; i++ { | 248 for i := 0; i < n; i++ { |
249 mdata[i] = data[i] + i%5 | 249 mdata[i] = data[i] + i%5 |
250 } | 250 } |
251 } | 251 } |
252 | 252 |
253 desc := fmt.Sprintf("n=%d m=%d dist=%s m
ode=%s", n, m, dists[dist], modes[mode]) | 253 desc := fmt.Sprintf("n=%d m=%d dist=%s m
ode=%s", n, m, dists[dist], modes[mode]) |
254 d := &testingData{desc, t, mdata[0:n], n
* lg(n) * 12 / 10, 0} | 254 d := &testingData{desc, t, mdata[0:n], n
* lg(n) * 12 / 10, 0} |
255 Sort(d) | 255 Sort(d) |
256 | 256 |
257 // If we were testing C qsort, we'd have
to make a copy | 257 // If we were testing C qsort, we'd have
to make a copy |
258 // of the slice and sort it ourselves an
d then compare | 258 // of the slice and sort it ourselves an
d then compare |
259 // x against it, to ensure that qsort wa
s only permuting | 259 // x against it, to ensure that qsort wa
s only permuting |
260 // the data, not (for example) overwriti
ng it with zeros. | 260 // the data, not (for example) overwriti
ng it with zeros. |
261 // | 261 // |
262 // In go, we don't have to be so paranoi
d: since the only | 262 // In go, we don't have to be so paranoi
d: since the only |
263 // mutating method Sort can call is Test
ingData.swap, | 263 // mutating method Sort can call is Test
ingData.swap, |
264 // it suffices here just to check that t
he final slice is sorted. | 264 // it suffices here just to check that t
he final slice is sorted. |
265 if !IntsAreSorted(mdata) { | 265 if !IntsAreSorted(mdata) { |
266 t.Errorf("%s: ints not sorted",
desc) | 266 t.Errorf("%s: ints not sorted",
desc) |
267 t.Errorf("\t%v", mdata) | 267 t.Errorf("\t%v", mdata) |
268 t.FailNow() | 268 t.FailNow() |
269 } | 269 } |
270 } | 270 } |
271 } | 271 } |
272 } | 272 } |
273 } | 273 } |
274 } | 274 } |
LEFT | RIGHT |