https://stackoverflow.com/questions/22892120/how-to-generate-a-random-string-of-a-fixed-length-in-go

问题

Go 语言中，我想要一个只包含字母（大写或小写）的随机字符串，不包含数字。最快最简单的方式是什么？

回答

Paul 的回答 提供了一个简单、普遍的解决方法。

这个问题要求“最快，最简单的方法”，让我们也关注最快这一方面。我们将一步步引出最终最快的代码，每一步的跑分也会在答案的最后给出。

所有的解决方式和跑分代码在 Go Playground
给出。其中的代码是测试文件，不是可执行代码文件，所以你需要将它保存在 XX_test.go 文件中，并用如下指令运行：

go test -bench . -benchmem

前言：

如果您只需要一个随机字符串，那么最快的解决方案不是首选解决方案。在那种情况下，Paul 的解答是完美的，这里主要关注性能问题。前两步（Bytes 和
Remainder）可能是一种折衷方案：它们确实将性能提高了约 50%（具体参考跑分部分），而且并不显著增加复杂度。

说了这么多，即使你用不到最快的方法，通读这篇回答也可能学到一些新知识。

一、实现

1. Genesis(Runes) – 起始

提醒一下，我们正在改进的原始通用解决方案是：

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

2. Bytes – 字节

如果随机字符串的组成只包含大小写英文字母，我们只需要用 byte 就好，因为英文字母在 UTF-8 编码中是与 byte 一一对应的（这也是 Go 存储字符串的方式）。

因此，可以将下列代码：

var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

替换为：

var letters = []byte("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

或者这样更好：

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

现在已经是一个很大的改进了：我们将它变成了一个常量（Go 中有字符串常量但没有切片常量
）。额外地，表达式 len(letters) 也会变成常量！（若 s 是字符串常量，则 len(s) 表达式也会是常量。）

那么代价呢？没有代价，字符串可以用下标索引其中的 bytes，完美，正是我们需要的。

现在代码看起来是这样：

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

3. Remainder – 取余

之前的方式调用 rand.Intn() 生成一个随机数字来选取随机字符，该函数委托给 Rand.Intn()，它再委托给 Rand.Int31n()。

这与产生 63 位随机数的 rand.Int63() 函数相比要慢的多。

所以我们直接调用 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)
}

这样可行而且明显要更快，但缺点是所有的字符出现的概率不一定相同（假设 rand.Int63() 以相同的概率生成所有 63 位随机数）。不过误差非常的小，因为 52
远小于 1<<63 - 1，所以实际上完全没问题。

^{为了让这段内容更易理解：假设你需要一个 0..5 以内的整数，使用 3 bit 随机数，则产生 0..1 中的数字的概率要比 2..5 要高一倍。若使用 5 bit 随机数，则 0..1 中的数字的出现概率是 6/32 而 2..5 中的数字出现的概率是 5/32，这更接近需求了。增加随机数位数会减小误差，当达到 63 bit 时，则可以忽略不计。}

4. Masking – 掩码

在之前的基础上，我们只需要用随机数字的最低的几位即可确保字符的平均分布，位数等于表示字符个数的数字的位数。比如我们有 52 个字符，它需要 6
位来表示：52 = 110100b。所以我们只要用 rand.Int63() 产生的随机数的低 6 位即可。为了保证平均分布，我们只“接受”落在 0..len(letterBytes)-1
范围内的数字，如果低几位大于范围则丢弃并重新生成一个随机数。

请注意，最低几位大于等于 len(letterBytes) 的概率通常小于 0.5（平均为 0.25
），这意味着即使是这种情况，重复这种“罕见”情况也会降低找不到好数字的机会。在 n 次重复之后，还是没找到合适的下标的概率远小于 pow(0.5,n)，且这只是个最坏情况。在
52 个字符的情况下，最低 6 位在 10 次重复后还是不可用的概率只有 1e-8。

所以解决方案如下：

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

5. Masking Improved – 改进掩码

上面的方法只使用了 rand.Int63() 返回的 63 位随机数的 最低 6 位。对生成的随机数的浪费是算法中最慢的部分。

如果我们有 52 个字符，意味着只需要 6 位来索引。所以一个 63 位随机数可以分割出 63/6 = 10 个不同的部分，让我们把它们充分利用起来：

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

6. Source – 随机源

上面的 Masking Improved 已经很好了，我们可以改进的不多了。可以是可以，但太复杂了而不值得。

现在我们找找其它可以改进的地方。随机数产生源。

crypto/rand 包提供了 Read(b []byte) 函数， 可以用于在一次调用中获取我们需要的尽可能多的字节。但在性能方面无济于事，crypto/rand 实现了加密安全的伪随机数生成器，因此速度要慢得多。

所以开始看看 math/rand 包，rand.Rand 使用一个 rand.Source 作为随机源。rand.Source 是一个要求实现 Int63() int64 方法的接口：这正是我们最后一个解决方案中需要用的唯一的东西。

因此我们实际上不需要 rand.Rand，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)
}

另请注意，这种方法不需要再初始化不被使用的 math/rand 包的全局 Rand 种子（我们使用的 rand.Source 已经被正确的初始化了）。

还有一点：math/rand 的包文档中指出：

The default Source is safe for concurrent use by multiple goroutines.

译：默认 Source 是并发安全的，可以用在多个 goroutine 中。

所以默认 Source 是要比我们用 rand.NewSource() 生成的 Source 要慢的，因为默认 Source 需要提供并发访问的安全性，而 rand.NewSource() 并未提供（因此该方法生成的 Source 很有可能要快的多）。

