快速产生一个随机字符串

发布于 2023-10-31 19:17:25 字数 9319 浏览 28 评论 0

如何高效的产生一个随机字符串？这看似是一个简单的问题，但是 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 代码

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

分享到QQ

分享到微博