Stackoverflow高贊問答：如何一步步提升Go生成隨機字符串的效率
假如我們要生成一個固定長度的隨機字符串，包含大小寫字母，沒有數字，沒有特殊字符串，那么我們怎么做呢？需要怎樣優(yōu)化，才會更簡單，更高效？在最終的方案之前，我們看看最常見的寫法是怎樣的，然后是如何一步步演進到最終的高效率方案的。好吧，先看下最原始的方案。
常見做法(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改進
我們在最開始的時候進行了假設，我們的隨機字符串只包含大小寫字母，這樣的話，我們發(fā)現沒有必要使用rune類型存儲，因為在Golang（Go語言）UTF-8編碼下，英文字母和byte字節(jié)是一對一的。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<1?//?All?1-bits,?as?many?as?letterIdxBits
)
func?RandStringBytesMask(n?int)?string?{
????b?:=?make([]byte,?n)
????for?i?:=?0;?i?????????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個，有點浪費，因為獲取隨機數是我們整個代碼中最慢的部分?，F在我們有52個字母，意味著6位編碼字母索引即可滿足，所以我們使用rand.Int63()生成的隨機數可以被我們使用63/6=10次。
const?letterBytes?=?"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
const?(
????letterIdxBits?=?6????????????????????//?6?bits?to?represent?a?letter?index
????letterIdxMask?=?1<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 優(yōu)化
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包全局的，而且支持安全高并發(fā)，所以速度比較慢?，F在我們自己創(chuàng)建的這個src只有我們自己用，所以效率比較高。
strings.Builder 改進
這個是G0 1.10 新增的功能，提升字符串拼接的效率。
經過改進后，代碼如下：
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 做了非常精彩的回答，我把整個翻譯下來加以整理分享給大家。
這是一篇非常棒的文章，它的意義不光是回答這個問題，還有幫助我們建立如何一步步優(yōu)化的思路以及追求極致的極客精神。
與大家共勉。
原文地址：https://stackoverflow.com/questions/22892120/how-to-generate-a-random-string-of-a-fixed-length-in-go
推薦閱讀
xxx
站長 polarisxu
自己的原創(chuàng)文章
不限于 Go 技術
職場和創(chuàng)業(yè)經驗
Go語言中文網
每天為你
分享 Go 知識
Go愛好者值得關注