洗牌算法及 random 中 shuffle 方法和 sample 方法浅析

对于算法书买了一本又一本却没一本读完超过 10%，leetcode 刷题从来没坚持超过 3 天的我来说，算法能力真的是渣渣。但是，今天决定写一篇跟算法有关的文章。起因是读了吴师兄的文章《扫雷与算法：如何随机化的布雷（二）之洗牌算法》。因为扫雷这个游戏我是写过的，具体见：《python：游戏：扫雷》。

游戏开始的时候需要随机布雷。扫雷的高级是 16 × 30 的网格，一共有 99 个雷。如果从 0 开始给所有网格做标记，那么布雷的问题就成了从 480 个数中随机选取 99 个数。
第一反应自然是记录已选项：

import random

mines = set()
for i in range(99):
    j = random.randint(0, 480)
    while j in mines:
        j = random.randint(0, 480)
    mines.add(j)
print(mines)

不过这算法看着似乎有点 low 啊。

其实从 480 个数中随机抽取 99 个数，那么只要将这 480 个数打乱，取前 99 个数就好了。这就引出了：高纳德置乱算法（洗牌算法）。

这个算法很牛逼却很好理解，通俗的解释就是：将最后一个数和前面任意 n-1 个数中的一个数进行交换，然后倒数第二个数和前面任意 n-2 个数中的一个数进行交换……以此类推。

这个原理很好理解，通俗得不能再通俗，稍微想一下就会明白，确实如此。

洗牌算法的 python 实现如下：

import random

lst = list(range(10))
for i in reversed(range(len(lst))):
    j = random.randint(0, i)
    lst[i], lst[j] = lst[j], lst[i]
print(lst)

看了吴师兄的文章，我立马去翻了我的扫雷代码，我觉得，我一定是用的那个很 “low” 的算法。翻出代码一看，我用的是 python 提供了随机取样算法：random.sample，感叹 python 的强大，这都有。然后我就想到了，随机打乱一个序列，random.shuffle 不就是干这事的吗？那么 random.shuffle 会是用的洗牌算法吗？

翻看 random.shuffle 的源码，发现正是洗牌算法。

def shuffle(self, x, random=none):
    if random is none:
        randbelow = self._randbelow
        for i in reversed(range(1, len(x))):
            j = randbelow(i + 1)
            x[i], x[j] = x[j], x[i]
    else:
        _int = int
        for i in reversed(range(1, len(x))):
            j = _int(random() * (i + 1))
            x[i], x[j] = x[j], x[i]

一切都是如此的自然而美好，然后我又去瞄了一眼 random.sample 的源码，然后就一头雾水了。我截了部分源码：

n = len(population)
result = [none] * k
setsize = 21        # size of a small set minus size of an empty list
if k > 5:
    setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
if n <= setsize:
    # an n-length list is smaller than a k-length set
    pool = list(population)
    for i in range(k):         # invariant:  non-selected at [0,n-i)
        j = randbelow(n-i)
        result[i] = pool[j]
        pool[j] = pool[n-i-1]   # move non-selected item into vacancy
else:
    selected = set()
    selected_add = selected.add
    for i in range(k):
        j = randbelow(n)
        while j in selected:
            j = randbelow(n)
        selected_add(j)
        result[i] = population[j]
return result

setsize 变量虽然看得一头雾水，但是下面的 if 和 else 部分还是能看懂的。if 里是洗牌算法，而 else 里是那个却是我看着很 “low” 记录已选项算法。

这是怎么回事？为了弄明白其中的道理，我去搜了很多文章查看，最有价值的是下面这篇：

随机取样有两种实现方式，一是随机抽取且不放回，就是洗牌算法；二是随机抽取且放回，就是我想到的记录已选项算法。random.sample 根据条件选择其中之一执行。那么就是说，洗牌算法和记录已选项算法之间是各有优劣的。这让我有点惊讶，不明摆着洗牌算法更优吗？

首先，这个抽样算法肯定不能改变原序列的顺序，而洗牌算法是会改变序列顺序的，所以只能使用序列的副本，代码中也是这么做的 pool = list(population) 创建副本，而记录已选项算法是不会改变原序列顺序的，所以无需创建副本。创建副本也需要消耗时间和空间，算法自然也是要把这考虑进去的。当需要取的样本数量 k 相较于样本总体数量 n 较小时，随机取到重复值的概率也就相对较小。

那 sample 是依据什么来判断应该用哪个算法的呢？源码中的判断基于 setsize 变量，其中还有一段让人看不懂的公式。其实这是在计算 set 所需的内存开销，算法的实现主要考虑的是额外使用的内存，如果 list 拷贝原序列内存占用少，那么用洗牌算法；如果 set 占用内存少，那么使用记录已选项算法。

what？居然是根据额外占用内存多少来判断？这有点太不可思议了。why？

我们来看一下算法的时间复杂度。对于算法很渣渣的小伙伴（例如我）来说，计算算法的时间复杂度也是件挺困难的事，为了简单起见，我用一种简单的方式来说明。

先说洗牌算法，时间复杂度是 o(k)，这个比较好理解。那么，对于记录已选项算法，时间复杂度是 o(nlogn)。这个别问我是怎么算出来的，我没算，抄的。有兴趣的小伙伴可以自行去计算一下。

我们来想一个简单的，对于记录已选项算法，如果每次选取的值恰好都没有重复，那么时间复杂度是多少呢？很显然是 o(k)。那么当 k 远小于 n 的时候，我们可以认为时间复杂度就是 o(k)。

而 sample 算法的思想就是，当 k 较 n 相对较小时，两种算法的时间复杂度都是 o(k)，则选用占用内存较小的；当 k 较 n 相对较接近时，记录已选项算法的时间复杂度就会高于 o(k)，这时就选用洗牌算法。

只得感叹算法真的博大精深。