Go实现快速生成固定长度的随机字符串

目录
  • 前言
  • Improvements
    • 1. Genesis (Runes)
    • 2. Bytes
    • 3. Remainder
    • 4. Masking
    • 5. Masking Improved
    • 6. Source
    • 7. Utilizing strings.Builder
    • 8. "Mimicing" strings.Builder with package unsafe
  • Benchmark

Q:怎样在Go语言中简单并快速地生成固定长度的随机字符串?

A:

问题是“最快和最简单的方式”,接下来我们会一步步迭代,最终实现最快的方式。每次迭代的基准测试代码放在了答案的末尾。

所有解决方案和基准测试代码都可以在 Go Playground 上找到。Playground 上的代码是测试文件,不是可执行文件。你需要把它保存到文件中并命名为XX_test.go然后运行

go test -bench . -benchmem

前言

如果您只需要一个随机字符串,最快的解决方案不是首选解决方案。Paul的解决方案(下面的第一种方法)就很好。如果很关注性能,那么前两个方法可能是可接受的折中方案:它们把性能提升了50%,而且也没有显著增加复杂性。

话虽如此,但就算你不需要最快生成随机字符串的方法,通读这篇回答相信你也应该会有所收获。

Improvements

1. Genesis (Runes)

提醒一下,下面这个方法是我们用来改进的原始通用解决方案:

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. Bytes

如果要生成的随机字符串只包含大小写英文字母,那么我们可以只使用英文字母字节,因为英文字母和UTF8编码的字节是一一对应的(这就是Go存储字符串的方式)

所以可以这么写:

// rune 替换为 byte
var letters = []byte("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

或者更好的写法是:

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

在这里把它写成一个常量就已经是一个很大的改进了(有字符串常量但没有切片常量), 还有一点就是表达式len(letters)也将是一个常量(如果s是字符串常量,那么len(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. Remainder

前面的方法都是通过调用rand.Intn()来生成一个随机数从而选择一个随机的字母。rand.Intn()来自于Rand.Intn(), 而后者又来自于Rand.Int31n()

与生成一个具有 63 个随机位的随机数的rand.Int63()相比上面生成随机数的方式要慢得多。

所以我们可以直接调用rand.Int63()然后对lenletterBytes)进行取余。

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范围内的概率是2..5的两倍;如果使用5个随机位,那么产生0..1范围的数字概率是6/32, 2..5范围的概率位5/32,这已经很接近了。增加位数可以使概率差异越来越小,当达到63位时,差异已经可以忽略不计了。

4. Masking

在前面的解决方案的基础上,我们可以通过只使用尽可能多的随机数的最低位来表示字母的数量从而保持字母的均匀分布。所以我们有52个字母,那么就需要6位来表示它:52=110100b。因此我们就只使用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. Masking Improved

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

因为我们有52个字母,可以用6位来编码一个字母索引。所以63个随机位可以生成63/6=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. Source

上面的 Masking Improved 方法已经非常好了,我们几乎没办法做更多的改进。可以但没必要。

现在让我们找找其他可以改进的地方:随机数的来源。

crypto/rand 包,它提供了一个 Read(b []byte) 函数,我们可以使用它来通过一次调用获得尽可能多的字节。这对性能没有帮助,因为 crypto/rand 实现了加密安全的伪随机数生成器,因此速度要慢得多。

所以我们还是使用math/rand包。rand.Rand使用的是rand.Source作为随机位来源。rand.Source 是一个指定 Int63() int64 方法的接口:这也正是我们在最新解决方案中唯一需要和使用的东西。

所以我们并不需要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)
}

还要注意的是,这个方法不需要初始化(seed)math/rand包里的全局Rand,因为它没有被用到。

还有就是:math/rand 的包文档说明

The default Source is safe for concurrent use by multiple goroutines.(协程安全)

