我想在Go中只有一个随机字符串(大写或小写),没有数字。什么是最快最简单的方法?
Paul的解决方案提供了一种简单,通用的解决方案。
这个问题要求“最快最简单的方法”。让我们来解决最快的部分。我们将以迭代的方式获得最终,最快的代码。可以在答案的最后找到每次迭代的基准测试。
所有解决方案和基准代码都可以在Go Playground上找到。 Playground上的代码是测试文件,而不是可执行文件。您必须将其保存到名为XX_test.go
的文件中并运行它
go test -bench . -benchmem
前言:
如果您只需要一个随机字符串,那么最快的解决方案不是首选解决方案。为此,保罗的解决方案是完美的。如果性能确实很重要。虽然前两个步骤(字节和剩余)可能是一个可接受的折衷方案:它们确实提高了50%的性能(参见II。基准测试部分中的确切数字),并且它们不会显着增加复杂性。
话虽如此,即使您不需要最快的解决方案,阅读这个答案可能是冒险和教育。
提醒一下,我们正在改进的原始通用解决方案是:
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)
}
如果要选择的字符和汇编随机字符串只包含英文字母的大写和小写字母,我们只能使用字节,因为英文字母字母映射到UTF-8编码中的字节1对1(是如何存储字符串)。
所以代替:
var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
我们可以用:
var letters = []bytes("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
甚至更好:
const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
现在这已经是一个很大的进步:我们可以实现它成为一个const
(有string
常数,但there are no slice constants)。作为一个额外的收获,表达len(letters)
也将是一个const
! (如果len(s)
是一个字符串常量,则表达式s
是常量。)
费用是多少?什么都没有。 string
s可以编入索引,索引其字节,完美,正是我们想要的。
我们的下一个目的地如下:
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.Int31n()
代表rand.Int63()
。
与使用63个随机位产生随机数的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)
}
后使用余数:
rand.Int63()
这种方法的效果明显更快,缺点是所有字母的概率都不完全相同(假设52
以相同的概率产生所有63位数字)。尽管变形非常小,因为字母1<<63 - 1
的数量比0..5
小得多,所以在实践中这非常好。
为了使这个理解更容易:假设你想要一个0..1
范围内的随机数。使用3个随机位,这将产生具有双倍概率的数字2..5
,而不是0..1
范围。使用5个随机位,范围6/32
中的数字将出现2..5
概率和5/32
范围内的数字,其中52 = 110100b
概率现在更接近期望值。增加位数会使其不那么重要,当达到63位时,它可以忽略不计。
在前面的解决方案的基础上,我们可以通过使用随机数的最低位来保持字母的均等分布,因为需要许多字母来表示字母数。因此,例如,如果我们有52个字母,则需要6位来表示它:rand.Int63()
。所以我们只使用0..len(letterBytes)-1
返回的最低6位数。为了保持字母的平等分配,如果它落在len(letterBytes)
范围内,我们只“接受”该数字。如果最低位更大,我们将其丢弃并查询新的随机数。
请注意,最低位大于或等于0.5
的可能性一般小于0.25
(平均值为n
),这意味着即使是这种情况,重复这种“罕见”情况也会减少不这样做的可能性。找到一个好数字。在pow(0.5, n)
重复之后,我们没有良好指数的机会远小于(64-52)/64 = 0.19
,这只是一个较高的估计。在52个字母的情况下,6个最低位不好的可能性仅为1e-8
;这意味着例如在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
)
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)
}
。
所以这是解决方案:
rand.Int63()
前面的解决方案仅使用63/6 = 10
返回的63个随机位中的最低6位。这是一种浪费,因为获取随机位是我们算法中最慢的部分。
如果我们有52个字母,那意味着6位代码一个字母索引。所以63个随机位可以指定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)
}
不同的字母索引。让我们使用所有这10个:
crypto/rand
Masking Improved非常好,我们可以改进它。我们可以,但不值得复杂。
现在让我们找到其他改进的东西。随机数的来源。
有一个Read(b []byte)
包提供了crypto/rand
函数,所以我们可以使用它来获得我们需要的单个调用所需的字节数。这在性能方面没有帮助,因为math/rand
实现了加密安全的伪随机数生成器,因此速度要慢得多。
所以让我们坚持使用rand.Rand
包。 rand.Source
使用rand.Source
作为随机位的来源。 Int63() int64
是一个指定rand.Rand
方法的接口:我们最新解决方案中唯一需要和使用的东西。
所以我们真的不需要rand
(显式或全局,共享的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
另请注意,最后一个解决方案不需要您初始化(种子)math/rand
包的全局rand.Source
,因为未使用(并且我们的math/rand
已正确初始化/播种)。
还有一点需要注意:Source
的包文档:
默认Source对于多个goroutine并发使用是安全的。
因此默认源比rand.NewSource()
可能获得的rand.NewSource()
要慢,因为默认源必须在并发访问/使用时提供安全性,而Source
不提供这个(因此它返回的strings.Builder
更可能更快) )。
string
所有先前的解决方案都返回一个[]rune
,其内容首先在切片中构建(Genesis中的[]byte
,后续解决方案中的string
),然后转换为string
。最后的转换必须复制切片的内容,因为How to convert utf8 string to []byte?值是不可变的,如果转换不能复制,则无法保证字符串的内容不会通过其原始切片进行修改。有关详细信息,请参阅golang: []byte(string) vs []byte(*string)和Go 1.10 introduced strings.Builder
.。
strings.Builder
string
我们可以用来构建类似于bytes.Buffer
的[]byte
的内容。它使用string
在内部完成,当我们完成时,我们可以使用其Builder.String()
方法获得最终的strings.Builder
值。但其中很酷的是它没有执行上面刚才讨论的副本就能做到这一点。它敢于这样做,因为用于构建字符串内容的字节切片没有公开,所以保证没有人可以无意或恶意地修改它来改变生成的“不可变”字符串。
所以我们的下一个想法是不在切片中构建随机字符串,但是在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()
}
的帮助下,所以一旦完成,我们就可以获得并返回结果,而无需复制它。这在速度方面可能有所帮助,在内存使用和分配方面肯定会有所帮助。
strings.Buidler
请注意,在创建新的Builder.Grow()
之后,我们调用了它的strings.Builder
方法,确保它分配了足够大的内部切片(以避免在我们添加随机字母时重新分配)。
unsafe
with package strings.Builder
[]byte
在内部strings.Builder
中构建字符串,与我们自己一样。所以基本上通过strings.Builder
做这件事有一些开销,我们切换到strings.Builder
的唯一办法是避免最终复制切片。
unsafe
使用包// String returns the accumulated string.
func (b *Builder) String() string {
return *(*string)(unsafe.Pointer(&b.buf))
}
避免最终副本:
[]byte
问题是,我们也可以自己做。因此,这里的想法是切换回在string
中构建随机字符串,但是当我们完成时,不要将其转换为string
返回,而是进行不安全的转换:获取指向我们的字节切片的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))
}
字符串数据。
这是如何做到的:
rand.Read()
rand.Read()
a Rand.Read()
功能和rand
方法。我们应该尝试使用它们在一个步骤中读取所需的字节数,以获得更好的性能。
这有一个小“问题”:我们需要多少字节?我们可以说:输出字母数量多。我们认为这是一个较高的估计,因为字母索引使用少于8位(1字节)。但在这一点上,我们已经做得更糟(因为获取随机位是“困难部分”),而且我们得到的不仅仅是需要。
还要注意,为了保持所有字母索引的平均分配,可能会有一些我们无法使用的“垃圾”随机数据,因此我们最终会跳过一些数据,因此当我们通过所有数据时最终会缩短字节切片。我们需要进一步获得更多随机字节,“递归地”。而现在我们甚至失去了“单次调用math.Rand()
包”的优势......
我们可以“稍微”优化我们从letterIdxBits
获得的随机数据的使用。我们可以估计我们需要多少字节(比特)。 1个字母需要n
位,我们需要n * letterIdxBits / 8.0
字母,所以我们需要github.com/icza/bitio
字节四舍五入。我们可以计算随机索引不可用的概率(见上文),因此我们可以请求更多“更可能”足够的(如果事实证明它不是,我们重复这个过程)。我们可以将字节切片处理为“比特流”,例如,我们有一个很好的第三方库:rand.Read()
(披露:我是作者)。
但基准代码仍显示我们没有获胜。为什么会这样?
最后一个问题的答案是因为Source.Int63()
使用循环并继续调用RandStringBytesMaskImprSrc()
直到它填充传递的切片。正是RandStringBytesMaskImprSrc()
解决方案的作用,没有中间缓冲区,并且没有增加复杂性。这就是为什么RandStringBytesMaskImprSrc()
仍然在宝座上。是的,rand.Source
使用与rand.Read()
不同的非同步Rand.Read()
。但推理仍然适用;如果我们使用rand.Read()
而不是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
(前者也是非同步的),这证明了。
好的,是时候对不同的解决方案进行基准测试了。
关键时刻:
rand.Intn()
只需从符文切换到字节,我们立即获得24%的性能提升,内存需求降至三分之一。
摆脱rand.Int63()
并使用rand.Int63()
代替另外20%的提升。
掩蔽(并且在大指数的情况下重复)减慢一点(由于重复调用):-22%......
但是当我们利用63个随机位中的所有(或大部分)时(来自一个rand.Source
调用的10个索引):这会加速大时间:3次。
如果我们用(非默认的,新的)rand.Rand
代替strings.Builder
,我们再次获得21%。
如果我们使用unsafe
,我们的速度只有3.5%,但我们的内存使用和分配也减少了50%!真好!
最后,如果我们敢于使用strings.Builder
包而不是RandStringBytesMaskImprSrcUnsafe()
,我们再次获得14%的优惠。
将最终解决方案与初始解决方案进行比较:RandStringRunes()
比package main
import (
"fmt"
"time"
"math/rand"
)
var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
func randSeq(n int) string {
b := make([]rune, n)
for i := range b {
b[i] = letters[rand.Intn(len(letters))]
}
return string(b)
}
func main() {
rand.Seed(time.Now().UnixNano())
fmt.Println(randSeq(10))
}
快6.3倍,使用六分之一内存和一半分配。任务完成。
qazxswpoi
BenchmarkRandStr16-8 20000000 68.1 ns / 16 B / 1分配/输出
你可以为它编写代码。如果你想在UTF-8编码时依赖所有单字节的字母,这个代码可以更简单一些。
crypto/rand
两种可能的选择(当然可能还有更多):
使用包icza's
,它生成加密安全的统一(无偏)字符串。
免责声明:我是该套餐的作者
以下crypto/rand
奇妙地解释了解决方案,这里是使用math/rand
而不是const (
letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" // 52 possibilities
letterIdxBits = 6 // 6 bits to represent 64 possibilities / indexes
letterIdxMask = 1<<letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
)
func SecureRandomAlphaString(length int) string {
result := make([]byte, length)
bufferSize := int(float64(length)*1.3)
for i, j, randomBytes := 0, 0, []byte{}; i < length; j++ {
if j%bufferSize == 0 {
randomBytes = SecureRandomBytes(bufferSize)
}
if idx := int(randomBytes[j%length] & letterIdxMask); idx < len(letterBytes) {
result[i] = letterBytes[idx]
i++
}
}
return string(result)
}
// SecureRandomBytes returns the requested number of bytes using crypto/rand
func SecureRandomBytes(length int) []byte {
var randomBytes = make([]byte, length)
_, err := rand.Read(randomBytes)
if err != nil {
log.Fatal("Unable to generate random bytes")
}
return randomBytes
}
的修改。
// SecureRandomString returns a string of the requested length,
// made from the byte characters provided (only ASCII allowed).
// Uses crypto/rand for security. Will panic if len(availableCharBytes) > 256.
func SecureRandomString(availableCharBytes string, length int) string {
// Compute bitMask
availableCharLength := len(availableCharBytes)
if availableCharLength == 0 || availableCharLength > 256 {
panic("availableCharBytes length must be greater than 0 and less than or equal to 256")
}
var bitLength byte
var bitMask byte
for bits := availableCharLength - 1; bits != 0; {
bits = bits >> 1
bitLength++
}
bitMask = 1<<bitLength - 1
// Compute bufferSize
bufferSize := length + length / 3
// Create random string
result := make([]byte, length)
for i, j, randomBytes := 0, 0, []byte{}; i < length; j++ {
if j%bufferSize == 0 {
// Random byte buffer is empty, get a new one
randomBytes = SecureRandomBytes(bufferSize)
}
// Mask bytes to get an index into the character slice
if idx := int(randomBytes[j%length] & bitMask); idx < availableCharLength {
result[i] = availableCharBytes[idx]
i++
}
}
return string(result)
}
如果你想要一个更通用的解决方案,它允许你传入一个字符字节切片来创建字符串,你可以尝试使用这个:
io.Reader
如果你想传递你自己的随机来源,修改上面接受crypto/rand
而不是使用func randStr(len int) string {
buff := make([]byte, len)
rand.Read(buff)
str := base64.StdEncoding.EncodeToString(buff)
// Base 64 can be longer than len
return str[:len]
}
是微不足道的。
这是我的方式)根据需要使用数学兰特或加密兰特。
import (
"crypto/rand"
"encoding/base64"
"math"
)
func randomBase64String(l int) string {
buff := make([]byte, int(math.Round(float64(l)/float64(1.33333333333))))
rand.Read(buff)
str := base64.RawURLEncoding.EncodeToString(buff)
return str[:l] // strip 1 extra character we get from odd length results
}
如果你想要加密安全的随机数,并且确切的字符集是灵活的(例如,base64很好),你可以准确计算出所需输出大小所需的随机字符的长度。
基本64文本比基数256长1/3。(2 ^ 8 vs 2 ^ 6; 8bits / 6bits = 1.333比率)
import (
"crypto/rand"
"encoding/hex"
"math"
)
func randomBase16String(l int) string {
buff := make([]byte, int(math.Round(float64(l)/2)))
rand.Read(buff)
str := hex.EncodeToString(buff)
return str[:l] // strip 1 extra character we get from odd length results
}
注意:如果你更喜欢+和/字符,你也可以使用RawStdEncoding和_
如果你想要十六进制,基数16比基数256长2倍。(2 ^ 8 vs 2 ^ 4; 8bits / 4bits = 2x ratio)
ratio = 8 / log2(len(charset))
但是,如果您的字符集有base256到baseN编码器,则可以将其扩展为任意字符集。您可以使用表示字符集所需的位数进行相同的大小计算。任意字符集的比率计算是:https://play.golang.org/p/i61WUVR8_3Z)。
虽然这两种解决方案都是安全的,简单的,但应该快速,并且不要浪费你的加密熵池。
这是操场,显示它适用于任何规模。 https://github.com/Pallinder/go-randomdata
另外我发现了一个包含大量方法来处理虚假数据的包。发现它在开发crypto/rand
时播种数据库很有用。也可能对其他人有帮助
如果您愿意在允许的字符池中添加几个字符,则可以使代码适用于通过io.Reader提供随机字节的任何内容。我们在这里使用// len(encodeURL) == 64. This allows (x <= 265) x % 64 to have an even
// distribution.
const encodeURL = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_"
// A helper function create and fill a slice of length n with characters from
// a-zA-Z0-9_-. It panics if there are any problems getting random bytes.
func RandAsciiBytes(n int) []byte {
output := make([]byte, n)
// We will take n bytes, one byte for each character of output.
randomness := make([]byte, n)
// read all random
_, err := rand.Read(randomness)
if err != nil {
panic(err)
}
// fill output
for pos := range output {
// get random item
random := uint8(randomness[pos])
// random % 64
randomPos := random % uint8(len(encodeURL))
// put into output
output[pos] = encodeURL[randomPos]
}
return output
}
。
const (
chars = "0123456789_abcdefghijkl-mnopqrstuvwxyz" //ABCDEFGHIJKLMNOPQRSTUVWXYZ
charsLen = len(chars)
mask = 1<<6 - 1
)
var rng = rand.NewSource(time.Now().UnixNano())
// RandStr 返回指定长度的随机字符串
func RandStr(ln int) string {
/* chars 38个字符
* rng.Int63() 每次产出64bit的随机数,每次我们使用6bit(2^6=64) 可以使用10次
*/
buf := make([]byte, ln)
for idx, cache, remain := ln-1, rng.Int63(), 10; idx >= 0; {
if remain == 0 {
cache, remain = rng.Int63(), 10
}
buf[idx] = chars[int(cache&mask)%charsLen]
cache >>= 6
remain--
idx--
}
return *(*string)(unsafe.Pointer(&buf))
}