Skip to content

Commit d9a198c

Browse files
rscrsc
committed
Revert "math/rand: make Perm match Shuffle"
This reverts CL 55972. Reason for revert: this changes Perm's behavior unnecessarily. I asked for this change originally but I now regret it. Reverting so that I don't have to justify it in Go 1.10 release notes. Edited to keep the change to rand_test.go, which seems to have been mostly unrelated. Fixes golang#22744. Change-Id: If8bb1bcde3ced0db2fdcd0aa65ab128613686c66 Reviewed-on: https://go-review.googlesource.com/78195 Run-TryBot: Russ Cox <[email protected]> Reviewed-by: Emmanuel Odeke <[email protected]> Reviewed-by: Rob Pike <[email protected]> Reviewed-by: Joe Tsai <[email protected]> Reviewed-by: Ian Lance Taylor <[email protected]>
1 parent 02298ae commit d9a198c

3 files changed

Lines changed: 27 additions & 35 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 [0 1 4 2 3] [0 4 3 1 2] [1 2 3 0 4]
97+
// Perm [1 4 2 3 0] [4 2 1 3 0] [1 2 4 0 3]
9898
}
9999

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

117117
// Output:
118-
// [my of the mouth corners from ink runs]
118+
// [mouth my the of runs corners from ink]
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
135137
// E: 5
136138
// B: 2
137-
// A: 1
138-
// D: 4
139139
}

‎src/math/rand/rand.go‎

Lines changed: 9 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -213,24 +213,16 @@ 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-
for i := range m {
217-
m[i] = i
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
218225
}
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-
234226
return m
235227
}
236228

‎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{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)
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)
331331
[]int{}, // Perm(0)
332332
[]int{0}, // Perm(1)
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)
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)
338338
[]int{}, // Perm(0)
339339
[]int{0}, // Perm(1)
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)
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)
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)