所以默认source要比rand.NewSource()生成的source慢,是因为默认source保证了并发使用时是安全的。而 rand.NewSource() 不提供此功能(因此它返回的 Source 更有可能更快)。

7. Utilizing strings.Builder

上面所有的方法返回的字符串都是先创建一个切片的(第一个是使用[]rune,后面的都是[]byte),然后转换成string。这个转换会对切片的内容做一次复制,因为字符串是不可变的,如果转换不进行复制,则不能保证字符串的内容不会被原始切边修改。详细内容可以看这里:How to convert utf8 string to []byte?golang: []byte(string) vs []byte(*string)

Go 1.10 引入了 strings.Builder。 strings.Builder 是一种新类型,我们可以使用它像 bytes.Buffer 那样来创建字符串内容。在内部,它使用 []byte 来构建内容,然后我们可以使用它的 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()
}

8. "Mimicing" strings.Builder with package unsafe

strings.Builder本质上做得和我们上面做得一样,都是使用切片来创建字符串,我们使用它的唯一原因就是为了避免对切片的复制操作。

strings.Builder通过unsafe避免复制操作:

// String returns the accumulated string.
func (b *Builder) String() string {
    return *(*string)(unsafe.Pointer(&b.buf))
}

其实我们也可以自己来做这件事。回到之前我们使用[]byte来创建随机字符串,但是在最后不是把它转换成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))
}

Benchmark

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

以上就是Go实现快速生成固定长度的随机字符串的详细内容,更多关于Go生成固定长度随机字符串的资料请关注我们其它相关文章!

(0)

