洗牌算法

所谓“洗牌算法”，就是把一组序列完全打乱，怎样才算乱呢？需要满足这样一个条件：对于包含n个元素的序列，每个元素出现在每个位置的概率都是$1/n$。

一种直白的方法就是，统计序列的全排列，然后在全排列集合中随机选取一各排列出来。这种方法虽然简单，但是无论是空间还是时间复杂度都太高了，有没有其他性能更高的算法呢？当然有，本文简单总结下集中常用的洗牌算法。

Fisher-Yates Shuffle算法

Fisher-Yates Shuffle的思想是：从原始数组中随机取一个之前没有取过的数字放到新数组中，具体步骤如下：

1. 初始化原始数组和新数组，假设数组长度为n；
2. 从原始数组中随机选取之前没选过的数，放到新数组中；
3. 重复第2步，直到所有数字都被选中过；
4. 新数组中的序列就是一个完全随机的序列。

这种方法的正确性也非常容易证明：

$\textbf{证明：}对于任意一个元素m被放在位置i的概率 = 前i-1个位置没有选中m * 第i个位置选中了m \\ P = \frac{n-1}{n}\times \frac{n-2}{n-1}\times ...\times\frac{n-i+1}{n-i+2}\times\frac{1}{n-i+1} =\frac{1}{n}$

该算法的性能并不高，因为需要维护哪些数字被选中了，哪些没有被选中，时间复杂度为$O(n^2)$，空间复杂度为$O(n)$。因此在实际应用中并不常用。

Knuth-Durstenfeld Shuffle算法

该算法是唐纳德在“计算机程序艺术”艺术中提出，是Fisher-Yates Shuffle的改进版本。该算法在原始数组中进行交换操作，不仅省去了额外空间需求，还将时间复杂度降低到了$O(n)$。具体步骤如下：

1. 假设初始数组arr大小为n，下标从0开始；
2. 从0~n-1随机选择一个数k，将arr[k]和arr[n-1]交换；
3. 从0~n-2随机选择一个数k，将arr[k]和arr[n-2]交换；
4. 从0~n-3随机选择一个数k，将arr[k]和arr[n-3]交换；
5. 重复上述步骤直到遍历完整个数组。

下面简单证明一下该算法的正确性：

$\begin{aligned} 证明： &对于任意arr[i]洗牌后被放置在n-1处概率 = 第一次就被选中的概率 = 1/n\\ &对于任意arr[i]洗牌后被放置在n-2处概率 = 第一次没被选中的概率 * 第二次被选中的概率 = (n-1)/n * 1/(n-1) = 1/n\\ &...\\ &对于任意arr[i]洗牌后被放置在n-k处概率 = 前k-1次没被选中的概率 * 第k次被选总的概率 \\ &= (n-1)/n * (n-2)/(n-1) * ... * (n-k+1)/(n-k+2) * 1/(n-k+1) = 1/n \end{aligned}$

该算法的优缺点可总结如下：

• 优点
  • 时间复杂度O(n)，空间复杂度O(1)，效率非常高；
• 缺点
  • 原始数组被打乱了；
  • 从后往前排序，无法处理不知道长度或者动态增长的数组。

Inside-Out Algorithm算法

Inside-Out算法的基本思想是：将位置i的数据随机插入前i个（包括i）位置中（假设为k），这个操作是在新数组中进行，然后用原始数据中位置k的数字替换新数组位置i的数字。

其实就是从前往后的Knuth-Durstenfeld Shuffle算法，并且操作是在新数组中进行的，不会破坏原始数组。这里用Java简单实现下该算法：

1
2
3
4
5
6
7
8
9
10
11
12
13

public int[] insideOutShuffle(int[] arr){
    int n = arr.length;
    int[] res = new int[n];
    res[0] = arr[0];
    Random rand = new Random();
    for(int i = 1; i < n; ++i){
        int j = rand.nextInt(i+1)-1;
        //交换res中i和j处的值
        res[i] = res[j];
        res[j] = arr[i];
    }
    return res;
}

下面简单证明下该算法的正确性：

$\begin{aligned} 证明：&求arr[i]被放在位置k处的概率，\\ (1) &当k<=i时，arr[i]被放在k位置的概率 = 在第i次选中k的概率 * 后面n-i次都没选中k \\ &= \frac{1}{i} * \frac{i}{i+1} * ... * \frac{n-1}{n} = \frac{1}{n}\\ (2) &当k>i时，arr[i]被放在k位置的概率 = arr[i]在第k次被选中的概率 * 后面n-k次都没被选中arr[i]的概率 \\ &= \frac{1}{k}*\frac{k}{k+1}*\frac{k+1}{k+2}* ... *\frac{n-1}{n} = \frac{1}{n} \end{aligned}$

