前言
这是**icza**在 StackOverflow 上的一篇高赞回答，质量很高，翻译一下，大家一起学习
问题是：go 语言中，有没有什么最快最简单的方法，用来生成只包含英文字母的随机字符串
icza 给出了 8 个方案，最简单的方法并不是最快的方法，它们各有优劣，末尾附上性能测试结果：
1. Runes
比较简单的答案，声明一个 rune 数组，通过随机数选取 rune 字符，拼接成结果
package approach1
import ( "fmt" "math/rand" "testing" "time")
var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
func randStr(n int) string { b := make([]rune, n) for i := range b { b[i] = letters[rand.Intn(len(letters))] } return string(b)}
func TestApproach1(t *testing.T) { rand.Seed(time.Now().UnixNano()) fmt.Println(randStr(10))}
func BenchmarkApproach1(b *testing.B) { rand.Seed(time.Now().UnixNano()) for i := 0; i < b.N; i++ { _ = randStr(10) }}
复制代码
2. Bytes
如果随机挑选的字符只包含英文字母，我们可以直接使用 bytes，因为在 UTF-8 编码模式下，英文字符和 Bytes 是一对一的（Go 正是使用 UTF-8 模式编码）
所以可以把
var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
复制代码
用这个替代
var letters = []byte("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
复制代码
或者更好
const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
复制代码
现在我们有很大的进展了，我们把它变为了一个常数，在 go 里面，只有 string 常数，可并没有 slice 常数。额外的收获，表达式len(letters)也变为了一个常数（如果s为常数，那么len(s)也将是常数)
我们没有付出什么代码，现在letters可以通过下标访问其中的 bytes 了，这正是我们需要的。
package approach2
import ( "fmt" "math/rand" "testing" "time")
const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
func randStr(n int) string { b := make([]byte, n) for i := range b { b[i] = letters[rand.Intn(len(letters))] } return string(b)}
func TestApproach2(t *testing.T) { rand.Seed(time.Now().UnixNano())
fmt.Println(randStr(10))}
func BenchmarkApproach2(b *testing.B) { rand.Seed(time.Now().UnixNano()) for i := 0; i < b.N; i++ { _ = randStr(10) }}
复制代码
3. Remainder 余数
上面的解决方法通过rand.Intn()来获得一个随机字母，这个方法底层调用了Rand.Intn()，然后调用了Rand.Int31n()
相比于生成 63 个随机 bits 的函数rand.Int63()来说，Rand.Int31n()很慢。
我们可以简单地调用rand.Int63()然后除以len(letterBytes)，使用它的余数来生成字母
package approach3
import ( "fmt" "math/rand" "testing" "time")
const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
func randStr(n int) string { b := make([]byte, n) for i := range b { b[i] = letters[rand.Int63() % int64(len(letters))] } return string(b)}
func TestApproach3(t *testing.T) { rand.Seed(time.Now().UnixNano())
fmt.Println(randStr(10))}
func BenchmarkApproach3(b *testing.B) { rand.Seed(time.Now().UnixNano()) for i := 0; i < b.N; i++ { _ = randStr(10) }}
复制代码
这个算法能正常工作并且非常快，不过它牺牲了部分精确性，字母出现的概率并不是精确一样的（假设rand.Int63()生成 63 比特的数字是等概率的）。由于字母总共才 52 个，远小于 1<<63 - 1，因此失真非常小，因此实际上这完全没问题。
解释: 假设你想要 0~5 的随机数，如果使用 3 位的 bit，3 位的 bit 等概率出现 0~7，所以出现 0 和 1 的概率是出现 2、3、4 概率的两倍。使用 5 位的 bit，0 和 1 出现的概率是6/32，2、3、4 出现的概率是5/32。现在接近了一些了，是吧？不断地增加比特位，这个差距就会变得越小，当你有 63 位地时候，这差别已经可忽略不计。
4. Masking 掩码
在上一个方案的基础上，我们通过仅使用随机数的最低 n 位保持均匀分布，n 表示所有字符的数量。比如我们有 52 个字母，我们需要 6 位（52 = 110100b）。所以我们仅仅使用了rand.Int63()的最后 6 位。并且，为了保持所有字符的均匀分布，我们决定只接受在0..len(letterBytes)-1的数字即 0~51。（译者注：这里已经没有第三个方案的不准确问题了）
最低几位大于等于len(letterBytes)的概率一般小于0.5（平均值为 0.25），这意味着出现这种情况，只要重试就好。重试 n 次之后，我们仍然需要丢弃这个数字的概率远小于 0.5 的 n 次方（这是上界了，实际会低于这个值）。以本文的 52 个字母为例，最低 6 位需要丢弃的概率只有(64-52)/64=0.19。这意味着，重复 10 次，仍然没有数字的概率是 1*10^-8。
package approach4
import ( "fmt" "math/rand" "testing" "time")
const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
const ( // 6 bits to represent a letters index letterIdBits = 6 // All 1-bits as many as letterIdBits letterIdMask = 1 <<letterIdBits - 1)
func randStr(n int) string { b := make([]byte, n) for i := range b { if idx := int(rand.Int63() & letterIdMask); idx < len(letters) { b[i] = letters[idx] i++ } } return string(b)}
func TestApproach4(t *testing.T) { rand.Seed(time.Now().UnixNano())
fmt.Println(randStr(10))}
func BenchmarkApproach4(b *testing.B) { rand.Seed(time.Now().UnixNano()) for i := 0; i < b.N; i++ { _ = randStr(10) }}
复制代码
5. Masking Improved
第 4 节的方案只使用了rand.Int63()方法返回的 64 个随机字节的后 6 位。这实在是太浪费了，因为rand.Int63()是我们算法中最耗时的部分了。
如果我们有 52 个字母，6 位就能生成一个随机字符串。所以 63 个随机字节，可以利用63/6=10次。
译者注：使用了缓存，缓存了rand.Int63()方法返回的内容，使用 10 次，不过已经并不是协程安全的了。
package approach5
import ( "fmt" "math/rand" "testing" "time")
const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
const ( // 6 bits to represent a letter index letterIdBits = 6 // All 1-bits as many as letterIdBits letterIdMask = 1<<letterIdBits - 1 letterIdMax = 63 / letterIdBits)
func randStr(n int) string { b := make([]byte, n) // A rand.Int63() generates 63 random bits, enough for letterIdMax letters! for i, cache, remain := n-1, rand.Int63(), letterIdMax; i >= 0; { if remain == 0 { cache, remain = rand.Int63(), letterIdMax } if idx := int(cache & letterIdMask); idx < len(letters) { b[i] = letters[idx] i-- } cache >>= letterIdBits remain-- } return string(b)}
func TestApproach5(t *testing.T) { rand.Seed(time.Now().UnixNano())
fmt.Println(randStr(10))}
func BenchmarkApproach5(b *testing.B) { rand.Seed(time.Now().UnixNano()) for i := 0; i < b.N; i++ { _ = randStr(10) }}
复制代码
6. Source
第 5 个方案非常好，能改进的点并不多。我们可以但不值得搞得很复杂。
让我们来找可以改进的点：随机数的生成源
crypto/rand的包提供了Read(b []byte)的函数，可以通过这个函数获得需要的随机比特数，只需要一次调用。不过并不能提升性能，因为crypto/rand实现了一个密码学上的安全伪随机数，所以速度比较慢。
所以让我们坚持使用math/rand包，rand.Rand使用rand.Source作为随机位的来源，rand.Source是一个声明了Int63() int64的接口：正是我们在最新解决方案中需要和使用的唯一方法。
所以我们不是真的需要rand.Rand，rand.Source包对于我们来说已经足够了
package approach6
import ( "fmt" "math/rand" "testing" "time")
const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
var src = rand.NewSource(time.Now().UnixNano())
const ( // 6 bits to represent a letter index letterIdBits = 6 // All 1-bits as many as letterIdBits letterIdMask = 1<<letterIdBits - 1 letterIdMax = 63 / letterIdBits)
func randStr(n int) string { b := make([]byte, n) // A rand.Int63() generates 63 random bits, enough for letterIdMax letters! for i, cache, remain := n-1, src.Int63(), letterIdMax; i >= 0; { if remain == 0 { cache, remain = src.Int63(), letterIdMax } if idx := int(cache & letterIdMask); idx < len(letters) { b[i] = letters[idx] i-- } cache >>= letterIdBits remain-- } return string(b)}
func TestApproach6(t *testing.T) { fmt.Println(randStr(10))}
func BenchmarkApproach6(b *testing.B) { for i := 0; i < b.N; i++ { _ = randStr(10) }}
复制代码
注意到这里我们没有使用种子初始化 rand 了，取而代之的是初始化了rand.Source
还有一件需要注意的事，math/rand的文档指出
所以默认的 Source 比通过rand.NewSource()创建出来的Source要慢。不用处理协程并发场景，当然慢啦。
7. 使用 strings.Builder
之前的解决方案都返回了通过 slice 构造的字符串。最后的一次转换进行了一次拷贝，因为字符串是不可变的，如果转换的时候不进行拷贝，就无法保证转换完成之后，byte slice 再被修改后，字符串仍能保持不变。
Go1.10 引入了 strings.Builder，这是一个新的类型，和 bytes.Buffer 类似，用来构造字符串。底层使用[]byte来构造内容，正是我们现在在做的，最后可以通过Builder.String()方法来获得最终的字符串值。但它很酷的地方在于，它无需执行刚才谈到的复制即可完成此操作。它敢这么做是因为它底层构造的[]byte从未暴露出来，所以仍然可以保证没有人可以无意地、恶意地来修改已经生成的不可变字符串。
所以我们的下一个想法不是在 slice 中构建随机字符串，而是使用 strings.Builder，结束 building 后，我们就可以获取并返回结果，而无需复制。 这可能在速度方面有所帮助，并且在内存使用和分配方面肯定会有所帮助（译者注：等会在 benchmark 中会清晰地看到）。
package approach7
import ( "fmt" "math/rand" "strings" "testing" "time")
const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
var src = rand.NewSource(time.Now().UnixNano())
const ( // 6 bits to represent a letter index letterIdBits = 6 // All 1-bits as many as letterIdBits letterIdMask = 1<<letterIdBits - 1 letterIdMax = 63 / letterIdBits)
func randStr(n int) string { sb := strings.Builder{} sb.Grow(n) // A rand.Int63() generates 63 random bits, enough for letterIdMax letters! for i, cache, remain := n-1, src.Int63(), letterIdMax; i >= 0; { if remain == 0 { cache, remain = src.Int63(), letterIdMax } if idx := int(cache & letterIdMask); idx < len(letters) { sb.WriteByte(letters[idx]) i-- } cache >>= letterIdBits remain-- } return sb.String()}
func TestApproach7(t *testing.T) { fmt.Println(randStr(10))}
func BenchmarkApproach7(b *testing.B) { for i := 0; i < b.N; i++ { _ = randStr(10) }}
复制代码
在构造出 builder 之后，我们立刻调用了Builder.Grow()方法，使得它分配一个足够大的底层 slice,避免在后续操作中再进行分配
8. "Mimicing" strings.Builder with package unsafe
模仿 string.Builder 使用 unsafe 包
string.Builder 跟我们第六节地解法一样，都是用[]byte来构建字符串。切换到 strings.Builder 可能有一些太重了，我们使用 strings.Builder 只是想避免拷贝 slice。
string.Builder 使用unsafe包来避免最终的拷贝
// String returns the accumulated string.func (b *Builder) String() string { return *(*string)(unsafe.Pointer(&b.buf))}
复制代码
我们也可以自己完成这个流程。所以思路是我们通过unsafe包来返回一个字符串，来避免拷贝
package approach8
import ( "fmt" "math/rand" "testing" "time" "unsafe")
const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
var src = rand.NewSource(time.Now().UnixNano())
const ( // 6 bits to represent a letter index letterIdBits = 6 // All 1-bits as many as letterIdBits letterIdMask = 1<<letterIdBits - 1 letterIdMax = 63 / letterIdBits)
func randStr(n int) string { b := make([]byte, n) // A rand.Int63() generates 63 random bits, enough for letterIdMax letters! for i, cache, remain := n-1, src.Int63(), letterIdMax; i >= 0; { if remain == 0 { cache, remain = src.Int63(), letterIdMax } if idx := int(cache & letterIdMask); idx < len(letters) { b[i] = letters[idx] i-- } cache >>= letterIdBits remain-- } return *(*string)(unsafe.Pointer(&b))}
func TestApproach8(t *testing.T) { fmt.Println(randStr(10))}
func BenchmarkApproach8(b *testing.B) { for i := 0; i < b.N; i++ { _ = randStr(10) }}
复制代码
Benchmark
go test ./... -bench=. -benchmem
复制代码
原作者测试的数据
(译者注：第三列代表操作一次需要多少纳秒)
BenchmarkRunes-4 2000000 723 ns/op 96 B/op 2 allocs/opBenchmarkBytes-4 3000000 550 ns/op 32 B/op 2 allocs/opBenchmarkBytesRmndr-4 3000000 438 ns/op 32 B/op 2 allocs/opBenchmarkBytesMask-4 3000000 534 ns/op 32 B/op 2 allocs/opBenchmarkBytesMaskImpr-4 10000000 176 ns/op 32 B/op 2 allocs/opBenchmarkBytesMaskImprSrc-4 10000000 139 ns/op 32 B/op 2 allocs/opBenchmarkBytesMaskImprSrcSB-4 10000000 134 ns/op 16 B/op 1 allocs/opBenchmarkBytesMaskImprSrcUnsafe-4 10000000 115 ns/op 16 B/op 1 allocs/op
复制代码
译者测试的数据
BenchmarkApproach1-12 3849038 299.5 ns/op 64 B/op 2 allocs/opBenchmarkApproach2-12 5545350 216.4 ns/op 32 B/op 2 allocs/opBenchmarkApproach3-12 7003654 169.7 ns/op 32 B/op 2 allocs/opBenchmarkApproach4-12 7164259 168.7 ns/op 32 B/op 2 allocs/opBenchmarkApproach5-12 13205474 89.06 ns/op 32 B/op 2 allocs/opBenchmarkApproach6-12 13665636 84.41 ns/op 32 B/op 2 allocs/opBenchmarkApproach7-12 17213431 70.37 ns/op 16 B/op 1 allocs/opBenchmarkApproach8-12 19756956 61.41 ns/op 16 B/op 1 allocs/op
复制代码
现在跑出来的数据，相原作者时候，已经有了一些变化，不过并不妨碍我们看出来各个方法的趋势：
仅仅只是把 rune 切换到 byte，就获得了性能的大幅度提升(大于百分之 20)
使用rand.Int63()代替rand.Intn()也获得大幅度提升(大于百分之 20)
使用 Masking 并没有提升性能，相反在原作者哪里，反而性能下降了
不过使用了一次rand.Int63()返回的全部字符后，性能提升了 3 倍
使用rand.Source替代rand.Rand，性能提升了 21%
使用strings.Builder，我们在速度上提升了 3.5%，并且把原本 2 次的内存分配，降低到了一次！
使用unsafe包来代替strings.Builder，性能提升了 14%
将第八个方案和第一个方案比较，第八个方案比第一个方案快 6.3 倍，仅仅使用六分之一的内存，分配次数也只有原来的一半。
评论