相关推荐

  • Golang中生成随机字符串并复制到粘贴板的方法

    前段时间在生活中偶尔需要对某些文件进行重命名,而且是随机名字,刚 开始是手动重命名然后在键盘上胡乱打一些字母数字,时间长了发现也挺麻烦的,于是想到能不能用golang实现这个功能并且自动把生成的字符串 复制到粘贴板,然后生成exe文件,要用的是直接鼠标双击就行.说干就干. 网上搜了些相关资料,于是写了出来. 安装必要的库 go get github.com/atotto/clipboard 代码实现 package main import ( "fmt" "github.co

  • go语言生成随机数和随机字符串的实现方法

    目录 生成随机数 生成随机字符串 生成随机数 随机数的生成是计算机科学的一个研究领域,同时也是一种艺术.这是因为计算机是纯粹的逻辑机器,所以使用计算机生成随机数异常困难! 你可以用 math/rand 包来生成随机数.开始生成随机数之前首先需要一个种子,种子用于整个过程的初始化,它相当重要.因为如果你每次都用同样的种子初始化,那么就总是会得到相同的随机数序列.这意味着每个人都可以重新生成同一个序列,那这个序列就根本不能再算是随机的了! 我们将用来生成随机数的程序名为 randomNumbers.

  • Go实现快速生成固定长度的随机字符串

    目录 前言 Improvements 1. Genesis (Runes) 2. Bytes 3. Remainder 4. Masking 5. Masking Improved 6. Source 7. Utilizing strings.Builder 8. "Mimicing" strings.Builder with package unsafe Benchmark Q:怎样在Go语言中简单并快速地生成固定长度的随机字符串? A: 问题是“最快和最简单的方式”,接下来我们会一

  • c#固定长度的随机字符串例子

    复制代码 代码如下: /// <summary>/// 固定长度的随机字符串/// </summary>/// <param name="length">长度</param>/// <returns>随机串</returns>public static String getRandStringEx(int length){char[] charList = {'0','1','2','3','4','5','6',

  • php生成固定长度纯数字编码的方法

    本文实例讲述了php生成固定长度纯数字编码的方法.分享给大家供大家参考.具体如下: 很多时候我们需要一些固定长度的数字编码,如订单编号.卡号.用户编号等等!但是经常我们有的是存储在数据库中的有序编号,我们可以通过它直接转成一个固定长度的数字编码,然后更新到数据库中形成此记录的唯一编号. <?php /** * 根据日期或者是给定前缀生成唯一编号 * User: minyifei.cn * Date: 15/7/7 */ namespace Minyifei\Libs; class Sequenc

  • Python中生成一个指定长度的随机字符串实现示例

    方法一: 定义一个函数,参数为所要生成随机字符串的长度.通过random.randint(a, b)方法得到随机数字,具体函数如下: def generate_random_str(randomlength=16): """ 生成一个指定长度的随机字符串 """ random_str = '' base_str = 'ABCDEFGHIGKLMNOPQRSTUVWXYZabcdefghigklmnopqrstuvwxyz0123456789' l

  • MySQL中随机生成固定长度字符串的方法

    要随机生成字符串代码如下: 在MySQL中定义一个随机串的方法,然后再SQL语句中调用此方法. 随机串函数定义方法: 复制代码 代码如下: CREATE DEFINER=`root`@`localhost` FUNCTION `rand_string`(n INT) RETURNS varchar(255) CHARSET latin1 BEGIN DECLARE chars_str varchar(100) DEFAULT 'abcdefghijklmnopqrstuvwxyzABCDEFGH

  • python实现字符串加密 生成唯一固定长度字符串

    背景 有时候爬虫爬过的url需要进行指纹核对,比如Scrapy就是进行指纹核对,如果是指纹重复则不再爬取.当然在入库的时候我还是需要做一次核对,否则如果爬虫有漏掉,进入数据库就不合适了. 思路 根据Scrapy的指纹生成方式,这次的指纹生成方式也是用hash的MD5对目标URL进行加密,生成固定长度的字符串,然后在数据库里面将字段设置成unique,这样的话在保证url固定长度的情况下还能够保证入库后的唯一性,进最大努力避免出现重复的数据. 指纹生成代码 新建一个文件,然后在里面编写指纹生成的方

  • Python生成六万个随机,唯一的8位数字和数字组成的随机字符串实例

    上代码: 环境:Python3 import random,string s=string.ascii_letters+string.digits print(s) n={''.join(random.choices(s,k=8)) for I in range(60000)} print(len(n)) with open('a.csv','w') as f: for i in n: f.write(i+'\n') 运行代码,生成a.csv文件并保存. n的类型为set集合类型,实现自动去重.

  • golang包快速生成base64验证码的方法

    base64Captcha快速生成base64编码图片验证码字符串 支持多种样式,算术,数字,字母,混合模式,语音模式. Base64是网络上最常见的用于传输8Bit字节代码的编码方式之一.Base64编码可用于在HTTP环境下传递较长的标识信息, 直接把base64当成是字符串方式的数据就好了 减少了http请求:数据就是图片: 为APIs微服务而设计 为什么base64图片 for RESTful 服务 Data URIs 支持大部分浏览器,IE8之后也支持. 小图片使用base64响应对于

  • python生成随机数、随机字符、随机字符串的方法示例

    本文是基于Windows 10系统环境,实现python生成随机数.随机字符.随机字符串: Windows 10 PyCharm 2018.3.5 for Windows (exe) python 3.6.8 Windows x86 executable installer (1) 生成随机数 随机整数 import random num = random.randint(1, 50) # 闭区间 print(num) 随机选取0到100间的偶数 import random num = rand

  • Mysql 自定义随机字符串的实现方法

    前几天在开发一个系统,需要用到随机字符串,但是mysql的库函数有没有直接提供,就简单的利用现有的函数东拼西凑出随机字符串来.下面简单的说下实现当时. 1.简单粗暴. select ..., substring(MD5(RAND()),floor(RAND()*26)+1,6) as rand_str ..... 上诉示例产生的是:6位长度的随机字符串. 函数解释: rand() :产生 0-1之间的小数,简称种子.rand()*25 产生的数 在 0- 25 之间,不包括25 floor(va

随机推荐