Go實現快速生成固定長度的隨機字串

2022-10-18 14:01:21

前言

如果您只需要一個隨機字串，最快的解決方案不是首選解決方案。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

以上就是Go實現快速生成固定長度的隨機字串的詳細內容，更多關於Go生成固定長度隨機字串的資料請關注it145.com其它相關文章！