golang生成随机字符串的八种方式与性能测试

前言

这是icza在StackOverflow上的一篇高赞回答,质量很高,翻译一下,大家一起学习

问题是:go语言中,有没有什么最快最简单的方法,用来生成只包含英文字母的随机字符串

icza给出了8个方案,最简单的方法并不是最快的方法,它们各有优劣,末尾附上性能测试结果:

1. Runes

比较简单的答案,声明一个rune数组,通过随机数选取rune字符,拼接成结果

package approach1

import (
    "fmt"
    "math/rand"
    "testing"
    "time"
)

var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

func randStr(n int) string {
    b := make([]rune, n)
    for i := range b {
        b[i] = letters[rand.Intn(len(letters))]
    }
    return string(b)
}

func TestApproach1(t *testing.T) {
    rand.Seed(time.Now().UnixNano())
    fmt.Println(randStr(10))
}

func BenchmarkApproach1(b *testing.B) {
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < b.N; i++ {
        _ = randStr(10)
    }
}

2. Bytes

如果随机挑选的字符只包含英文字母,我们可以直接使用bytes,因为在UTF-8编码模式下,英文字符和Bytes是一对一的(Go正是使用UTF-8模式编码)

所以可以把

var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

用这个替代

var letters = []byte("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

或者更好

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

现在我们有很大的进展了,我们把它变为了一个常数,在go里面,只有string常数,可并没有slice常数。额外的收获,表达式len(letters)也变为了一个常数(如果s为常数,那么len(s)也将是常数)

我们没有付出什么代码,现在letters可以通过下标访问其中的bytes了,这正是我们需要的。

package approach2

import (
    "fmt"
    "math/rand"
    "testing"
    "time"
)

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

func randStr(n int) string {
    b := make([]byte, n)
    for i := range b {
        b[i] = letters[rand.Intn(len(letters))]
    }
    return string(b)
}

func TestApproach2(t *testing.T) {
    rand.Seed(time.Now().UnixNano())

    fmt.Println(randStr(10))
}

func BenchmarkApproach2(b *testing.B) {
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < b.N; i++ {
        _ = randStr(10)
    }
}

3. Remainder 余数

上面的解决方法通过rand.Intn()来获得一个随机字母,这个方法底层调用了Rand.Intn(),然后调用了Rand.Int31n()

相比于生成63个随机bits的函数rand.Int63()来说,Rand.Int31n()很慢。

我们可以简单地调用rand.Int63()然后除以len(letterBytes),使用它的余数来生成字母

package approach3

import (
    "fmt"
    "math/rand"
    "testing"
    "time"
)

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

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

func TestApproach3(t *testing.T) {
    rand.Seed(time.Now().UnixNano())

    fmt.Println(randStr(10))
}

func BenchmarkApproach3(b *testing.B) {
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < b.N; i++ {
        _ = randStr(10)
    }
}

这个算法能正常工作并且非常快,不过它牺牲了部分精确性,字母出现的概率并不是精确一样的(假设rand.Int63()生成63比特的数字是等概率的)。由于字母总共才52个,远小于 1<<63 - 1,因此失真非常小,因此实际上这完全没问题。

解释: 假设你想要05的随机数,如果使用3位的bit,3位的bit等概率出现07,所以出现0和1的概率是出现2、3、4概率的两倍。使用5位的 bit,0和1出现的概率是6/32,2、3、4出现的概率是5/32。现在接近了一些了,是吧?不断地增加比特位,这个差距就会变得越小,当你有63位地时候,这差别已经可忽略不计。

4. Masking 掩码

在上一个方案的基础上,我们通过仅使用随机数的最低n位保持均匀分布,n表示所有字符的数量。比如我们有52个字母,我们需要6位(52 = 110100b)。所以我们仅仅使用了rand.Int63()的最后6位。并且,为了保持所有字符的均匀分布,我们决定只接受在0..len(letterBytes)-1的数字即0~51。(译者注:这里已经没有第三个方案的不准确问题了)

最低几位大于等于len(letterBytes)的概率一般小于0.5(平均值为0.25),这意味着出现这种情况,只要重试就好。重试n次之后,我们仍然需要丢弃这个数字的概率远小于0.5的n次方(这是上界了,实际会低于这个值)。以本文的52个字母为例,最低6位需要丢弃的概率只有(64-52)/64=0.19。这意味着,重复10次,仍然没有数字的概率是1*10^-8。

package approach4

import (
    "fmt"
    "math/rand"
    "testing"
    "time"
)

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

const (
    // 6 bits to represent a letters index
    letterIdBits = 6
    // All 1-bits as many as letterIdBits
    letterIdMask = 1 <<letterIdBits - 1
)

func randStr(n int) string {
    b := make([]byte, n)
    for i := range b {
        if idx := int(rand.Int63() & letterIdMask); idx < len(letters) {
            b[i] = letters[idx]
            i++
        }
    }
    return string(b)
}

func TestApproach4(t *testing.T) {
    rand.Seed(time.Now().UnixNano())

    fmt.Println(randStr(10))
}

func BenchmarkApproach4(b *testing.B) {
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < b.N; i++ {
        _ = randStr(10)
    }
}

5. Masking Improved

第4节的方案只使用了rand.Int63()方法返回的64个随机字节的后6位。这实在是太浪费了,因为rand.Int63()是我们算法中最耗时的部分了。

如果我们有52个字母,6位就能生成一个随机字符串。所以63个随机字节,可以利用63/6=10次。

译者注:使用了缓存,缓存了rand.Int63()方法返回的内容,使用10次,不过已经并不是协程安全的了。

package approach5

import (
    "fmt"
    "math/rand"
    "testing"
    "time"
)

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

const (
    // 6 bits to represent a letter index
    letterIdBits = 6
    // All 1-bits as many as letterIdBits
    letterIdMask = 1<<letterIdBits - 1
    letterIdMax  = 63 / letterIdBits
)

func randStr(n int) string {
    b := make([]byte, n)
    // A rand.Int63() generates 63 random bits, enough for letterIdMax letters!
    for i, cache, remain := n-1, rand.Int63(), letterIdMax; i >= 0; {
        if remain == 0 {
            cache, remain = rand.Int63(), letterIdMax
        }
        if idx := int(cache & letterIdMask); idx < len(letters) {
            b[i] = letters[idx]
            i--
        }
        cache >>= letterIdBits
        remain--
    }
    return string(b)
}

func TestApproach5(t *testing.T) {
    rand.Seed(time.Now().UnixNano())

    fmt.Println(randStr(10))
}

func BenchmarkApproach5(b *testing.B) {
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < b.N; i++ {
        _ = randStr(10)
    }
}

6. Source

第5个方案非常好,能改进的点并不多。我们可以但不值得搞得很复杂。

让我们来找可以改进的点:随机数的生成源

crypto/rand的包提供了Read(b []byte)的函数,可以通过这个函数获得需要的随机比特数,只需要一次调用。不过并不能提升性能,因为crypto/rand实现了一个密码学上的安全伪随机数,所以速度比较慢。

所以让我们坚持使用math/rand包,rand.Rand使用rand.Source作为随机位的来源,rand.Source是一个声明了Int63() int64的接口:正是我们在最新解决方案中需要和使用的唯一方法。

所以我们不是真的需要rand.Randrand.Source包对于我们来说已经足够了

package approach6

import (
    "fmt"
    "math/rand"
    "testing"
    "time"
)

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

var src = rand.NewSource(time.Now().UnixNano())

const (
    // 6 bits to represent a letter index
    letterIdBits = 6
    // All 1-bits as many as letterIdBits
    letterIdMask = 1<<letterIdBits - 1
    letterIdMax  = 63 / letterIdBits
)

func randStr(n int) string {
    b := make([]byte, n)
    // A rand.Int63() generates 63 random bits, enough for letterIdMax letters!
    for i, cache, remain := n-1, src.Int63(), letterIdMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdMax
        }
        if idx := int(cache & letterIdMask); idx < len(letters) {
            b[i] = letters[idx]
            i--
        }
        cache >>= letterIdBits
        remain--
    }
    return string(b)
}

