Golang中Fisher–Yates shuffle算法的使用

ivansli 2021/11/19 371℃ 0

Golang中rand.Shuffle

从go1.10开始,math包新增了rand.Shuffle方法。

data := []int{1,2,3,4,5,6,7,8}

rand.Seed(time.Now().UnixNano())
rand.Shuffle(len(data), func(i, j int) {
    data[i], data[j] = data[j], data[i]
})

fmt.Println(data)
// [1 2 6 4 5 3 7 8] or other,每次执行结果都不一样

通过,该方法可以实现随机打散功能(一般用于切片、数组)。

rand.Shuffle 源码

// Shuffle pseudo-randomizes the order of elements using the default Source.
// n is the number of elements. Shuffle panics if n < 0.
// swap swaps the elements with indexes i and j.
func Shuffle(n int, swap func(i, j int)) { globalRand.Shuffle(n, swap) }


// Shuffle pseudo-randomizes the order of elements.
// n is the number of elements. Shuffle panics if n < 0.
// swap swaps the elements with indexes i and j.
func (r *Rand) Shuffle(n int, swap func(i, j int)) {
    if n < 0 {
        panic("invalid argument to Shuffle")
    }

        // 可以看到,这里使用了 Fisher–Yates shuffle 洗牌算法
    // Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
    // Shuffle really ought not be called with n that doesn't fit in 32 bits.
    // Not only will it take a very long time, but with 2³¹! possible permutations,
    // there's no way that any PRNG can have a big enough internal state to
    // generate even a minuscule percentage of the possible permutations.
    // Nevertheless, the right API signature accepts an int n, so handle it as best we can.
    i := n - 1
    for ; i > 1<<31-1-1; i-- {
        j := int(r.Int63n(int64(i + 1)))
        swap(i, j)
    }
    for ; i > 0; i-- {
        j := int(r.int31n(int32(i + 1)))
        swap(i, j)
    }
}

问题来了:什么是 Fisher–Yates shuffle 洗牌算法呢?

Fisher–Yates shuffle 洗牌算法

简单来说 Fisher–Yates shuffle 算法是一个用来将一个有限集合生成一个随机排列的算法(数组随机排序)。这个算法生成的随机排列是等概率的,同时这个算法非常高效。

Fisher–Yates shuffle 的原始版本,最初描述在 1938 年的 Ronald Fisher(上图) 和 Frank Yates 写的书中,书名为《Statistical tables for biological, agricultural and medical research》。他们使用纸和笔去描述了这个算法,并使用了一个随机数表来提供随机数。它给出了 1 到 N 的数字的的随机排列,具体步骤如下:

  1. 写下从 1 到 N 的数字
  2. 取一个从 1 到剩下的数字(包括这个数字)的随机数 k
  3. 从低位开始,得到第 k 个数字(这个数字还没有被取出),把它写在独立的一个列表的最后一位
  4. 重复第 2 步,直到所有的数字都被取出
  5. 第 3 步写出的这个序列,现在就是原始数字的随机排列

迭代步骤演示

根据每次迭代次数可以用下面的表格,描述这个算法的执行过程

随机数取值范围 随机数 原始数据 结果
1 2 3 4 5 6 7 8
1-8 6 1 2 3 4 5 7 8 6
1-7 2 1 7 3 4 5 8 2 6
1–6 6 1 7 3 4 5 8 2 6
1–5 1 5 7 3 4 1 8 2 6
1–4 3 5 7 4 3 1 8 2 6
1–3 3 5 7 4 3 1 8 2 6
1–2 1 7 5 4 3 1 8 2 6

Go对Fisher–Yates shuffle算法的实现

这里以随机打散切片为例

rand.Seed(time.Now().UnixNano())

shuffle := func(in []int) []int {
    // i等于len(in) - 1, 即:最后一个位置下标
    // 循环条件:i>0是因为i等于0时,只剩下最后一个元素了。这个时候们已经不需要再进行位置交换了
    for i := len(in) - 1; i > 0; i-- {
        // 获取 [0, i) 之间的随机数,即:随机得到的位置
        rands := rand.Intn(i + 1)

            // 把随机位置的数值放到最后一位,然后继续下一轮,从[0, i-1) 找随机
        in[i], in[rands] = in[rands], in[i]
    }
    return in
}

fmt.Println(shuffle([]int{1,2,3,4,5,6,7,8}))

时间复杂度

在每次迭代时交换这个被取出的数字到原始列表的最后,时间复杂度为 O(n)。

总结

  1. Fisher–Yates shuffle 算法是一个非常高效又公平的随机排序算法,如果有随机排序数组的需求,可以使用这个算法。
  2. 时间复杂度仅为 O(n)
  3. 逻辑简单、易于理解

参考

Fisher–Yates shuffle 洗牌算法

https://gaohaoyang.github.io/2016/10/16/shuffle-algorithm/

评论啦~