如何使用Go标准库生成一系列独特的随机数流

Question

如何使用Go标准库生成一系列独特的随机数流

13

如何在Go中生成一串独特的随机数流？

我希望使用math/rand和/或标准Go库工具来确保数组a中没有重复的值。

func RandomNumberGenerator() *rand.Rand {
    s1 := rand.NewSource(time.Now().UnixNano())
    r1 := rand.New(s1)          
    return r1
}
rng := RandomNumberGenerator()    
N := 10000
for i := 0; i < N; i++ {
    a[i] = rng.Int()
}

有关如何在Go中生成一系列随机数的问题和解决方案，例如这里。

但我想生成一系列不重复之前值的随机数。在Go中是否有标准/推荐的方法来实现这一点？

我的猜测是(1)使用置换或(2)跟踪先前生成的数字并重新生成值(如果已经生成过)。

但如果我只想要几个数字，解决方案(1)听起来太过繁琐；如果由于冲突而最终生成了长系列的随机数，则解决方案(2)听起来非常耗时，而且我猜它也非常费内存。

用例: 对一个包含10K、100K、1M个没有重复伪随机数的Go程序进行基准测试。

- cookieisaac

如果你想要使用标准库保证一个唯一的随机序列，你需要实现一个完整循环的伪随机数生成器。如果可预测性不是那么重要，你可以使用更简单的线性同余生成器。 - JimB

请参阅：如何使用Golang生成长度范围内的唯一随机字符串？：https://dev59.com/Spnga4cB1Zd3GeqPSACk - user6169399

但它是（伪）随机数，你所说的“独特”是什么意思？当你说随机时，它只是随机而不是独特！例如，99999是随机数！在真正的RNG中，下一个数字可能再次是99999，这只是偶然发生的！（这是随机的，不是吗！？） - user6169399

@cookieisaac 你能不能生成1,2,3...序列，然后将其随机打乱？如果数字的大小不重要，而你只是想要一个随机顺序，那么这可能是最简单的解决方案，可以绝对保证不会重复。 - biziclop

@biziclop，从技术上讲，我可以这样做，这是我的猜测（1）。然而，我想从[-2^31, 2^31)中获取N个数字，那么我必须洗牌2^32个数字并仅检索前N个数字。当N << 2^32时，这太过于浪费了。（N大约为10万，2^32大约为40亿） - cookieisaac

显示剩余5条评论

6个回答

2

我有一个类似的任务，需要从初始切片中随机选择唯一索引的元素。因此，从包含10k个元素的切片中获取1k个随机唯一元素。

以下是简单的解决方案：

import (
    "time"
    "math/rand"
)

func getRandomElements(array []string) []string {
    result := make([]string, 0)
    existingIndexes := make(map[int]struct{}, 0)
    randomElementsCount := 1000

    for i := 0; i < randomElementsCount; i++ {
        randomIndex := randomIndex(len(array), existingIndexes)
        result = append(result, array[randomIndex])
    }

    return result
}

func randomIndex(size int, existingIndexes map[int]struct{}) int {
    rand.Seed(time.Now().UnixNano())

    for {
        randomIndex := rand.Intn(size)

        _, exists := existingIndexes[randomIndex]
        if !exists {
            existingIndexes[randomIndex] = struct{}{}
            return randomIndex
        }
    }
}

- Martin Zinovsky

1

我看到有两个原因想要这样做。你想测试一个随机数生成器，或者你想要独特的随机数。

你正在测试一个随机数生成器

我的第一个问题是为什么？已经有很多可靠的随机数生成器了。不要自己写，那基本上就是涉足密码学，这从来不是一个好主意。也许你正在测试一个使用随机数生成器来生成随机输出的系统？

这里有一个问题：没有保证随机数是唯一的。它们是随机的。总是有可能碰撞。测试随机输出是否唯一是不正确的。

相反，你想测试结果是否均匀分布。为此，我将引用另一个关于如何测试随机数生成器的答案。

你想要独特的随机数