7. Utilizing strings.Builder

之前的所有解决方案都返回一个首先由切片（Genesis 中是 []rune，而后续的是 []byte）构建，然后转换而成的 string。这个最终的转换需要复制切片中的值，因为 string 是不可修改的，如果转换不经复制，则无法保证转换后的字符串不会间接被原始切片修改。详见 How to convert utf8 string to []byte? 以及 golang: []byte(string) vs []byte(*string)。

Go 1.10 引入了 strings.Builder。strings.Builder 是一个用于构建 string 内容的类似于 bytes.Buffer 的新类型。它内部由 []byte 构建内容，当结束时，使用 Builder.String() 即可获取最终的 string 值。而最酷的事情是它并没有上面提到的复制操作。它敢这样处理是因为内部用于构建的切片没有暴露出来，因此可以保证没有人可以无意或恶意地修改它生成的“不可变”字符串。

所以我们的下一个想法就是不再使用切片来构建随机字符串，而采用 strings.Builder，在最后直接不经复制获取返回值。这样可能可以提高速度，而且肯定可以优化内存使用和分配。

func RandStringBytesMaskImprSrcSB(n int) string {
    sb := strings.Builder{}
    sb.Grow(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) {
            sb.WriteByte(letterBytes[idx])
            i--
        }
        cache >>= letterIdxBits
        remain--
    }

    return sb.String()
}

一定要注意在声明一个新的 strings.Builder 后，要调用 Builder.Grow() 方法，来保证一次分配足够的内存空间（避免当添加随机字符时重新分配内存）。

8. "Mimicing" strings.Builder with package unsafe – 模仿标准库

strings.Builder 内部用 []byte 构建字符串，和我们所做的事情其实一样。所以在这里用 strings.Builder 有点过犹不及，我们切换到 strings.Builder 只是为了避免最终的切片内存复制。

strings.Builder 利用 unsafe 包来避免最终的复制：

// String returns the accumulated string.
func (b *Builder) String() string {
    return *(*string)(unsafe.Pointer(&b.buf))
}

实际上我们也可以自己做这个操作，所以现在的想法是用回 []byte 来构建字符串，但当我们完成时，不是直接转换为 string 返回，而是做一个 unsafe 转换：声明一个指向我们 byte 切片的 string。

下面是实现方法：

func RandStringBytesMaskImprSrcUnsafe(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)(unsafe.Pointer(&b))
}

(9. Using rand.Read())

Go 1.7 添加了 一个 rand.Read() 函数和一个 Rand.Read() 方法。我们应该研究一下用它一次性尽可能多的读取随机字节是否可以提升性能。

这样有一个小“问题”：我们需要多少字节？可以说：就是输出的随机字符串长度。可以把它当作一个较高的估计，因为字符索引只用到不足 8 位（1 字节）。但在这一点上，已经做得更差了（因为获得随机位是 "困难的部分"），而且我们得到的比需要的更多。

同时要注意保持所有字符出现概率相同，这里会产生一些不能使用的随机“垃圾”数据，所以我们最终会跳过一些数据，而这样会导致最终切片可用部分较少。我们还是需要再次“递归地”获取更多随机字节，而这样我们就甚至就失去了“只调用一次 rand 包”这个优势…

我们可以“稍微”优化我们从 math.Rand() 获取的随机数据的使用率。估计一下总共需要多少随机字节（位），1 个字符需要 letterIdBits 个位，总共需要 n 个字符，则我们差不多需要 n * letterIdxBits / 8.0 字节。我们可以计算随机索引不可用的概率（见上文），因此可以多生成一些以便“更可能”满足需要（若还不满足，则重复这个过程）。可以将字节切片当作，比如“比特流”来处理，为此我们有一个不错的第三方库：github.com/icza/bitio （本文作者是库作者）。

但跑分结果依旧不理想，为什么呢？

答案是 rand.Read() 使用了对 Source.Int63() 的循环调用直到填满传入的切片。其实就是 RandStringBytesMaskImprSrc() 中所做的事情，而且 RandStringBytesMaskImprSrc() 还没有中间缓冲区，没有额外的复杂度。这正是 RandStringBytesMaskImprSrc() 依旧称王的原因。是的，RandStringBytesMaskImprSrc() 使用了 rand.Read() 中没有的非同步的 rand.Source。但推论仍然适用，若适用 Rand.Read() 而不是 rand.Read() （前者也是非同步的），则证明了这一点。

二、跑分

好了，下面是不同解决方案的跑分环节。

关键时刻：

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

仅仅是从 runes 切换到 bytes，我们立马就获得了 24% 的性能提升，而且只有 1/3 的内存占用。

用 rand.Int63() 取代 rand.Int() 提升了 20% 的速度。

掩码（并在过大时重新获取）稍微拖慢了一些（由于多次重复调用）：-22%…

但当我们利用好所有（或大部分）63 个随机位时（每次调用 rand.Int63() 时产生 10 个下标）：速度大大提升了：3倍。

如果我们采用（非默认，自定义的）rand.Source 来取代 rand.Rand 时，又提升了 21%。

如果利用 strings.Builder，速度提升了小小的 3.5%，但减少了 50% 的内存使用和分配！这真不错！

最终使用 unsafe 包替代 strings.Builder，性能再次提升了 14%。

对比最后和最开始的方案：RandStringBytesMaskImprSrcUnsafe() 要比 RandStringRunes() 快 6.3 倍，只占用 1/6 内存和一半的内存分配。任务完成。