random string in golang
在学习golang的过程中，有注意到对于随机字符串的生成方式有很多种，下面就网上的罗列一下，最后一种是我最喜欢的方式，够优雅。
第一种 通用方案
最普通方案就是随机产生每个字符，所以整体字符串也是随机的。这样的好处是可以控制要使用的字符。
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] = letterRuens[rand.Intn(len(letterRunes))]
}
return string(b)
}
第二种 字节替换rune
如果需求是只使用英语字母字符(包括大小写)，那么我们可以使用byte替换rune,因为UTF-8编码中英语字母和byte是一一对应的。
const = letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
func RandStringBytes(n int) string {
b := make([]byte, n)
for i := rang b {
b[i] = letterBytes[rand.Intn(len(letterBytes))]
}
return string(b)
}
第三种 使用余数
上一步种我们使用rand.Intn来随机选择一个字符，rand.Intn会调用Rand.Intn,而Rand.Intn会调用Rand.Int31n,它会比直接调用rand.Int63慢，后者会产生一个63bit的随机整数。我们可以使用rand.Int63,然后除以len(letterBytes)的余数来选择字符：
func RandStringBytesRmndr(n int) string {
b := make([]byte, n)
for i := rang b {
b[i] = letterBytes[rand.Int63() & int64(len(letterBytes))]
}
return string(b)
}
使用掩码
通过前面的方案，我们可以看到我们并不需要太多的bit来决定字符的平均分布，事实上我们只需要随机整数的后几个bit就可以来选择字母。对于52个英语字母(大小写)， 只需要6个bit就可以实现均匀分布(52=110100b)，所以我们可以使用rand.Int63后6个bit来实现，我们只接受后六位在0..len(letterBytes)-1的随机数，如果不在这个范围，丢弃重选。 通过掩码就可以得到一个整数的后6个bit。
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)
}
掩码加强版
上面有个不好的地方，会产生大量的丢弃的case,造成重选和浪费。rand.Int63会产生63bit的随机数，如果我们把它分成6份，那么一次就可以产生10个6bit的随机数。这样就减少了浪费。
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)
}
Source
上面的代码的确好，没有太多可以改进的地方，即使可以提升，也得花费很大的复杂度。
我们可以从另外一个方面进行优化，那就是提高随机数的产生(source)。
crypto/rand包提供了Read(b []byte)的方法，它可以随机生成我们所需bit的字节，但是因为处于安全方面的设计和检查，它的随机数产生比较慢。
我们再转回math/rand，rand.Rand使用rand.Source来产生随机bit。rand.Source是一个接口，提供了Int63() int64,正是我们所需要的。
所以我们可以直接使用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)
}
全局的(默认的)随机源是线程安全，里面用到了锁，所以没有我们直接rand.Source更好。
下面的代码是全局的随机源，可以看到Lock/Unlock的使用。
func Int63() int64 { return globalRand.Int63() }
var globalRand = New(&lockedSource{src: NewSource(1).(Source64)})
type lockedSource struct {
lk sync.Mutex
src Source64
}
func (r *lockedSource) Int63() (n int64) {
r.lk.Lock()
n = r.src.Int63()
r.lk.Unlock()
return
}
Go1.7中增加了rand.Read()方法和Rand.Read()函数，我们可以尝试使用它得到一组随机bit,用来获取更高的性能。
一个小问题就是取多少字节的随机数比较好？我们可以说: 和输出字符一样多的。这是一个上限估计，因为字符的索引会少于8bit。 为了维护字符的均匀分布，我们不得不丢弃一些随机数，这可能会获取更多的随机数，所以只能预估大约需要n * letterIdxBits / 8.0字节的随机byte。
当然最好的验证方法就是写一个Benchmark,附录是benchmark的代码，以下是测试的结果:
BenchmarkRunes 1000000 1703 ns/op
BenchmarkBytes 1000000 1328 ns/op
BenchmarkBytesRmndr 1000000 1012 ns/op
BenchmarkBytesMask 1000000 1214 ns/op
BenchmarkBytesMaskImpr 5000000 395 ns/op
BenchmarkBytesMaskImprSrc 5000000 303 ns/op
Benchmark代码
package main
import (
"math/rand"
"testing"
"time"
)
// Implementations
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)
}
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 RandStringBytes(n int) string {
b := make([]byte, n)
for i := range b {
b[i] = letterBytes[rand.Intn(len(letterBytes))]
}
return string(b)
}
func RandStringBytesRmndr(n int) string {
b := make([]byte, n)
for i := range b {
b[i] = letterBytes[rand.Int63()%int64(len(letterBytes))]
}
return string(b)
}
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)
}
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)
}
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)
}
// Benchmark functions
const n = 16
func BenchmarkRunes(b *testing.B) {
for i := 0; i < b.N; i++ {
RandStringRunes(n)
}
}
func BenchmarkBytes(b *testing.B) {
for i := 0; i < b.N; i++ {
RandStringBytes(n)
}
}
func BenchmarkBytesRmndr(b *testing.B) {
for i := 0; i < b.N; i++ {
RandStringBytesRmndr(n)
}
}
func BenchmarkBytesMask(b *testing.B) {
for i := 0; i < b.N; i++ {
RandStringBytesMask(n)
}
}
func BenchmarkBytesMaskImpr(b *testing.B) {
for i := 0; i < b.N; i++ {
RandStringBytesMaskImpr(n)
}
}
func BenchmarkBytesMaskImprSrc(b *testing.B) {
for i := 0; i < b.N; i++ {
RandStringBytesMaskImprSrc(n)
}
}
其它提升
其实如果能替换一个性能更好的随机数生成算法，可能性能会更好，我使用Xorshift算法实现了一个快速的随机数生成器， 和前面的实现做了比较，发觉性能会更好一点。
BenchmarkRunes-4 1000000 1396 ns/op
BenchmarkBytes-4 2000000 799 ns/op
BenchmarkBytesRmndr-4 3000000 627 ns/op
BenchmarkBytesMask-4 2000000 719 ns/op
BenchmarkBytesMaskImpr-4 10000000 260 ns/op
BenchmarkBytesMaskImprSrc-4 10000000 227 ns/op
BenchmarkBytesMaskImprXorshiftSrc-4 10000000 205 ns/op
以上内容均引用自鸟窝的博客
最后一种
import ("math/rand")
func GetRandomString(n int) string {
randBytes := make([]byte, n/2)
rand.Read(randBytes)
return fmt.Sprintf("%x", randBytes)
}