Q：怎樣在Go語(yǔ)言中簡(jiǎn)單并快速地生成固定長(zhǎng)度的隨機(jī)字符串？

A：

問題是“最快和最簡(jiǎn)單的方式”，接下來我們會(huì)一步步迭代，最終實(shí)現(xiàn)最快的方式。每次迭代的基準(zhǔn)測(cè)試代碼放在了答案的末尾。

所有解決方案和基準(zhǔn)測(cè)試代碼都可以在 Go Playground 上找到。Playground 上的代碼是測(cè)試文件，不是可執(zhí)行文件。你需要把它保存到文件中并命名為XX_test.go然后運(yùn)行

go test -bench . -benchmem

前言

如果您只需要一個(gè)隨機(jī)字符串，最快的解決方案不是首選解決方案。Paul的解決方案(下面的第一種方法)就很好。如果很關(guān)注性能，那么前兩個(gè)方法可能是可接受的折中方案：它們把性能提升了50%，而且也沒有顯著增加復(fù)雜性。

話雖如此，但就算你不需要最快生成隨機(jī)字符串的方法，通讀這篇回答相信你也應(yīng)該會(huì)有所收獲。

Improvements

1. Genesis (Runes)

提醒一下，下面這個(gè)方法是我們用來改進(jìn)的原始通用解決方案：

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

如果要生成的隨機(jī)字符串只包含大小寫英文字母，那么我們可以只使用英文字母字節(jié)，因?yàn)橛⑽淖帜负蚒TF8編碼的字節(jié)是一一對(duì)應(yīng)的(這就是Go存儲(chǔ)字符串的方式)

所以可以這么寫：

// rune 替換為 byte
var letters = []byte("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

或者更好的寫法是：

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

在這里把它寫成一個(gè)常量就已經(jīng)是一個(gè)很大的改進(jìn)了(有字符串常量但沒有切片常量), 還有一點(diǎn)就是表達(dá)式len(letters)也將是一個(gè)常量(如果s是字符串常量，那么len(s)也就是個(gè)常量)

所以我們的第二種方法是這樣的：

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

前面的方法都是通過調(diào)用rand.Intn()來生成一個(gè)隨機(jī)數(shù)從而選擇一個(gè)隨機(jī)的字母。rand.Intn()來自于Rand.Intn(), 而后者又來自于Rand.Int31n()。

與生成一個(gè)具有 63 個(gè)隨機(jī)位的隨機(jī)數(shù)的rand.Int63()相比上面生成隨機(jī)數(shù)的方式要慢得多。

所以我們可以直接調(diào)用rand.Int63()然后對(duì)lenletterBytes)進(jìn)行取余。

func RandStringBytesRmndr(n int) string {
    b := make([]byte, n)
    for i := range b {
        b[i] = letterBytes[rand.Int63() % int64(len(letterBytes))]
    }
    return string(b)
}

這么做是可以的并且要比上面的方法快很多，但是有個(gè)缺點(diǎn)就是所有的字母出現(xiàn)的概率不是完全相等的(假設(shè) rand.Int63() 以相等的概率產(chǎn)生所有 63 位數(shù)字)。由于字母的長(zhǎng)度52比 1<<63 - 1要小得多，因此各個(gè)字母出現(xiàn)的概率的差異非常小，在實(shí)際使用中是完全沒問題的。

解釋下上面字母出現(xiàn)概率不相等的現(xiàn)象：假設(shè)你要生成一個(gè)0..5之間的隨機(jī)數(shù)，如果使用3個(gè)隨機(jī)位，那么會(huì)導(dǎo)致產(chǎn)生數(shù)字0..1范圍內(nèi)的概率是2..5的兩倍；如果使用5個(gè)隨機(jī)位，那么產(chǎn)生0..1范圍的數(shù)字概率是6/32, 2..5范圍的概率位5/32，這已經(jīng)很接近了。增加位數(shù)可以使概率差異越來越小，當(dāng)達(dá)到63位時(shí)，差異已經(jīng)可以忽略不計(jì)了。

4. Masking

在前面的解決方案的基礎(chǔ)上，我們可以通過只使用盡可能多的隨機(jī)數(shù)的最低位來表示字母的數(shù)量從而保持字母的均勻分布。所以我們有52個(gè)字母，那么就需要6位來表示它：52=110100b。因此我們就只使用rand.Int63()返回的數(shù)的最低六位來表示。為了保持字母的均勻粉筆，我們只接受落在0...len(letterBytes)-1范圍內(nèi)的數(shù)字。如果最低位的數(shù)字大于這個(gè)范圍，那么就丟棄它并重新生成一個(gè)新的隨機(jī)數(shù)。

