Golang 加密洗牌

Question

我正在尝试在 Go 中实现一个字符串随机播放函数，它使用加密/兰特而不是数学/兰特。在费雪耶茨洗牌需要随机整数，所以我一直在努力，实现该功能，而无需使用密码/兰特诠释依赖于数学/大。以下是我目前想到的最好的方法，但有没有更好的方法？我找不到现有示例的事实让我想知道为什么没有人这样做是有充分理由的！package mainimport "crypto/rand"import "fmt"import "encoding/binary"func randomInt(max int) int {    var n uint16    binary.Read(rand.Reader, binary.LittleEndian, &n)    return int(n) % max}func shuffle(s *[]string) {        slice := *s        for i := range slice {                j := randomInt(i + 1)                slice[i], slice[j] = slice[j], slice[i]        }        *s = slice    }func main() {        slice := []string{"a", "b", "c", "d", "e", "f", "h", "i", "j", "k"}        shuffle(&slice)        fmt.Println(slice)}

Answer 1

Go 的math/rand库有很好的工具可以从Source.

// A Source represents a source of uniformly-distributed 

// pseudo-random int64 values in the range [0, 1<<63).

type Source interface {

    Int63() int64

    Seed(seed int64)

}

NewSource(seed int64)返回内置的确定性 PRNG，但New(source Source)将允许满足Source接口的任何内容。

这是一个Source由crypto/rand.

type CryptoRandSource struct{}

func NewCryptoRandSource() CryptoRandSource {

    return CryptoRandSource{}

}

func (_ CryptoRandSource) Int63() int64 {

    var b [8]byte

    rand.Read(b[:])

    // mask off sign bit to ensure positive number

    return int64(binary.LittleEndian.Uint64(b[:]) & (1<<63 - 1))

}

func (_ CryptoRandSource) Seed(_ int64) {}

你可以这样使用它：

r := rand.New(NewCryptoRandSource())

for i := 0; i < 10; i++ {

    fmt.Println(r.Int())

}

该math/rand库具有正确实施的Intn()方法，可确保均匀分布。

func (r *Rand) Intn(n int) int {

    if n <= 0 {

        panic("invalid argument to Intn")

    }

    if n <= 1<<31-1 {

        return int(r.Int31n(int32(n)))

    }

    return int(r.Int63n(int64(n)))

}

func (r *Rand) Int31n(n int32) int32 {

    if n <= 0 {

        panic("invalid argument to Int31n")

    }

    if n&(n-1) == 0 { // n is power of two, can mask

        return r.Int31() & (n - 1)

    }

    max := int32((1 << 31) - 1 - (1<<31)%uint32(n))

    v := r.Int31()

    for v > max {

        v = r.Int31()

    }

    return v % n

}

func (r *Rand) Int63n(n int64) int64 {

    if n <= 0 {

        panic("invalid argument to Int63n")

    }

    if n&(n-1) == 0 { // n is power of two, can mask

        return r.Int63() & (n - 1)

    }

    max := int64((1 << 63) - 1 - (1<<63)%uint64(n))

    v := r.Int63()

    for v > max {

        v = r.Int63()

    }

    return v % n

}

加密散列函数也可以包装为Source随机性的替代方法。

Answer 2

来自的数字n % max分布不均匀。例如，

package main

import (

    "fmt"

    "math"

)

func main() {

    max := 7

    size := math.MaxUint8

    count := make([]int, size)

    for i := 0; i < size; i++ {

        count[i%max]++

    }

    fmt.Println(count[:max])

}

输出：

[37 37 37 36 36 36 36]

Answer 3

根据收到的评论，我认为我可以通过添加一个 uniformInt 函数、填充一个 uint32 而不是 uint16 并移除指向切片的指针来改进我的问题中的示例。

package main

import "crypto/rand"

import "fmt"

import "encoding/binary"

func randomInt() int {

        var n uint32

        binary.Read(rand.Reader, binary.LittleEndian, &n)

        return int(n)

}

func uniformInt(max int) (r int) {

        divisor := 4294967295 / max // Max Uint32

        for {

                r = randomInt() / divisor

                if r <= max {

                        break

                }

        }

        return

}

func shuffle(slice []string) {

        for i := range slice {

                j := uniformInt(i + 1)

                slice[i], slice[j] = slice[j], slice[i]

        }

}

func main() {

        slice := []string{"a", "b", "c", "d", "e", "f", "h", "i", "j", "k"}

        shuffle(slice)

        fmt.Println(slice)

}