Skip to content

Commit caae091

Browse files
josharianianlancetaylor
josharian
authored and
ianlancetaylor
committed
math/rand: make Perm match Shuffle
Perm and Shuffle are fundamentally doing the same work. This change makes Perm's algorithm match Shuffle's. In addition to allowing developers to switch more easily between the two methods, it affords a nice speed-up: name old time/op new time/op delta Perm3-8 75.7ns ± 1% 51.8ns ± 1% -31.59% (p=0.000 n=9+8) Perm30-8 610ns ± 1% 405ns ± 1% -33.67% (p=0.000 n=9+9) This change alters the output from Perm, given the same Source and seed. This is a change from Go 1.0 behavior. This necessitates updating the regression test. This also changes the number of calls made to the Source during Perm, which changes the output of the math/rand examples. This also slightly perturbs the output of Perm, nudging it out of the range currently accepted by TestUniformFactorial. However, it is complete unclear that the helpers relied on by TestUniformFactorial are correct. That is golang#21211. This change updates checkSimilarDistribution to respect closeEnough for standard deviations, which makes the test pass. The whole situation is muddy; see golang#21211 for details. There is an alternative implementation of Perm that avoids initializing m, which is more similar to the existing implementation, plus some optimizations: func (r *Rand) Perm(n int) []int { m := make([]int, n) max31 := n if n > 1<<31-1-1 { max31 = 1<<31 - 1 - 1 } i := 1 for ; i < max31; i++ { j := r.int31n(int32(i + 1)) m[i] = m[j] m[j] = i } for ; i < n; i++ { j := r.Int63n(int64(i + 1)) m[i] = m[j] m[j] = i } return m } This is a tiny bit faster than the implementation actually used in this change: name old time/op new time/op delta Perm3-8 51.8ns ± 1% 50.3ns ± 1% -2.83% (p=0.000 n=8+9) Perm30-8 405ns ± 1% 394ns ± 1% -2.66% (p=0.000 n=9+8) However, 3% in performance doesn't seem worth having the two algorithms diverge, nor the reduced readability of this alternative. Updates golang#16213. Change-Id: I11a7441ff8837ee9c241b4c88f7aa905348be781 Reviewed-on: https://go-review.googlesource.com/55972 Run-TryBot: Ian Lance Taylor <[email protected]> TryBot-Result: Gobot Gobot <[email protected]> Reviewed-by: Rob Pike <[email protected]>
1 parent a2dfe5d commit caae091

4 files changed

Lines changed: 36 additions & 28 deletions

File tree

‎src/math/rand/example_test.go‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -94,7 +94,7 @@ func Example_rand() {
9494
// Intn(10) 1 2 5
9595
// Int31n(10) 4 7 8
9696
// Int63n(10) 7 6 3
97-
// Perm [1 4 2 3 0] [4 2 1 3 0] [1 2 4 0 3]
97+
// Perm [0 1 4 2 3] [0 4 3 1 2] [1 2 3 0 4]
9898
}
9999