func TestApproach6(t *testing.T) {
    fmt.Println(randStr(10))
}

func BenchmarkApproach6(b *testing.B) {
    for i := 0; i < b.N; i++ {
        _ = randStr(10)
    }
}

注意到这里我们没有使用种子初始化rand了,取而代之的是初始化了rand.Source

还有一件需要注意的事,math/rand的文档指出

默认的Source是协程安全的

所以默认的Source比通过rand.NewSource()创建出来的Source要慢。不用处理协程并发场景,当然慢啦。

7. 使用 strings.Builder

之前的解决方案都返回了通过slice构造的字符串。最后的一次转换进行了一次拷贝,因为字符串是不可变的,如果转换的时候不进行拷贝,就无法保证转换完成之后,byte slice再被修改后,字符串仍能保持不变。

Go1.10引入了strings.Builder,这是一个新的类型,和bytes.Buffer类似,用来构造字符串。底层使用[]byte来构造内容,正是我们现在在做的,最后可以通过Builder.String()方法来获得最终的字符串值。但它很酷的地方在于,它无需执行刚才谈到的复制即可完成此操作。它敢这么做是因为它底层构造的[]byte从未暴露出来,所以仍然可以保证没有人可以无意地、恶意地来修改已经生成的不可变字符串。

所以我们的下一个想法不是在slice中构建随机字符串,而是使用 strings.Builder,结束building后,我们就可以获取并返回结果,而无需复制。 这可能在速度方面有所帮助,并且在内存使用和分配方面肯定会有所帮助(译者注:等会在benchmark中会清晰地看到)。

package approach7

