日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

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

作者：阿白499 ? 更新時間： 2022-11-25 編程語言

Q：怎樣在Go語言中簡單并快速地生成固定長度的隨機字符串？

A：

問題是“最快和最簡單的方式”，接下來我們會一步步迭代，最終實現最快的方式。每次迭代的基準測試代碼放在了答案的末尾。

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

go test -bench . -benchmem

前言

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

原文鏈接：https://juejin.cn/post/7154206953940451335

欄目分類
最近更新