注意，最低位大于等于len(letterBytes)的概率通常小于0.5(平均為0.25)，這意味著重復(fù)出現(xiàn)這種情況會(huì)降低我們找到能用的隨機(jī)數(shù)字的概率。在 n 次重復(fù)后我們?nèi)匀粵]有找到一個(gè)能用的隨機(jī)數(shù)的概率遠(yuǎn)小于pow(0.5, n)，當(dāng)然這是一個(gè)最壞的情況。在52個(gè)字母的情況下，最低6位不能用的可能性為 (64 - 52) / 64 = 0.19，也就是說在10次重復(fù)還沒有遇到可以用的數(shù)字的概率為 1e-8。

所以，這個(gè)解決方法是這樣的：

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 個(gè)隨機(jī)位中的最低 6 位。這是一種浪費(fèi)，因?yàn)楂@取隨機(jī)位是我們算法中最慢的部分。

因?yàn)槲覀冇?2個(gè)字母，可以用6位來編碼一個(gè)字母索引。所以63個(gè)隨機(jī)位可以生成63/6=10個(gè)不同的索引：

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 方法已經(jīng)非常好了，我們幾乎沒辦法做更多的改進(jìn)。可以但沒必要。

現(xiàn)在讓我們找找其他可以改進(jìn)的地方：隨機(jī)數(shù)的來源。

crypto/rand 包，它提供了一個(gè) Read(b []byte) 函數(shù)，我們可以使用它來通過一次調(diào)用獲得盡可能多的字節(jié)。這對(duì)性能沒有幫助，因?yàn)?crypto/rand 實(shí)現(xiàn)了加密安全的偽隨機(jī)數(shù)生成器，因此速度要慢得多。

所以我們還是使用math/rand包。rand.Rand使用的是rand.Source作為隨機(jī)位來源。rand.Source 是一個(gè)指定 Int63() int64 方法的接口：這也正是我們?cè)谧钚陆鉀Q方案中唯一需要和使用的東西。

所以我們并不需要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)
}

還要注意的是，這個(gè)方法不需要初始化(seed)math/rand包里的全局Rand,因?yàn)樗鼪]有被用到。

還有就是：math/rand 的包文檔說明

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

所以默認(rèn)source要比rand.NewSource()生成的source慢，是因?yàn)槟J(rèn)source保證了并發(fā)使用時(shí)是安全的。而 rand.NewSource() 不提供此功能（因此它返回的 Source 更有可能更快）。

7. Utilizing strings.Builder

上面所有的方法返回的字符串都是先創(chuàng)建一個(gè)切片的(第一個(gè)是使用[]rune，后面的都是[]byte)，然后轉(zhuǎn)換成string。這個(gè)轉(zhuǎn)換會(huì)對(duì)切片的內(nèi)容做一次復(fù)制，因?yàn)樽址遣豢勺兊模绻D(zhuǎn)換不進(jìn)行復(fù)制，則不能保證字符串的內(nèi)容不會(huì)被原始切邊修改。詳細(xì)內(nèi)容可以看這里：How to convert utf8 string to []byte?和 golang: []byte(string) vs []byte(*string)。

Go 1.10 引入了 strings.Builder。 strings.Builder 是一種新類型，我們可以使用它像 bytes.Buffer 那樣來創(chuàng)建字符串內(nèi)容。在內(nèi)部，它使用 []byte 來構(gòu)建內(nèi)容，然后我們可以使用它的 Builder.String() 方法獲得最終的字符串值。但是它的不同之處就是不會(huì)執(zhí)行我們上面說到的復(fù)制操作。之所以可以這么做，是因?yàn)樗糜跇?gòu)建的字符串字節(jié)切片沒有暴露出來，所以可以保證不會(huì)有人無(wú)意或者惡意得修改它。

所以我們接下來要做的就是使用strings.Builder而不是切片來創(chuàng)建字符串，最后我們可以再無(wú)需復(fù)制操作的情況下獲得想要的結(jié)果。這在速度方面可能有所幫助，并且在內(nèi)存使用和分配方面肯定會(huì)有所幫助。

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本質(zhì)上做得和我們上面做得一樣，都是使用切片來創(chuàng)建字符串，我們使用它的唯一原因就是為了避免對(duì)切片的復(fù)制操作。

strings.Builder通過unsafe避免復(fù)制操作：

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

其實(shí)我們也可以自己來做這件事。回到之前我們使用[]byte來創(chuàng)建隨機(jī)字符串，但是在最后不是把它轉(zhuǎn)換成string然后返回，而是做一個(gè)不安全的轉(zhuǎn)換：獲取一個(gè)指向我們的字節(jié)切片的字符串作為字符串?dāng)?shù)據(jù)。

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