by smallnest

快速产生一个随机字符串

目录 [−]

  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基于这个方案逐步优化。

最通用的方案

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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是一一对应的。

1
2
3
4
5
6
7
8
9
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)的余数来选择字符：

1
2
3
4
5
6
7
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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的随机数。这样就减少了浪费。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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的代码，以下是测试的结果:

1
2
3
4
5
6
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
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算法实现了一个快速的随机数生成器， 和前面的实现做了比较，发觉性能会更好一点。

1
2
3
4
5
6
7
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