目录 [−]

1. 最通用的方案
2. 字节替换rune
3. 使用余数
4. 掩码
5. 掩码加强版
6. Source
7. Benchmark代码
8. 其它提升

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

问题是这样的：

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

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

最通用的方案

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

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是一一对应的。

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)的余数来选择字符：

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。

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的随机数。这样就减少了浪费。

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，而不是全局或者共享的随机源。

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的使用。

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的代码，以下是测试的结果:

BenchmarkRunes                   1000000              1703 ns/op
BenchmarkBytes                   1000000              1328 ns/op
BenchmarkBytesRmndr              1000000              1012 ns/op
BenchmarkBytesMask               1000000              1214 ns/op
BenchmarkBytesMaskImpr           5000000               395 ns/op
BenchmarkBytesMaskImprSrc        5000000               303 ns/op

Benchmark代码

BenchmarkRandomString_test.go

package main

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

// Implementations

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

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 functions

const n = 16

func 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算法实现了一个快速的随机数生成器， 和前面的实现做了比较，发觉性能会更好一点。

BenchmarkRunes-4                         1000000              1396 ns/op
BenchmarkBytes-4                         2000000               799 ns/op
BenchmarkBytesRmndr-4                    3000000               627 ns/op
BenchmarkBytesMask-4                     2000000               719 ns/op
BenchmarkBytesMaskImpr-4                10000000               260 ns/op
BenchmarkBytesMaskImprSrc-4             10000000               227 ns/op
BenchmarkBytesMaskImprXorshiftSrc-4     10000000               205 ns/op

---

有疑问加站长微信联系（非本文作者）