Golang 生成随机字符串的高级玩法！
Golang 生成随机字符串的高级玩法！
如题：用 Golang 生成随机字符串（大小写字母组成），最快、最简单的实现方式是怎样的？ 原文：How to generate a random string of a fixed length in Go?[1]
随机字符串嘛，rand就行了哦，这还不是信手拈来？
package main
import (
"fmt"
"time"
"math/rand"
)
var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
func randSeq(n int) string {
b := make([]rune, n)
for i := range b {
b[i] = letters[rand.Intn(len(letters))]
}
return string(b)
}
func main() {
rand.Seed(time.Now().UnixNano())
fmt.Println(randSeq(10))
}源码作者：Paul[2]
这个世界很简单，复杂的是人。总有那么一波人要搞个大新闻，他们玩的就是人群中的不一样！于是乎，就有了下面这位老哥的高赞回答。
I. Improvements
如果仅仅是生成随机字符串，最快的方案也可能不是首选的。就此而言，
Paul的实现是很完美的。但如果确实很看重性能的话，不显著提高复杂度的情况的前提下（只需前两步），我们还能把性能再提升 50%（参考压测）。
话虽如此，即便你不需要最快的实现方案，但读一读也是有教育意义的，挑战一下自己嘛（备好啤酒、花生米，让我们一起看看作者是如何一步步把我们逼到陆地神仙的 ^_^）。
1. Genesis(Runes)
先看看原始版本：
内心os：这才是简洁、易读的代码啊！ 但是，为了把这个逼装下去，同时也出于膜拜的心理（手动狗头），我还真仔细看看，且看他如何出招！！！
func init() {
rand.Seed(time.Now().UnixNano())
}
var letterRunes = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
func RandStringRunes(n int) string {
b := make([]rune, n)
for i := range b {
b[i] = letterRunes[rand.Intn(len(letterRunes))]
}
return string(b)
}2. Bytes
如果要生成的字符串只包括大小写字母的话，直接用 bytes 就行了。因为英文字母 UTF-8 编码映射到字节时是1对1的。
取而代之，直接用：
var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")或者，常量更好：
const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"现在已有较大改进了：const 取代 slice；另外，len(letters)也可以搞成常量。
因为，如果
s是一个字符串常量的话，len(s)也是一个常量。
经过一波改进后，代码长这样：
const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
func RandStringBytes(n int) string {
b := make([]byte, n)
for i := range b {
b[i] = letterBytes[rand.Intn(len(letterBytes))]
}
return string(b)
}3. Remainder
上一个版本是用 rand.Intn() 生成随机字符的，阅读源码可以知道 rand.Intn() 会降级为 rand.Int31n，最终再降级为 rand.Int63。
本着闹革命要彻底的原则，一步到位直接调用 rand.Int63：
func RandStringBytesRmndr(n int) string {
b := make([]byte, n)
for i := range b {
b[i] = letterBytes[rand.Int63() % int64(len(letterBytes))]
}
return string(b)
}本次改动在速度上提升很多，但也有缺点（这是一个严谨的数学问题 ^_^）：所有字母的生成概率是不完全相等的（假设 rand.Int63 生成的 63-bit 的数有相同概率）。尽管失真很小，毕竟 52 （字符数）相对于 1<<63 - 1 而言很小，因此在实践中是完全没有问题的。
便于理解：假设随机生成一个数，范围
[0,5]。 如果用 3-bits 随机生成，那么范围[0,1]内数字的概率会是[2,5]的 2 倍（因为实际生成的数字为[0,7]，一般地 会再对[6,7]取模变成[0, 1]）； 如果用 5-bits 随机生成，那么范围[0,1]内数字的概率是6/32，[2,5]的概率是5/32。相对来说，两部分的概率更接近一些了。 随着 bits 的增加，这种差异变变得更小，当达到 63-bits 时基本就可以忽略不计了。
4. Masking
基于前文，为保证字母的均匀分布，我们可以用最少的 bits 来表示要生成的随机数。例如，对于 52 个字母可以用 6-bits 表示：52 = 110110b，因此，只取 rand.Int63() 的最低 6-bits 即可。为保证满足均匀分布，我们只取落在范围 [0,len(letterBytes)-1] 内的数，如果数还是比较大就再随机一个新的。
话说，每次生成的随机数大于等于
len(letterBytes)的概率一般是小于0.5（平均为0.25）；在重复n次后，还没有找到合适数字的概率会比power(0.5,n)（这里只是一个上限）小很多。以 52 个字母为例（6-bits表示），未找到的概率仅有(64-52/64) = 0.19，意味着重复 10 次后几率会是1e-8。
实现如下：
const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
const (
letterIdxBits = 6 // 6 bits to represent a letter index
letterIdxMask = 1<<letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
)
func RandStringBytesMask(n int) string {
b := make([]byte, n)
for i := 0; i < n; {
if idx := int(rand.Int63() & letterIdxMask); idx < len(letterBytes) {
b[i] = letterBytes[idx]
i++
}
}
return string(b)
}5. Masking Improved
上一个版本只使用了rand.Int63() 返回的 63-bits 随机数中的最低 6-bits，这是一种极大的浪费，因为随机数是本算法中最费性能的部分了。
再进一步，63-bits 可以分为 63/6 = 10 部分，我们全都给他用上：
const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
const (
letterIdxBits = 6 // 6 bits to represent a letter index
letterIdxMask = 1<<letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
letterIdxMax = 63 / letterIdxBits // # of letter indices fitting in 63 bits
)
func RandStringBytesMaskImpr(n int) string {
b := make([]byte, n)
// A rand.Int63() generates 63 random bits, enough for letterIdxMax letters!
for i, cache, remain := n-1, rand.Int63(), letterIdxMax; i >= 0; {
if remain == 0 {
cache, remain = rand.Int63(), letterIdxMax
}
if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
b[i] = letterBytes[idx]
i--
}
cache >>= letterIdxBits
remain--
}
return string(b)
}6. Source
通过前面一波猛搞（Masking Improved），提升空间已经不多了。尽管有，也不值得去大费周章了。
但是，子曰：只要思想不滑坡，办法总比困难多。于是乎，我们换个方向，把目标转向了随机数生成部分。
crypto/rand包也能生成随机数，但是它更慢。回过头来，还是得搞一搞 math/rand包了。阅读源码可知在 rand.Rand内部包了个rand.Source，嘿嘿，花拳绣腿，要啥自行车，有rand.Source是够了呢：
var src = rand.NewSource(time.Now().UnixNano())
func RandStringBytesMaskImprSrc(n int) string {
b := make([]byte, n)
// A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
if remain == 0 {
cache, remain = src.Int63(), letterIdxMax
}
if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
b[i] = letterBytes[idx]
i--
}
cache >>= letterIdxBits
remain--
}
return string(b)
}
math/rand源码有云：The default Source is safe for concurrent use by multiple goroutines. 因此，直接用rand.NewSource可能会快那么一丢丢。
7. Utilizing strings.Builder
前面的所有方法都会先返回一个[]byte再强转为string。这个转换会创建 slice 内容的一个副本，因为string的内容是不可更改的。
How to convert utf8 string to byte?[3] golang: []byte(string) vs []byte(*string)[4]
相比 bytes.Buffer[5] 而言， strings.Builder[6] 是一个好的替代方案，最终 Builder.String()[7]转为string时就不必再做一次 copy 了（是不是很酷？）。
言归正传，strings.Builder 搞起！这样做有两个好处：
•不必再 make([]byte, n);•最后返回 string 时也省去了 copy 操作；
这样做会不仅在提速上会有提升，在内存使用、分配方面也有不小的改善：
func RandStringBytesMaskImprSrcSB(n int) string {
sb := strings.Builder{}
sb.Grow(n)
// A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
if remain == 0 {
cache, remain = src.Int63(), letterIdxMax
}
if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
sb.WriteByte(letterBytes[idx])
i--
}
cache >>= letterIdxBits
remain--
}
return sb.String()
}8. "Mimicing" strings.Builder with package unsafe
我们使用strings.Builder 的目的仅仅是为了避免 []byte 的 copy 操作，能否把 strings.Builder 这部分的开销也省了呢？先看核心逻辑：
// String returns the accumulated string.
func (b *Builder) String() string {
return *(*string)(unsafe.Pointer(&b.buf))
}原来如此，嘿嘿，这个我也能搞。话说从头，还是用[]byte，最终返回 string时做个 unsafe 转换：
func RandStringBytesMaskImprSrcUnsafe(n int) string {
b := make([]byte, n)
// A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
if remain == 0 {
cache, remain = src.Int63(), letterIdxMax
}
if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
b[i] = letterBytes[idx]
i--
}
cache >>= letterIdxBits
remain--
}
return *(*string)(unsafe.Pointer(&b))
}9. Using rand.Read()
Go 1.7[8] 新增了 rand.Read()[9] 方法，一次可以生成多个 bytes，是否可以提速呢？先说答案：不太行！
因为它的底层实现也是个循环（和 RandStringBytesMaskImprSrc 的做法是一样的）：
func read(p []byte, src Source, readVal *int64, readPos *int8) (n int, err error) {
pos := *readPos
val := *readVal
rng, _ := src.(*rngSource)
for n = 0; n < len(p); n++ {
if pos == 0 {
if rng != nil {
val = rng.Int63()
} else {
val = src.Int63()
}
pos = 7
}
p[n] = byte(val)
val >>= 8
pos--
}
*readPos = pos
*readVal = val
return
}没有了额外的 buffer 、没有了附加的复杂度，正是 RandStringBytesMaskImprSrc 能一马当先的原因。
II. Benchmark
下面是各种版本的压测数据：
BenchmarkRunes-4 2000000 723 ns/op 96 B/op 2 allocs/op
BenchmarkBytes-4 3000000 550 ns/op 32 B/op 2 allocs/op
BenchmarkBytesRmndr-4 3000000 438 ns/op 32 B/op 2 allocs/op
BenchmarkBytesMask-4 3000000 534 ns/op 32 B/op 2 allocs/op
BenchmarkBytesMaskImpr-4 10000000 176 ns/op 32 B/op 2 allocs/op
BenchmarkBytesMaskImprSrc-4 10000000 139 ns/op 32 B/op 2 allocs/op
BenchmarkBytesMaskImprSrcSB-4 10000000 134 ns/op 16 B/op 1 allocs/op
BenchmarkBytesMaskImprSrcUnsafe-4 10000000 115 ns/op 16 B/op 1 allocs/op•优化点 1：仅 bytes 替换 runes 这一个优化点，性能就提升了 24%，内存占用降为原来的 1/3•优化点 2：rand.Int63() 替换 rand.Intn() 又提升了20%•优化点 3：Masking 又倒回去了 -22%，主要是由于重复调用引起的（无效的循环）。•优化点 4：Masking Improved 使用 63-bits 拆分（1拆10）之后，成果斐然：速度又提升了3倍•优化点 5：rand.Source 替换 rand.Rand，提升 *21% *•优化点 6：使用 strings.Builder 虽然速度仅提升 3.5%，但是内存方面降了 50%•优化点 7：使用 unsafe 替换 strings.Builder,又提升了 21%
最终，RandStringBytesMaskImprSrcUnsafe比最初版本randstringgrunes快了 6.3倍。仅用了原 1/6 的内存和1/2的资源分配。
References
How to generate a random string of a fixed length in Go?[10]
References
[1] How to generate a random string of a fixed length in Go?: https://stackoverflow.com/questions/22892120/how-to-generate-a-random-string-of-a-fixed-length-in-go
[2] Paul: https://stackoverflow.com/questions/22892120/how-to-generate-a-random-string-of-a-fixed-length-in-go/22892986#22892986
[3] How to convert utf8 string to byte?: https://stackoverflow.com/questions/41460750/how-to-convert-utf8-string-to-byte/41460993#41460993
[4] golang: []byte(string) vs []byte(*string): https://stackoverflow.com/questions/43470284/golang-bytestring-vs-bytestring/43470344#43470344
[5] bytes.Buffer: https://golang.org/pkg/bytes/#Buffer
[6] strings.Builder: https://golang.org/pkg/strings/#Builder
[7] Builder.String(): https://golang.org/pkg/strings/#Builder.String
[8] Go 1.7: https://golang.org/doc/go1.7#math_rand
[9] rand.Read(): https://golang.org/pkg/math/rand/#Read
[10] How to generate a random string of a fixed length in Go?: https://stackoverflow.com/questions/22892120/how-to-generate-a-random-string-of-a-fixed-length-in-go