How to generate a stream of *unique* random numbers in Go using the standard library

Issue

How can I generate a stream of unique random number in Go?

I want to guarantee there are no duplicate values in array a using math/rand and/or standard Go library utilities.

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

There are questions and solutions on how to generate a series of random number in Go, for example, here.

But I would like to generate a series of random numbers that does not duplicate previous values. Is there a standard/recommended way to achieve this in Go?

My guess is to (1) use permutation or to (2) keep track of previously generated numbers and regenerate a value if it’s been generated before.

But solution (1) sounds like overkill if I only want a few number and (2) sounds very time consuming if I end up generating a long series of random numbers due to collision, and I guess it’s also very memory-consuming.


Use Case: To benchmark a Go program with 10K, 100K, 1M pseudo-random number that has no duplicates.

Solution

Temporary workaround based on @joshlf’s answer

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

Client side code

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

Answered By – cookieisaac

Answer Checked By – Timothy Miller (GoLangFix Admin)

Leave a Reply

Your email address will not be published.