从实际角度来看，您不需要保证唯一性，但要使冲突的可能性如此之小，以至于不必担心。这就是UUIDs的作用。它们是128位通用唯一标识符。有许多方法可以为特定情况生成它们。

UUIDv4基本上只是一个122位的随机数，具有极小的碰撞几率。让我们来近似计算一下。

n = how many random numbers you'll generate
M = size of the keyspace (2^122 for a 122 bit random number)
P = probability of collision

P = n^2/2M

解决n的问题...

n = sqrt(2MP)

设置 P 为像 1e-12（一万亿分之一）这样的荒谬数字，我们发现你可以生成约 3.2 万亿个 UUIDv4，并且有一万亿分之一的碰撞概率。在 3.2 万亿个 UUIDv4 中发生碰撞的概率比中彩票还要低 1000 倍。我认为这是可以接受的。

这里有一个 Go 中的 UUIDv4 库和一个生成 100 万个唯一随机 128 位值的演示。

package main

import (
    "fmt"
    "github.com/frankenbeanies/uuid4"
)

func main() {
    for i := 0; i <= 1000000; i++ {
        uuid := uuid4.New().Bytes()

        // use the uuid
    }
}

- Schwern

当我提出问题时，这并不是原因。使用情况是，我改进了先前的B+树删除/插入算法，用于没有重复项的输入。我想要提出诸如“此算法针对大小为Z的Y案例比以前的版本提高了X％”之类的声明。不同的基准测试案例场景包括顺序和随机。为了构建测试树以及构建输入数据集，我需要一串没有重复项的“随机”数字流。 - cookieisaac

@cookieisaac 重点仍然存在。你不需要所有额外的工作和内存来保证唯一性，你只需要几乎保证唯一性。math.Rand.Int63 产生100万个数字有大约1/1800万的机会产生重复。这是约为5 sigma或在飞机上死亡的可能性。对于基准测试而言，这是可以接受的。如果你使用 crypto/rand，你可以使它更加不太可能发生。 - Schwern

那个项目一段时间前就结束了，但我记得有一些要求阻止我使用Int63而必须使用Int(32位)。使用int(32位)，即使对于10万个样本，我总是（出于某种原因）遇到重复并使算法崩溃。随着整数位大小的增加，它肯定有助于避免冲突，但不必要地将树的内存占用量翻倍。所以我选择从int32范围[-2,147,483,648 to 2,147,483,647]中采样100万个唯一数字。 - cookieisaac

@cookieisaac 啊，如果你只能使用32位数字，那么生成100万个32位数字肯定会发生碰撞。在大约70,000个数字时，有大约50%的概率。 - Schwern

1

您可以使用golang时间包中的UnixNano函数生成一个长度为12的唯一随机数：

uniqueNumber:=time.Now().UnixNano()/(1<<22)
println(uniqueNumber)

它总是随机的 :D

- ben

0

1- 使用标准库在296ms内生成快速的正负int32唯一伪随机数：

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func main() {
    const n = 1000000
    rand.Seed(time.Now().UTC().UnixNano())
    duplicate := 0
    mp := make(map[int32]struct{}, n)
    var r int32
    t := time.Now()
    for i := 0; i < n; {
        r = rand.Int31()
        if i&1 == 0 {
            r = -r
        }
        if _, ok := mp[r]; ok {
            duplicate++
        } else {
            mp[r] = zero
            i++
        }
    }
    fmt.Println(time.Since(t))
    fmt.Println("len: ", len(mp))
    fmt.Println("duplicate: ", duplicate)
    positive := 0
    for k := range mp {
        if k > 0 {
            positive++
        }
    }
    fmt.Println(`n=`, n, `positive=`, positive)
}

var zero = struct{}{}

输出：

296.0169ms
len:  1000000
duplicate:  118
n= 1000000 positive= 500000

2- 只需填充map[int32]struct{}即可：

for i := int32(0); i < n; i++ {
        m[i] = zero
}

在 Go 中，当阅读时不是按顺序进行的：

for k := range m {
    fmt.Print(k, " ")
}

而且这仅需要183ms来处理1000000个不重复的数字（ The Go Playground ）：

package main

