产生随机布尔

Question

What's the fastest way to generate a random bool in go ?

currently I'm doing like this :

package main

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

// random generator
var src = rand.NewSource(time.Now().UnixNano())
var r = rand.New(src)

func main() {
    for i := 0; i < 100; i++ {
        // generate a random boolean and print it 
        fmt.Printf("bool: %s
", r.Intn(2) != 0)
    }
}

How can I improve this ?

Answer 1

Examples of how to generate a random bool value can be found here (not necessarily the fastest solutions, as that wasn't a requirement there):

How can I let a function randomly return either a true or a false in go

The slowest part of such algorithms is always getting the random data (random information). For example a rand.Int31() call returns 31 random bits, but if we only use it to "generate" a random bool value (which is 1 bit of information), we waste 30 bits (which could be 30 additional random bool values!).

Using rand.Source is a good choice, as we don't need all the "code kung-fu" that rand.Rand does on the random data. We just need a source of random information.

rand.Source defines one method to obtain random information:

Int63() int64

This Source.Int63() method returns 63 random bits; to be fast(est), we should use all. Of course generating a single bool value requires only 1 of its bits, but we should store the remaining and use them when subsequent random bools are asked from us.

This is how it can be done:

type boolgen struct {
    src       rand.Source
    cache     int64
    remaining int
}

func (b *boolgen) Bool() bool {
    if b.remaining == 0 {
        b.cache, b.remaining = b.src.Int63(), 63
    }

    result := b.cache&0x01 == 1
    b.cache >>= 1
    b.remaining--

    return result
}

Creating such a boolgen is like this:

func New() *boolgen {
    return &boolgen{src: rand.NewSource(time.Now().UnixNano())}
}

Example usage:

r := New()
for i := 0; i < 100; i++ {
    if i%10 == 0 {
        fmt.Println()
    }
    fmt.Print(r.Bool(), " ")
}

Example output (try it on the Go Playground):

false false true true false false false false false false 
false false false true false false true false true true 
false false true false true false false true true true 
false false false false false false false true true false 
true true true true false false false false true false 
true true true false true true true true true true 
true true false true true false false true false true 
true true false false false true true true true false 
true false false true true true true false false true 
true false false false false false false false true false 

Some notes:

The Source returned by rand.NewSource() is not safe for concurrent use by multiple goroutines, so our boolgen is also not safe for concurrent use. On one hand this is good, as it will be faster (as no synchronization takes place) than using the default source of the rand package which is safe in this manner (which is by the way unexported, so can only be "reached" indirectly through functions of the rand package).

If you need to use this from multiple goroutines, fastest (as in spirit of the question) would be for all goroutines to create their own boolgen, so no synchronization is needed.

If boolgen itself must be made safe for concurrent use, simply its Bool() method should be protected with a sync.Mutex.