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）算法中的位运算