100100
func ExamplePerm() {
@@ -115,7 +115,7 @@ func ExampleShuffle() {
115115
fmt.Println(words)
116116

117117
// Output:
118-
// [mouth my the of runs corners from ink]
118+
// [my of the mouth corners from ink runs]
119119
}
120120

121121
func ExampleShuffle_slicesInUnison() {
@@ -132,8 +132,8 @@ func ExampleShuffle_slicesInUnison() {
132132

133133
// Output:
134134
// C: 3
135-
// D: 4
136-
// A: 1
137135
// E: 5
138136
// B: 2
137+
// A: 1
138+
// D: 4
139139
}

‎src/math/rand/rand.go‎

Lines changed: 17 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -213,16 +213,24 @@ again:
213213
// Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n).
214214
func (r *Rand) Perm(n int) []int {
215215
m := make([]int, n)
216-
// In the following loop, the iteration when i=0 always swaps m[0] with m[0].
217-
// A change to remove this useless iteration is to assign 1 to i in the init
218-
// statement. But Perm also effects r. Making this change will affect
219-
// the final state of r. So this change can't be made for compatibility
220-
// reasons for Go 1.
221-
for i := 0; i < n; i++ {
222-
j := r.Intn(i + 1)
223-
m[i] = m[j]
224-
m[j] = i
216+
for i := range m {
217+
m[i] = i
225218
}
219+
220+
// The code that follows is equivalent to calling
221+
// r.Shuffle(n, func(i, j int) { m[i], m[j] = m[j], m[i] })
222+
// but with the swap function inlined.
223+
// This inlining provides a 10-15% speed-up.
224+
i := n - 1
225+
for ; i > 1<<31-1-1; i-- {
226+
j := int(r.Int63n(int64(i + 1)))
227+
m[i], m[j] = m[j], m[i]
228+
}
229+
for ; i > 0; i-- {
230+
j := int(r.int31n(int32(i + 1)))
231+
m[i], m[j] = m[j], m[i]
232+
}
233+
226234
return m
227235
}
228236

‎src/math/rand/rand_test.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -53,7 +53,7 @@ func (this *statsResults) checkSimilarDistribution(expected *statsResults) error
5353
fmt.Println(s)
5454
return errors.New(s)
5555
}
56-
if !nearEqual(this.stddev, expected.stddev, 0, expected.maxError) {
56+
if !nearEqual(this.stddev, expected.stddev, expected.closeEnough, expected.maxError) {
5757
s := fmt.Sprintf("stddev %v != %v (allowed error %v, %v)", this.stddev, expected.stddev, expected.closeEnough, expected.maxError)
5858
fmt.Println(s)
5959
return errors.New(s)

‎src/math/rand/regress_test.go‎

Lines changed: 14 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -323,24 +323,24 @@ var regressGolden = []interface{}{
323323
float64(-0.5987943422687668), // NormFloat64()
324324
[]int{}, // Perm(0)
325325
[]int{0}, // Perm(1)
326-
[]int{0, 4, 1, 3, 2}, // Perm(5)
327-
[]int{3, 1, 0, 4, 7, 5, 2, 6}, // Perm(8)
328-
[]int{5, 0, 3, 6, 7, 4, 2, 1, 8}, // Perm(9)
329-
[]int{4, 5, 0, 2, 6, 9, 3, 1, 8, 7}, // Perm(10)
330-
[]int{14, 2, 0, 8, 3, 5, 13, 12, 1, 4, 6, 7, 11, 9, 15, 10}, // Perm(16)
326+
[]int{2, 3, 1, 0, 4}, // Perm(5)
327+
[]int{5, 6, 0, 4, 3, 1, 7, 2}, // Perm(8)
328+
[]int{2, 4, 0, 5, 7, 3, 1, 6, 8}, // Perm(9)
329+
[]int{6, 0, 4, 2, 5, 1, 9, 8, 3, 7}, // Perm(10)
330+
[]int{7, 11, 12, 14, 0, 15, 2, 5, 9, 3, 8, 13, 4, 1, 6, 10}, // Perm(16)
331331
[]int{}, // Perm(0)
332332
[]int{0}, // Perm(1)
333-
[]int{3, 0, 1, 2, 4}, // Perm(5)
334-
[]int{5, 1, 2, 0, 4, 7, 3, 6}, // Perm(8)
335-
[]int{4, 0, 6, 8, 1, 5, 2, 7, 3}, // Perm(9)
336-
[]int{8, 6, 1, 7, 5, 4, 3, 2, 9, 0}, // Perm(10)
337-
[]int{0, 3, 13, 2, 15, 4, 10, 1, 8, 14, 7, 6, 12, 9, 5, 11}, // Perm(16)
333+
[]int{2, 1, 0, 4, 3}, // Perm(5)
334+
[]int{4, 2, 1, 6, 0, 5, 3, 7}, // Perm(8)
335+
[]int{7, 3, 1, 2, 8, 5, 4, 6, 0}, // Perm(9)
336+
[]int{3, 0, 7, 4, 8, 9, 5, 6, 1, 2}, // Perm(10)
337+
[]int{0, 1, 8, 14, 9, 5, 4, 13, 7, 12, 10, 3, 15, 6, 11, 2}, // Perm(16)
338338
[]int{}, // Perm(0)
339339
[]int{0}, // Perm(1)
340-
[]int{0, 4, 2, 1, 3}, // Perm(5)
341-
[]int{2, 1, 7, 0, 6, 3, 4, 5}, // Perm(8)
342-
[]int{8, 7, 5, 3, 4, 6, 0, 1, 2}, // Perm(9)
343-
[]int{1, 0, 2, 5, 7, 6, 9, 8, 3, 4}, // Perm(10)
340+
[]int{2, 1, 4, 3, 0}, // Perm(5)
341+
[]int{4, 0, 7, 5, 1, 6, 2, 3}, // Perm(8)
342+
[]int{6, 5, 3, 4, 7, 1, 0, 8, 2}, // Perm(9)
343+
[]int{1, 7, 6, 3, 2, 9, 0, 5, 4, 8}, // Perm(10)
344344
[]byte{0x1}, // Read([0])
345345
[]byte{0x94, 0xfd, 0xc2, 0xfa, 0x2f, 0xfc, 0xc0}, // Read([0 0 0 0 0 0 0])
346346
[]byte{0x41, 0xd3, 0xff, 0x12, 0x4, 0x5b, 0x73, 0xc8}, // Read([0 0 0 0 0 0 0 0])

0 commit comments

Comments
 (0)