另外，该算法由于是从前往后，因此适用于数组长度未知或者会动态增强的情况。

蓄水池抽样

问题是这样的： 给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出m个不重复的数据。 该问题有3个核心点：

1. 数据流长度N很大且不可知，所以不能一次性存入内存；
2. 时间复杂度为O(N)；
3. 随机选取m个数，每个数被选中的概率为m/N。

蓄水池抽样算法的核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int[] reservoir = new int[m];//蓄水池大小为m

// 初始化，将0~m-1处元素放到数组中
for (int i = 0; i < reservoir.length; i++){
    reservoir[i] = dataStream[i];
}
for (int i = m; i < dataStream.length; i++){
    // 随机获得一个[0, i]内的随机整数
    int d = rand.nextInt(i + 1);
    // 如果随机整数落在[0, m-1]范围内，则替换蓄水池中的元素
    if (d < m){
        reservoir[d] = dataStream[i];
    }
}

下面我们简单证明一下该算法的正确性：

$\begin{aligned} 证明：&第i个元素被保留的概率 = 第i个数据进入过蓄水池的概率 * 之后N-i次操作没有把第i个数据替换出去的概率\\ (1)&对于0 < i < m，被选中的概率 = 1 * 后面N-m次操作都没有把i替换出去的概率\\ (1.1)&第m+1次操作，替换i的概率 = \frac{1}{m+1}，不替换的概率 = 1 - \frac{1}{m+1} = \frac{m}{m+1}\\ (1.2)&第m+2次操作，替换i的概率 = \frac{1}{m+2}，不替换的概率 = 1 - \frac{1}{m+2} = \frac{m+1}{m+2}\\ (1.3)&以此类推，第N次操作，替换i的概率 = \frac{1}{N}，不替换的概率 = 1 - \frac{1}{N} = \frac{N-1}{N}\\ (1.4)&这样，对于0<i<m，被选中概率 = \frac{m}{m+1}\times\frac{m+1}{m+2}\times...\times\frac{N-1}{N} = \frac{m}{N}\\ (2)&对于i \geq m，被选中的概率 = \frac{m}{i} \times (1-\frac{1}{i+1}) \times (1-\frac{1}{i+2}) \times...\times(1-\frac{1}{N})=\frac{m}{i}\times\frac{i}{i+1}\times\frac{i+1}{i+2}\times ... \times \frac{N-1}{N} = \frac{m}{N+1} \end{aligned}$

分布式蓄水池抽样

一块CPU的计算能力再强，也总有内存和磁盘IO拖他的后腿。因此为提高数据吞吐量，分布式的硬件搭配软件是现在的主流。

如果遇到超大的数据量，即使是O(N)的时间复杂度，蓄水池抽样程序完成抽样任务也将耗时很久。因此分布式的蓄水池抽样算法应运而生。运作原理如下：

1. 假设有K台机器，将大数据集分成K个数据流，每台机器使用单机版蓄水池抽样处理一个数据流，抽样m个数据，并最后记录处理的数据量为$N_1, N_2, ..., N_k$, (假设$m<N_k$)。$N_1+N_2+...+N_K=N$。
2. 取[1, N]一个随机数d，若$d<N_1$，则在第一台机器的蓄水池中等概率不放回地（1/m）选取一个数据；若$N_1<=d<(N_1+N_2)$，则在第二台机器的蓄水池中等概率不放回地选取一个数据；依次类推，重复m次，则最终从N大数据集中选出m个数据。

m/N的概率验证如下：

1. 第k台机器中的蓄水池数据被选取的概率为$m/N_k$。
2. 从第k台机器的蓄水池中选取一个数据放进最终蓄水池的概率为$N_k/N$。
3. 第k台机器蓄水池的一个数据被选中的概率为1/m。（不放回选取时等概率的）
4. 重复m次选取，则每个数据被选中的概率为$m\times(m/N_k\times N_k/N\times 1/m)=m/N$。

参考资料

1. https://blog.csdn.net/qq_26399665/article/details/79831490
2. https://www.jianshu.com/p/7a9ea6ece2af