当前位置: 首页 > 面试题库 >

如何在Go中生成固定长度的随机字符串?

於意蕴
2023-03-14
问题内容

在Go语言中,我只需要一个随机的字符串(大写或小写),没有数字。最快和最简单的方法是什么?


问题答案:

Paul的解决方案提供了一个 简单的 通用解决方案。

问题要求 “最快,最简单的方法” 。让我们也讨论 最快的
部分。我们将以迭代的方式得出最终的最快的代码。对每个迭代进行基准测试可以在答案的结尾处找到。

所有解决方案和基准代码都可以在GoPlayground上找到。Playground上的代码是测试文件,而不是可执行文件。您必须将其保存到一个名为的文件中XX_test.go,然后使用

go test -bench . -benchmem

前言

如果只需要随机字符串,最快的解决方案不是首选解决方案。为此,保罗的解决方案是完美的。这就是性能确实重要。尽管前两个步骤( Bytes
Remainder )可能是一个可以接受的折衷方案:它们确实将性能提高了大约50%(请参阅 II.Benchmark
部分中的确切数字),并且不会显着增加复杂性。

话虽如此,即使您不需要最快的解决方案,通读此答案也可能是冒险和有教育意义的。

一,改进

1.创世记(符文)

提醒一下,我们正在改进的原始通用解决方案是:

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

2.字节

如果要选择并组合随机字符串的字符仅包含英文字母的大写和小写字母,则只能使用字节,因为英文字母映射为UTF-8编码中的1对1字节(是Go存储字符串的方式)。

所以代替:

var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

我们可以用:

var letters = []bytes("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

甚至更好:

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

现在这已经是一个很大的改进:我们可以实现为aconst(有string常量,但没有切片常量)。作为额外的收获,表达式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)
}

3.剩余

以前的解决方案得到一个随机数,通过调用来指定一个随机的信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()产生所有63位数字的概率均相等)。尽管由于字母的数量52远小于1<<63 - 1,所以失真非常小,所以在实践中这是完全可以的。

为了使这一点更容易理解:假设您想要一个范围为的随机数0..5。使用3个随机位,这将产生0..1比range两倍的概率2..5。使用5个随机位,范围内的数字0..1将以6/32概率出现,范围内的数字2..5将以5/32概率出现,现在更接近所需值。增加位数会使此意义降低,当达到63位时,可以忽略不计。

4.遮罩

