快速产生一个随机字符串

鸟窝 2018-09-02 16:47

如何高效的产生一个随机字符串?这看似是一个简单的问题,但是icza却通过例子,逐步优化,实现了一个更高效的随机字符串的算法。这是来自的来自stackoverflow上的一个问题:How to generate a random string of a fixed length in Go?, 大家群策群力,提出了很好的方案和反馈,尤其是icza的回答。 本文翻译和整理自这条问答。

问题是这样的:

我想要一个Go实现的固定长度的随机字符串(包括大小写字母,但是没有数字),哪种方式最快最简单?

优化基于Paul Hankin提出的一种方案(第一种方案),也就是最基本最容易理解的一种方案, icza基于这个方案逐步优化。

最通用的方案

最普通方案就是随机产生每个字符,所以整体字符串也是随机的。这样的好处是可以控制要使用的字符。

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

字节替换rune

如果需求是只使用英语字母字符(包括大小写),那么我们可以使用byte替换rune,因为UTF-8编码中英语字母和byte是一一对应的。

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

使用余数

上一步中我们使用rand.Intn来随机选择一个字符,rand.Intn会调用Rand.Intn, 而Rand.Intn会调用Rand.Int31n,它会比直接调用rand.Int63慢,后者会产生一个63bit的随机整数。

我们可以使用rand.Int63,然后除以len(letterBytes)的余数来选择字符:

1234567
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),
只是理论上会有差别,实践中可以忽略不计。

掩码

通过前面的方案,我们可以看到我们并不需要太多的bit来决定字符的平均分布,事实上我们只需要随机整数的后几个bit就可以来选择字母。对于52个英语字母(大小写), 只需要6个bit就可以实现均匀分布(52=110100b),所以我们可以使用rand.Int63后6个bit来实现,我们只接受后六位在0..len(letterBytes)-1的随机数,如果不在这个范围,丢弃重选。 通过掩码就可以得到一个整数的后6个bit。

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

掩码加强版

上面有个不好的地方,会产生大量的丢弃的case,造成重选和浪费。rand.Int63会产生63bit的随机数,如果我们把它分成6份,那么一次就可以产生10个6bit的随机数。这样就减少了浪费。

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

Source

上面的代码的确好,没有太多可以改进的地方,即使可以提升,也得花费很大的复杂度。

我们可以从另外一个方面进行优化,那就是提高随机数的产生(source)。

crypto/rand包提供了Read(b []byte)的方法,它可以随机生成我们所需bit的字节,但是因为处于安全方面的设计和检查,它的随机数产生比较慢。

我们再转回math/rand,rand.Rand使用rand.Source来产生随机bit。rand.Source是一个接口,提供了Int63() int64,正是我们所需要的。

所以我们可以直接使用rand.Source,而不是全局或者共享的随机源。

1234567891011121314151617181920
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.Source更好。

下面的代码是全局的随机源,可以看到Lock/Unlock的使用。

12345678910111213141516171819202122
func Int63() int64 { return globalRand.Int63() }var globalRand = New(&lockedSource{src: NewSource(1).(Source64)})type lockedSource struct {	lk  sync.Mutex	src Source64}func (r *lockedSource) Int63() (n int64) {	r.lk.Lock()	n = r.src.Int63()	r.lk.Unlock()	return}

Go1.7中增加了rand.Read()方法和Rand.Read()函数,我们可以尝试使用它得到一组随机bit,用来获取更高的性能。

一个小问题就是取多少字节的随机数比较好?我们可以说: 和输出字符一样多的。这是一个上限估计,因为字符的索引会少于8bit。
为了维护字符的均匀分布,我们不得不丢弃一些随机数,这可能会获取更多的随机数,所以只能预估大约需要n * letterIdxBits / 8.0字节的随机byte。

当然最好的验证方法就是写一个Benchmark,附录是benchmark的代码,以下是测试的结果:

123456
BenchmarkRunes                   1000000              1703 ns/opBenchmarkBytes                   1000000              1328 ns/opBenchmarkBytesRmndr              1000000              1012 ns/opBenchmarkBytesMask               1000000              1214 ns/opBenchmarkBytesMaskImpr           5000000               395 ns/opBenchmarkBytesMaskImprSrc        5000000               303 ns/op

Benchmark代码

BenchmarkRandomString_test.go
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135
package mainimport (	"math/rand"	"testing"	"time")// Implementationsfunc 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)}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 RandStringBytes(n int) string {	b := make([]byte, n)	for i := range b {		b[i] = letterBytes[rand.Intn(len(letterBytes))]	}	return string(b)}func RandStringBytesRmndr(n int) string {	b := make([]byte, n)	for i := range b {		b[i] = letterBytes[rand.Int63()%int64(len(letterBytes))]	}	return string(b)}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)}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)}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)}// Benchmark functionsconst n = 16func BenchmarkRunes(b *testing.B) {	for i := 0; i < b.N; i++ {		RandStringRunes(n)	}}func BenchmarkBytes(b *testing.B) {	for i := 0; i < b.N; i++ {		RandStringBytes(n)	}}func BenchmarkBytesRmndr(b *testing.B) {	for i := 0; i < b.N; i++ {		RandStringBytesRmndr(n)	}}func BenchmarkBytesMask(b *testing.B) {	for i := 0; i < b.N; i++ {		RandStringBytesMask(n)	}}func BenchmarkBytesMaskImpr(b *testing.B) {	for i := 0; i < b.N; i++ {		RandStringBytesMaskImpr(n)	}}func BenchmarkBytesMaskImprSrc(b *testing.B) {	for i := 0; i < b.N; i++ {		RandStringBytesMaskImprSrc(n)	}}

其它提升

其实如果能替换一个性能更好的随机数生成算法,可能性能会更好,我使用Xorshift算法实现了一个快速的随机数生成器, 和前面的实现做了比较,发觉性能会更好一点。

1234567
BenchmarkRunes-4                         1000000              1396 ns/opBenchmarkBytes-4                         2000000               799 ns/opBenchmarkBytesRmndr-4                    3000000               627 ns/opBenchmarkBytesMask-4                     2000000               719 ns/opBenchmarkBytesMaskImpr-4                10000000               260 ns/opBenchmarkBytesMaskImprSrc-4             10000000               227 ns/opBenchmarkBytesMaskImprXorshiftSrc-4     10000000               205 ns/op

[返回] [原文链接]