c語言随機生成字元串_一步步提升Go語言生成随機字元串的效率

假如我們要生成一個固定長度的随機字元串，包含大小寫字母，沒有數字，沒有特殊字元串，那麼我們怎麼做呢？需要怎樣優化，才會更簡單，更高效？在最終的方案之前，我們看看最常見的寫法是怎樣的，然後是如何一步步演進到最終的高效率方案的。好吧，先看下最原始的方案。

常見做法(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)
}

這個實作比較簡單，二十六字母（大小寫），然後随機取數，獲得随機字元串。

Bytes改進

我們在最開始的時候進行了假設，我們的随機字元串隻包含大小寫字母，這樣的話，我們發現沒有必要使用

rune

類型存儲，因為在Golang（Go語言）UTF-8編碼下，英文字母和

byte

位元組是一對一的。

byte

的本質是

uint8

類型，而

rune

本質是

int32

類型。我們改進後的代碼如下：

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

仔細看上面的代碼，我們不光對

rune

類型進行了改進，還把原來的

letter

變量變成了常量，這樣

len(letterBytes)

也是一個常量，代碼的效率将大大提升。

餘數改進

我們前面的方案都是通過調用

rand.Intn()

生成的随機字元，這個

rand.Intn()

其實是委托調用的

Rand.Intn()

,而

Rand.Intn()

最終又是調用的

Rand.Int31n()

實作。相比我們直接調用

rand.Int63()

來說，

rand.Intn()

要慢很多。

是以我們可以把

rand.Intn()

換成

rand.Int63()

來提高效率，為了不超過

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

這種方式雖然快，但是有個缺點，就是每個字母的機率可能會不一樣，不過52個字母相比

1<<63-1

是在太小太小，是以在這種情況下，這個缺點可以忽略不計。

Masking 掩碼

基于前面的方案，我們可以進一步改進，使用随機數的最低位保證字母的均等配置設定，也就是掩碼的方式。我們現在有52個字母，52用二進制表示就是

52==110100b

，是以我們可以隻使用

rand.Int63()

傳回最低的6位數就可以。為了保證平均分為，如果傳回的隻大于

len(letterBytes)-1

，則舍棄不用。

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

按照作者的推測，在52個字母的情況下，随機到超過範圍的可能性

(64-52)/64 = 0.19

,按上面的代碼，如果超過範圍會重複生成，重複的10次的機率僅有

1e-8

。

Masking 掩碼改進

上一步的方案，我們使用

rand.Int63()

可以生成63個随機位的數，但是我們隻用了最低位的6個，有點浪費，因為擷取随機數是我們整個代碼中最慢的部分。現在我們有52個字母，意味着6位編碼字母索引即可滿足，是以我們使用

rand.Int63()

生成的随機數可以被我們使用

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

把生成的63位的随機數，分成10部分，每一部分都可以被我們使用，這樣我們調用

rand.Int63()

次數将大大降低，進而提升效率。

rand Source 優化

rand.Rand

其實是使用了一個

rand.Source

作為生成随機數的源，這個

rand.Source

是個接口，正好有個

func Int63() int64

方法。

// A Source represents a source of uniformly-distributed
// pseudo-random int64 values in the range [0, 1<<63).
type Source interface {
    Int63() int64
    Seed(seed int64)
}

這正好是我們需要的，也夠我們用了。改進後代碼如下：

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

原來的

rand.Int63()

是整個

rand

包全局的，而且支援安全高并發，是以速度比較慢。現在我們自己建立的這個

src

隻有我們自己用，是以效率比較高。

strings.Builder 改進

這個是G0 1.10 新增的功能，提升字元串拼接的效率，這方面的可以參考我以前寫的三篇文章，這裡不做過多的介紹了。

Go語言字元串高效拼接（一）

Go語言字元串高效拼接（二）

Go語言字元串高效拼接（三）

經過改進後，代碼如下：

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

使用unsafe包模拟 strings.Builder

strings.Builder

的原理其實很簡單，是内置了一個

[]byte

存儲字元，最終轉換為

string

的時候為了避免拷貝，使用了

unsafe

包。

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

以上這些我們可以自己來做，看看我們重寫後的代碼。

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

效果和使用

strings.Builder

一樣，而且看起來更簡潔了。

Benchmark 性能測試

以後，我們通過一步步的改進代碼，提升效率，現在我們通過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

僅僅從

rune

到

byte

的改進，我們就獲得了

24%

的提升，記憶體占用降低了

三分之一

。

使用

rand.Int63

替換掉原來的

rand.Intn

，我們又獲得了近

20%

的提升。

單純的使用掩碼，因為重複擷取可用索引的問題，性能下降了

-22%

。

但是當我們對 Masking 掩碼進行改進，分為10部分緩存的時候，我們獲得了

3倍

的提升。

使用

rand.Source

代替

rand.Rand

, 我們再次獲得了

21%

的提升。

使用

strings.Builder

,速度提升雖然隻有

3.5%

,但是記憶體配置設定降低了

50%

。

最後，通過

unsafe

包精簡重寫了

strings.Builder

的功能，我們又獲得了

14%

的提升。

最終，

RandStringBytesMaskImprSrcUnsafe

比

RandStringRunes

快

6.3倍

，并且隻使用了

六分之一

的記憶體和

一半的

記憶體配置設定，我們就完成了任務。

結語

這是一篇stackoverflow的文章，有人提問 How to generate a random string of a fixed length in Go? ，icza 做了非常精彩的回答，我把整個翻譯下來加以整理分享給大家。

這是一篇非常棒的文章，它的意義不光是回答這個問題，還有幫助我們建立如何一步步優化的思路以及追求極緻的極客精神。

與大家共勉。

c語言随機生成字元串_一步步提升Go語言生成随機字元串的效率

常見做法(Runes)

Bytes改進

餘數改進

Masking 掩碼

Masking 掩碼改進

rand Source 優化

strings.Builder 改進

使用unsafe包模拟 strings.Builder

Benchmark 性能測試

結語

繼續閱讀

go int64轉string_Go語言複習筆記——基本文法一之變量與資料類型變量一、聲明變量二、變量初始化三、多個變量同時指派四、匿名變量資料類型1. 整型(int)2. 浮點型(float)3. 布爾型(bool)4. 字元串(string)5. 字元(byte)6. 切片

c int轉字元串_pandas float、object類型轉int類型

golang for循環_golang 遇坑總結

go int 轉string_go 變量傳遞和切片

go int 轉string_Go語言泛型的進化

c++ _int64轉字元串_go|字元串、整型和浮點型的互相轉換

c++ 異或_位運算中異或的常見用法總結

随機生成10條不重複長度為10以内的字元串，進行排序

生成n套數位加減乘除_雪花算法（02）算法中的位運算