[toc]
我们应用中的随机数
- 抽奖，大转盘
- 我们经常接触的验证码
- 密码找回
- go中select的公平保证
- 再然后https通信中的秘钥生成
- 还有游戏中爆装备的概率等
你以为的随机是真的随机吗
如果我们试着在程序开始的生成一个随机数，你会发现每次都是一样的。
我们可以准确的判断出随机数是什么。
所以这也就是我们经常说的伪随机数。
那有没有真正的随机数呢，比如我们可以再一开始生成一个seed，然后再去生成随机数，这样每次都不一样了，但是这样就是真正的随机了吗。举一个极端的例子，你用随机数生成密码，种子是时间戳，而我恰好知道了你程序开始的时间，那么我就可以得到你的密码序列。
那再进一步呢，还没有别的办法，有的。我们可以根据周边物理条件来生成随机数。比如温度或者声音的变化，用户是键盘和鼠标输入等。 目前这些已经集成在部分硬件上了。
对应到我们go中呢，真随机是 crypto/rand，伪随机是math/rand，虽然真随机更好，但是我们不是需要再任何地方都用真随机的。因为有的时候安全并不重要，其次真随机性能会差很多。
// 伪随机
func Prng() int64 {
return rand.Int63()
}
//真随机
func SecureRng() int64 {
v, _ := srand.Int(srand.Reader, big.NewInt(math.MaxInt64))
return v.Int64()
}
进行性能测试如下
➜ rand go test -run=none -bench=BenchmarkRng -count=10
goos: darwin
goarch: amd64
pkg: lucas/code/rand
BenchmarkRng/PRNG-8 79132172 14.7 ns/op
BenchmarkRng/PRNG-8 81666558 14.8 ns/op
BenchmarkRng/PRNG-8 72479173 14.8 ns/op
BenchmarkRng/PRNG-8 79032494 14.8 ns/op
BenchmarkRng/PRNG-8 75016249 15.0 ns/op
BenchmarkRng/PRNG-8 77717745 14.9 ns/op
BenchmarkRng/PRNG-8 80101124 14.8 ns/op
BenchmarkRng/PRNG-8 76762986 14.8 ns/op
BenchmarkRng/PRNG-8 77451264 14.7 ns/op
BenchmarkRng/PRNG-8 75431827 14.8 ns/op
BenchmarkRng/SRNG-8 6292308 179 ns/op
BenchmarkRng/SRNG-8 6467247 178 ns/op
BenchmarkRng/SRNG-8 6467979 178 ns/op
BenchmarkRng/SRNG-8 6464542 178 ns/op
BenchmarkRng/SRNG-8 6239452 179 ns/op
BenchmarkRng/SRNG-8 6433585 177 ns/op
BenchmarkRng/SRNG-8 6494451 178 ns/op
BenchmarkRng/SRNG-8 6401463 179 ns/op
BenchmarkRng/SRNG-8 6466090 179 ns/op
BenchmarkRng/SRNG-8 6501558 178 ns/op
可见差了1个量级。所以我们应该有个这样的结论就是随机数用我们最合适的。
随机数怎么生成的呢
<img src="http://picgo.vipkk.work/20200517013900.png" alt="image-20200517013900312" style="zoom:50%;" />
简单来说就是我们维护了一个随机数表，然后每次调用从表里取一个进行生成，然后用生成的值更新表里的值。
具体的算法
-
线性同余法（c和java内部是这样实现的）
<img src="http://picgo.vipkk.work/20200517014210.png" alt="image-20200517014210305" style="zoom:50%;" />
-
go的实现（继承于plan9,也没有具体的名称了）
src/math/rand/rng.go/* * Uniform distribution * * algorithm by * DP Mitchell and JA Reeds */
一个细节
无论是go还是c实现上我们都需要更新内部状态，这也就是说rand生成是加锁的。
具体案例分析
-
公平的select
channel 之间的选择
-
shuffle算法
如何保证公平
-
-
[生成一个字符串][1]
➜ go test -run=none -bench=BenchmarkRandStr -benchmem goos: darwin goarch: amd64 pkg: lucas/code/rand BenchmarkRandStr/str1-8 504416 2230 ns/op 224 B/op 2 allocs/op BenchmarkRandStr/str2-8 587556 1946 ns/op 224 B/op 2 allocs/op BenchmarkRandStr/str3-8 1996708 583 ns/op 224 B/op 2 allocs/op BenchmarkRandStr/str4-8 1859163 690 ns/op 112 B/op 1 allocs/op BenchmarkRandStr/str5-8 2001969 560 ns/op 112 B/op 1 allocs/op PASS ok lucas/code/rand 9.819simage-20200517022405429- 合适的function
- 结合实际的mask
- 内存减少
随机数的定义
- 随机性
- 不可预测性
- 不可重现性
这三个是依次递进的，
<img src="http://picgo.vipkk.work/20200517002229.png" alt="image-20200517002229634" style="zoom:50%;" />
参考资料
https://stackoverflow.com/questions/22892120/how-to-generate-a-random-string-of-a-fixed-length-in-go
-
shuffle算法
// Shuffle pseudo-randomizes the order of elements. // n is the number of elements. Shuffle panics if n < 0. // swap swaps the elements with indexes i and j. func (r *Rand) Shuffle(n int, swap func(i, j int)) { if n < 0 { panic("invalid argument to Shuffle") } // Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle // Shuffle really ought not be called with n that doesn't fit in 32 bits. // Not only will it take a very long time, but with 2³¹! possible permutations, // there's no way that any PRNG can have a big enough internal state to // generate even a minuscule percentage of the possible permutations. // Nevertheless, the right API signature accepts an int n, so handle it as best we can. i := n - 1 for ; i > 1<<31-1-1; i-- { j := int(r.Int63n(int64(i + 1))) swap(i, j) } for ; i > 0; i-- { j := int(r.int31n(int32(i + 1))) swap(i, j) } }
如何评价一个随机数算法的优劣
TODO
C#
<img src="http://picgo.vipkk.work/20200518133248.jpg" alt="img" style="zoom:100%;" />
PHP
GO
Other
- int64n 与 int64 %n 效果是不一样的
