• Josh Bleecher Snyder's avatar
    math/rand: make Perm match Shuffle · caae0917
    Josh Bleecher Snyder authored
    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 #21211.
    This change updates checkSimilarDistribution to respect
    closeEnough for standard deviations, which makes the test pass.
    The whole situation is muddy; see #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 #16213.
    
    Change-Id: I11a7441ff8837ee9c241b4c88f7aa905348be781
    Reviewed-on: https://go-review.googlesource.com/55972
    Run-TryBot: Ian Lance Taylor <iant@golang.org>
    TryBot-Result: Gobot Gobot <gobot@golang.org>
    Reviewed-by: 's avatarRob Pike <r@golang.org>
    caae0917
regress_test.go 18.5 KB