Go中Fisher–Yates shuffle算法的使用
![](/img/space-man-small.png)
Go中Fisher–Yates shuffle算法的使用
ivansliGolang中rand.Shuffle
从go1.10开始,math包新增了rand.Shuffle方法。
1 | data := []int{1,2,3,4,5,6,7,8} |
通过,该方法可以实现随机打散功能(一般用于切片、数组)。
rand.Shuffle 源码
1 | // Shuffle pseudo-randomizes the order of elements using the default Source. |
问题来了:什么是 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 到 N 的数字
- 取一个从 1 到剩下的数字(包括这个数字)的随机数 k
- 从低位开始,得到第 k 个数字(这个数字还没有被取出),把它写在独立的一个列表的最后一位
- 重复第 2 步,直到所有的数字都被取出
- 第 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算法的实现
这里以随机打散切片为例
1 | rand.Seed(time.Now().UnixNano()) |
时间复杂度
在每次迭代时交换这个被取出的数字到原始列表的最后,时间复杂度为 O(n)。
总结
- Fisher–Yates shuffle 算法是一个非常高效又公平的随机排序算法,如果有随机排序数组的需求,可以使用这个算法。
- 时间复杂度仅为 O(n)
- 逻辑简单、易于理解
参考
Fisher–Yates shuffle 洗牌算法