8种超简单的Golang生成随机字符串方式
本文分享自华为云社区《Golang生成随机字符串的八种方式与性能测试》,作者: 张俭。
前言
这是**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是协程安全的
所以默认的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/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
译者测试的数据
BenchmarkApproach1-12 3849038 299.5 ns/op 64 B/op 2 allocs/op BenchmarkApproach2-12 5545350 216.4 ns/op 32 B/op 2 allocs/op BenchmarkApproach3-12 7003654 169.7 ns/op 32 B/op 2 allocs/op BenchmarkApproach4-12 7164259 168.7 ns/op 32 B/op 2 allocs/op BenchmarkApproach5-12 13205474 89.06 ns/op 32 B/op 2 allocs/op BenchmarkApproach6-12 13665636 84.41 ns/op 32 B/op 2 allocs/op BenchmarkApproach7-12 17213431 70.37 ns/op 16 B/op 1 allocs/op BenchmarkApproach8-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倍,仅仅使用六分之一的内存,分配次数也只有原来的一半。