从洗牌算法谈起--Python的random.shuffle函数实现原理

2020/01/16 Python 数据结构

此文首发于我的个人博客:zhang0peter的个人博客


昨天看知乎的时候看到了洗牌算法(Knuth shuffle, 最初版本叫Fisher–Yates shuffle/ Sattolo’s algorithm):世界上有哪些代码量很少,但很牛逼很经典的算法或项目案例? - 知乎

具体的问题是:如何打乱一个数组,确保数组乱的很随机。

伪代码的实现如下:

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

在整个过程中,这个算法保证了每一个元素出现在每一个位置的概率是相等的。

洗牌算法时间复杂度为O(N),并且被证明为完美的随机排序。

更具体的说明参考维基:Fisher–Yates shuffle - Wikipedia


然后我就想到了Python的random库中的shuflle函数,shuflle函数的作用就是打乱数组,我觉得具体的实现应该就是这个洗牌算法。

然后去查看random.shuffle的源码:

_inst = Random()
shuffle = _inst.shuffle
    def shuffle(self, x, random=None):
        """Shuffle list x in place, and return None.

        Optional argument random is a 0-argument function returning a
        random float in [0.0, 1.0); if it is the default None, the
        standard random.random will be used.

        """

        if random is None:
            randbelow = self._randbelow
            for i in reversed(range(1, len(x))):
                # pick an element in x[:i+1] with which to exchange x[i]
                j = randbelow(i+1)
                x[i], x[j] = x[j], x[i]
        else:
            _int = int
            for i in reversed(range(1, len(x))):
                # pick an element in x[:i+1] with which to exchange x[i]
                j = _int(random() * (i+1))
                x[i], x[j] = x[j], x[i]

可以看出使用了洗牌算法。

参考:How Python random shuffle works? - Software Engineering Stack Exchange