import (
    "fmt"
    "time"
)

func main() {
    const n = 1000000
    m := make(map[int32]struct{}, n)
    t := time.Now()
    for i := int32(0); i < n; i++ {
        m[i] = zero
    }
    fmt.Println(time.Since(t))
    fmt.Println("len: ", len(m))
    //  for k := range m {
    //      fmt.Print(k, " ")
    //  }
}

var zero = struct{}{}

3- 这里是简单但慢的代码（对于200000个唯一数字需要22秒），因此您可以生成并保存到文件中：

package main

import "time"
import "fmt"
import "math/rand"

func main() {
    dup := 0
    t := time.Now()
    const n = 200000
    rand.Seed(time.Now().UTC().UnixNano())
    var a [n]int32
    var exist bool
    for i := 0; i < n; {
        r := rand.Int31()
        exist = false
        for j := 0; j < i; j++ {
            if a[j] == r {
                dup++
                fmt.Println(dup)
                exist = true
                break
            }
        }
        if !exist {
            a[i] = r
            i++
        }
    }
    fmt.Println(time.Since(t))
}

- user6169399

感谢您详细的回答。以下是我的一些评论：代码片段<1>与@joshlf的答案相同，感谢您对结果进行基准测试。代码片段<2>是一个很酷的技巧，我之前不知道。然而，它不适合我的当前用例，因为对于任何给定的固定N，生成的数组将始终相同，这有点违背了伪随机数生成器的目的。如果我将代码片段<3>保存到文件中，则会继承与代码片段<2>相同的缺陷，但速度更慢。 - cookieisaac

@cookieisaac 不用谢，使用 map[int32]struct{} 中的空结构 struct{} 不占用内存，速度快30毫秒，详情请见：http://dave.cheney.net/2014/03/25/the-empty-struct - user6169399

0

基于 @joshlf 的答案的临时解决方案

type UniqueRand struct {
    generated   map[int]bool    //keeps track of
    rng         *rand.Rand      //underlying random number generator
    scope       int             //scope of number to be generated
}

//Generating unique rand less than N
//If N is less or equal to 0, the scope will be unlimited
//If N is greater than 0, it will generate (-scope, +scope)
//If no more unique number can be generated, it will return -1 forwards
func NewUniqueRand(N int) *UniqueRand{
    s1 := rand.NewSource(time.Now().UnixNano())
    r1 := rand.New(s1)
    return &UniqueRand{
        generated: map[int]bool{},
        rng:        r1,
        scope:      N,
    }
}

func (u *UniqueRand) Int() int {
    if u.scope > 0 && len(u.generated) >= u.scope {
        return -1
    }
    for {
        var i int
        if u.scope > 0 {
            i = u.rng.Int() % u.scope
        }else{
            i = u.rng.Int()
        }
        if !u.generated[i] {
            u.generated[i] = true
            return i
        }
    }
}

客户端代码

func TestSetGet2(t *testing.T) {
    const N = 10000
    for _, mask := range []int{0, -1, 0x555555, 0xaaaaaa, 0x333333, 0xcccccc, 0x314159} {
        rng := NewUniqueRand(2*N)
        a := make([]int, N)
        for i := 0; i < N; i++ {
            a[i] = (rng.Int() ^ mask) << 1
        }

        //Benchmark Code
    }
}

- cookieisaac

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- joshlf · Accepted Answer

你应该采用第二种方法。假设你正在运行64位机器，因此生成63位整数（64位，但rand.Int从不返回负数）。即使您生成40亿个数字，仍然只有4十亿分之一的几率任何给定数字都是重复的。因此，你几乎永远不必重新生成，而且几乎永远不需要重新生成两次。

请尝试以下操作：

type UniqueRand struct {
    generated map[int]bool
}

func (u *UniqueRand) Int() int {
    for {
        i := rand.Int()
        if !u.generated[i] {
            u.generated[i] = true
            return i
        }
    }
}

如何使用Go标准库生成一系列*独特*的随机数流

你正在测试一个随机数生成器

你想要独特的随机数

如何使用Go标准库生成一系列独特的随机数流