import (
    "fmt"
    "math/rand"
    "strings"
    "testing"
    "time"
)

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

var src = rand.NewSource(time.Now().UnixNano())

const (
    // 6 bits to represent a letter index
    letterIdBits = 6
    // All 1-bits as many as letterIdBits
    letterIdMask = 1<<letterIdBits - 1
    letterIdMax  = 63 / letterIdBits
)

func randStr(n int) string {
    sb := strings.Builder{}
    sb.Grow(n)
    // A rand.Int63() generates 63 random bits, enough for letterIdMax letters!
    for i, cache, remain := n-1, src.Int63(), letterIdMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdMax
        }
        if idx := int(cache & letterIdMask); idx < len(letters) {
            sb.WriteByte(letters[idx])
            i--
        }
        cache >>= letterIdBits
        remain--
    }
    return sb.String()
}

func TestApproach7(t *testing.T) {
    fmt.Println(randStr(10))
}

func BenchmarkApproach7(b *testing.B) {
    for i := 0; i < b.N; i++ {
        _ = randStr(10)
    }
}

在构造出builder之后,我们立刻调用了Builder.Grow()方法,使得它分配一个足够大的底层slice,避免在后续操作中再进行分配

8. "Mimicing" strings.Builder with package unsafe

模仿string.Builder使用unsafe包

string.Builder跟我们第六节地解法一样,都是用[]byte来构建字符串。切换到strings.Builder可能有一些太重了,我们使用strings.Builder只是想避免拷贝slice。

string.Builder使用unsafe包来避免最终的拷贝

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

我们也可以自己完成这个流程。所以思路是我们通过unsafe包来返回一个字符串,来避免拷贝

package approach8

import (
    "fmt"
    "math/rand"
    "testing"
    "time"
    "unsafe"
)

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

var src = rand.NewSource(time.Now().UnixNano())

const (
    // 6 bits to represent a letter index
    letterIdBits = 6
    // All 1-bits as many as letterIdBits
    letterIdMask = 1<<letterIdBits - 1
    letterIdMax  = 63 / letterIdBits
)

func randStr(n int) string {
    b := make([]byte, n)
    // A rand.Int63() generates 63 random bits, enough for letterIdMax letters!
    for i, cache, remain := n-1, src.Int63(), letterIdMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdMax
        }
        if idx := int(cache & letterIdMask); idx < len(letters) {
            b[i] = letters[idx]
            i--
        }
        cache >>= letterIdBits
        remain--
    }
    return *(*string)(unsafe.Pointer(&b))
}

func TestApproach8(t *testing.T) {
    fmt.Println(randStr(10))
}

func BenchmarkApproach8(b *testing.B) {
    for i := 0; i < b.N; i++ {
        _ = randStr(10)
    }
}

Benchmark

go test ./... -bench=. -benchmem

原作者测试的数据

(译者注:第三列代表操作一次需要多少纳秒)

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

译者测试的数据

BenchmarkApproach1-12            3849038               299.5 ns/op            64 B/op          2 allocs/op
BenchmarkApproach2-12            5545350               216.4 ns/op            32 B/op          2 allocs/op
BenchmarkApproach3-12            7003654               169.7 ns/op            32 B/op          2 allocs/op
BenchmarkApproach4-12            7164259               168.7 ns/op            32 B/op          2 allocs/op
BenchmarkApproach5-12           13205474                89.06 ns/op           32 B/op          2 allocs/op
BenchmarkApproach6-12           13665636                84.41 ns/op           32 B/op          2 allocs/op
BenchmarkApproach7-12           17213431                70.37 ns/op           16 B/op          1 allocs/op
BenchmarkApproach8-12           19756956                61.41 ns/op           16 B/op          1 allocs/op

现在跑出来的数据,相原作者时候,已经有了一些变化,不过并不妨碍我们看出来各个方法的趋势:

  • 仅仅只是把rune切换到byte,就获得了性能的大幅度提升(大于百分之20)
  • 使用rand.Int63()代替rand.Intn()也获得大幅度提升(大于百分之20)
  • 使用Masking并没有提升性能,相反在原作者哪里,反而性能下降了
  • 不过使用了一次rand.Int63()返回的全部字符后,性能提升了3倍
  • 使用rand.Source替代rand.Rand,性能提升了21%
  • 使用strings.Builder,我们在速度上提升了3.5%,并且把原本2次的内存分配,降低到了一次!
  • 使用unsafe包来代替strings.Builder,性能提升了14%

将第八个方案和第一个方案比较,第八个方案比第一个方案快6.3倍,仅仅使用六分之一的内存,分配次数也只有原来的一半。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,080评论 6 493
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,422评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,630评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,554评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,662评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,856评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,014评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,752评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,212评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,541评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,687评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,347评论 4 331
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,973评论 3 315
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,777评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,006评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,406评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,576评论 2 349

推荐阅读更多精彩内容