110100b。因此,我们将仅使用所返回数字的最低6位rand.Int63()。为了保持字母的均等分布,我们仅在数字落入范围内时才“接受”该数字0..len(letterBytes)-1`。如果最低位更大,我们将其丢弃并查询新的随机数。

请注意,最低位大于或等于的可能性要len(letterBytes)小于0.5一般情况(0.25平均),这意味着即使是这种情况,重复这种“稀有”情况也会降低找不到好的状态的可能性。数。n重复之后,我们将无法获得良好指标的机会比少得多pow(0.5, n),这只是一个较高的估计。在52个字母的情况下,最低的6位不好的机会只是(64-52)/64 = 0.19;
例如,这意味着重复10次后没有很好的数字的机会是1e-8

所以这是解决方案:

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

5.改进了遮罩

先前的解决方案仅使用由返回的63个随机位中的最低6位rand.Int63()。这是浪费,因为获取随机位是我们算法中最慢的部分。

如果我们有52个字母,则意味着6个位编码一个字母索引。因此63个随机位可以指定63/6 = 10不同的字母索引。让我们使用所有这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)
}

6.来源

改进遮罩效果 非常好,我们可以对其进行改进。我们可以,但不值得如此复杂。

现在让我们找到其他需要改进的地方。 随机数的来源。

有一个crypto/rand提供Read(b []byte)功能的包,因此我们可以用它通过一个调用获得所需的字节数。这在性能方面无济于事,因为它crypto/rand实现了加密安全的伪随机数生成器,因此速度要慢得多。

因此,让我们坚持下去math/rand。在rand.Rand使用rand.Source作为随机比特的源。rand.Source是一个接口,它指定一种Int63() int64方法:正是我们最新解决方案中需要和使用的唯一方法。

因此,我们实际上并不需要rand.Rand(包的显式或全局共享rand),rand.Source对于我们来说,a 足够了:

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

另请注意,最后一种解决方案不需要您初始化(种子)未使用Randmath/rand程序包的全局变量(并且rand.Source已正确初始化/植入了种子)。

这里还要注意一件事:math/rand状态包doc :

默认Source是安全的,可以供多个goroutine并发使用。

因此,默认来源比Source可能获得的慢rand.NewSource(),因为默认来源必须在并发访问/使用下提供安全性,而默认来源则不能提供安全性rand.NewSource()(因此Source,它返回的可能性更大)。

7.利用 strings.Builder

之前的所有解决方案都返回一个,string其内容首先构建在切片中([]runeGenesis
中以及[]byte后续的解决方案中),然后转换为string。由于string值是不可变的,因此最终的转换必须复制切片的内容,并且如果转换不能复制,则不能保证字符串的内容不会通过其原始切片进行修改。

Go 1.10推出strings.Builder
strings.Builder一种新的类型,我们可以用它来建立string类似的内容bytes.Buffer。它在内部使用进行操作[]byte,完成后,我们可以string使用其Builder.String()方法获得最终值。但是,最酷的是它可以执行此操作而不执行我们上面刚刚谈到的复制操作。之所以敢于这样做,是因为未暴露用于构建字符串内容的字节片,因此可以确保没有人可以无意或恶意地修改它来更改生成的“不可变”字符串。

因此,我们的下一个想法是不要在切片中构建随机字符串,而是借助a
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()
}

请注意,在创建new之后strings.Buidler,我们调用了它的Builder.Grow()方法,确保它分配了足够大的内部切片(以避免在添加随机字母时重新分配)。

8.“模仿” strings.Builder包装unsafe

strings.Builder``[]byte就像我们自己一样,在内部构建字符串。因此,基本上通过a进行操作会strings.Builder产生一些开销,我们切换到的唯一strings.Builder方法是避免切片的最终复制。

strings.Builder通过使用package避免最终副本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))
}

(9.使用rand.Read()

Go
1.7添加了一个rand.Read()函数和一个Rand.Read()方法。为了获得更好的性能,我们应该尝试使用这些来一步读取所需的字节数。

这有一个小“问题”:我们需要多少个字节?我们可以说:与输出字母的数量一样多。我们认为这是一个较高的估计,因为字母索引使用的少于8位(1个字节)。但是在这一点上,我们已经变得越来越糟(因为获得随机位是“困难的部分”),而且我们得到的超出了需要。

还要注意,要保持所有字母索引的均等分布,可能会有一些我们将无法使用的“垃圾”随机数据,因此我们最终将跳过一些数据,因此在遍历所有数据时最终会变短字节片。我们将需要进一步“递归”获得更多随机字节。现在我们甚至失去了“单次rand打包”的优势…

我们可以“某种程度上”优化从中获取的随机数据的使用math.Rand()。我们可以估计需要多少字节(位)。1个字母需要letterIdxBits位,而我们需要n字母,因此我们需要将n* letterIdxBits /8.0字节四舍五入。我们可以计算出随机索引不可用的可能性(请参见上文),因此我们可以请求更多的“可能”足够(如果事实并非如此,则重复该过程)。例如,我们可以将字节片处理为“位流”,为此,我们有一个不错的第三方lib
:(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

只需从符文转换为字节,我们即可立即获得 24%的 性能提升,而内存需求则下降至 三分之一

摆脱rand.Intn()并使用rand.Int63()它可以再提高 20%

遮罩(在大索引的情况下重复)会稍微减慢(由于重复调用):- 22%

但是,当我们利用63个随机位的全部(或大部分)(一次rand.Int63()调用即可获得10个索引)时:可以节省大量时间: 3倍

如果我们使用(非默认值,新值)rand.Source代替rand.Rand,我们将再次获得 21%的 收益

如果我们使用strings.Builder,我们获得了一个微小的 3.5%速度 ,但我们也取得了 50%
的内存使用和分配的减少!真好!

最后,如果我们敢于使用package unsafe而不是strings.Builder,我们将再次获得 14%的 收益。

最后进行比较来对初始解:RandStringBytesMaskImprSrcUnsafe()快6.3倍
RandStringRunes(),使用 六分之一 存储器和 半尽可能少的分配 。任务完成。



 类似资料:
  • 在Go中,我只想要一个随机的字符串(大写或小写),没有数字。最快和最简单的方法是什么?

  • 问题内容: 我有一个字节数组,固定长度为4。 我需要将每个字节设置为随机字节。如何以最有效的方式这样做?就我而言,这些方法没有提供随机字节功能。 也许有一种内置的方式,还是我应该生成一个随机字符串并将其转换为字节数组? 问题答案: 包兰特 func Read 读取从默认源生成len(p)个随机字节,并将它们写入p。它总是返回len(p)和nil错误。 f unc(* Rand)读 读取生成len(

  • 本文向大家介绍在JavaScript中生成指定长度的随机字符串,包括了在JavaScript中生成指定长度的随机字符串的使用技巧和注意事项,需要的朋友参考一下 我们需要编写一个JavaScript函数,该函数接受数字n,并返回长度为n的随机字符串,其中不包含26个英文小写字母。 因此,让我们为该函数编写代码- 示例 为此的代码将是- 输出结果 控制台中的输出将为- 注意-这是许多可能的输出之一。控

  • 本文向大家介绍Python生成给定长度的随机字符串,包括了Python生成给定长度的随机字符串的使用技巧和注意事项,需要的朋友参考一下 在本文中,我们将看到如何生成具有给定长度的随机字符串。这在创建需要随机性的随机密码或其他程序时很有用。 random.choices 随机模块中的choices函数可以产生字符串,然后可以将其连接以创建给定长度的字符串。 示例 输出结果 运行上面的代码给我们以下结

  • 我想生成一个固定长度的散列字符串。我正在为此使用MessageDigest API。我注意到API中的这个函数,但它返回的是整数而不是字节数组。 当我尝试使用此重载摘要方法时,我得到 java.security.DigestException:对于 SHA-256 摘要,长度必须至少为 32,或者输出缓冲区对于指定的偏移量和长度来说太小。 有人能举个例子来说明如何生成固定长度的哈希值吗?

  • 问题内容: 我需要生成许多固定长度的随机十六进制字符串。 我正在做这样的事情: 但是我遇到了这个紧急错误 错误似乎在 ,但我不知道为什么会出现此错误。 在Go中生成大量固定长度的随机十六进制字符串的最快,最简单的方法是什么? 基准测试 => icza 解决方案更有效 问题答案: 实际上,您发布的代码可以运行,即使其中有错误(请参见下文),也不会引起恐慌(只会使性能变差)。 您发布的堆栈跟踪指示软件