快速产生一个随机字符串

如何高效的产生一个随机字符串？这看似是一个简单的问题，但是icza却通过例子，逐步优化，实现了一个更高效的随机字符串的算法。这是来自的来自stackoverflow上的一个问题： How to generate a random string of a fixed length in Go? , 大家群策群力，提出了很好的方案和反馈，尤其是icza的回答。 本文翻译和整理自这条问答。

问题是这样的：

我想要一个 Go 实现的固定长度的随机字符串(包括大小写字母，但是没有数字)，哪种方式最快最简单？

优化基于Paul Hankin提出的一种方案(第一种方案)，也就是最基本最容易理解的一种方案， icza基于这个方案逐步优化。

最通用的方案

最普通方案就是随机产生每个字符，所以整体字符串也是随机的。这样的好处是可以控制要使用的字符。

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)
}

字节替换rune

如果需求是只使用英语字母字符(包括大小写)，那么我们可以使用byte替换rune,因为UTF-8编码中英语字母和byte是一一对应的。

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)
}

使用余数

上一步中我们使用 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 := range b {
        b[i] = letterBytes[rand.Int63() % int64(len(letterBytes))]
    }
    return string(b)
}

这个实现明显会比上面的解决方案快，但是有一点小小的瑕疵：那就是字符被选择的概率并不是完全一样。但是这个差别是非常非常的小(字符的数量52远远小于1<<63 -1),

只是理论上会有差别，实践中可以忽略不计。

掩码

通过前面的方案，我们可以看到我们并不需要太多的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