Go实现快速生成固定长度的随机字符串

前言

如果您只需要一个随机字符串，最快的解决方案不是首选解决方案。Paul的解决方案(下面的第一种方法)就很好。如果很关注性能，那么前两个方法可能是可接受的折中方案：它们把性能提升了50%，而且也没有显著增加复杂性。

话虽如此，但就算你不需要最快生成随机字符串的方法，通读这篇回答相信你也应该会有所收获。

Improvements

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

如果要生成的随机字符串只包含大小写英文字母，那么我们可以只使用英文字母字节，因为英文字母和UTF8编码的字节是一一对应的(这就是Go存储字符串的方式)

所以可以这么写：

// rune 替换为 byte
var letters = []byte("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

或者更好的写法是：

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

在这里把它写成一个常量就已经是一个很大的改进了(有字符串常量但没有切片常量), 还有一点就是表达式len(letters)也将是一个常量(如果s是字符串常量，那么len(s)也就是个常量)

所以我们的第二种方法是这样的：

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.Intn(), 而后者又来自于Rand.Int31n()。

与生成一个具有 63 个随机位的随机数的rand.Int63()相比上面生成随机数的方式要慢得多。

所以我们可以直接调用rand.Int63()然后对lenletterBytes)进行取余。

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个随机位，那么会导致产生数字0..1范围内的概率是2..5的两倍；如果使用5个随机位，那么产生0..1范围的数字概率是6/32, 2..5范围的概率位5/32，这已经很接近了。增加位数可以使概率差异越来越小，当达到63位时，差异已经可以忽略不计了。

4. Masking

在前面的解决方案的基础上，我们可以通过只使用尽可能多的随机数的最低位来表示字母的数量从而保持字母的均匀分布。所以我们有52个字母，那么就需要6位来表示它：52=110100b。因此我们就只使用rand.Int63()返回的数的最低六位来表示。为了保持字母的均匀粉笔，我们只接受落在0...len(letterBytes)-1范围内的数字。如果最低位的数字大于这个范围，那么就丢弃它并重新生成一个新的随机数。

注意，最低位大于等于len(letterBytes)的概率通常小于0.5(平均为0.25)，这意味着重复出现这种情况会降低我们找到能用的随机数字的概率。在 n 次重复后我们仍然没有找到一个能用的随机数的概率远小于pow(0.5, n)，当然这是一个最坏的情况。在52个字母的情况下，最低6位不能用的可能性为 (64 - 52) / 64 = 0.19，也就是说在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)
}

还要注意的是，这个方法不需要初始化(seed)math/rand包里的全局Rand,因为它没有被用到。

还有就是：math/rand 的包文档说明

The default Source is safe for concurrent use by multiple goroutines.(协程安全)

所以默认source要比rand.NewSource()生成的source慢，是因为默认source保证了并发使用时是安全的。而 rand.NewSource() 不提供此功能（因此它返回的 Source 更有可能更快）。

7. Utilizing strings.Builder

上面所有的方法返回的字符串都是先创建一个切片的(第一个是使用[]rune，后面的都是[]byte)，然后转换成string。这个转换会对切片的内容做一次复制，因为字符串是不可变的，如果转换不进行复制，则不能保证字符串的内容不会被原始切边修改。详细内容可以看这里：How to convert utf8 string to []byte?和 golang: []byte(string) vs []byte(*string)。

Go 1.10 引入了 strings.Builder。 strings.Builder 是一种新类型，我们可以使用它像 bytes.Buffer 那样来创建字符串内容。在内部，它使用 []byte 来构建内容，然后我们可以使用它的 Builder.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()
}

8. "Mimicing" strings.Builder with package unsafe

strings.Builder本质上做得和我们上面做得一样，都是使用切片来创建字符串，我们使用它的唯一原因就是为了避免对切片的复制操作。

strings.Builder通过unsafe避免复制操作：

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

其实我们也可以自己来做这件事。回到之前我们使用[]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))
}

Benchmark

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