random string in golang

在 日 07 二月 2021 发布于 TECH SKILLS 分类 • 3 min read

在学习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)
}