如何用Python蓄水池算法实现随机抽样

一、什么是蓄水池算法

蓄水池算法（Reservoir Sampling）是一种随机抽样算法，它可以在有限的时间内从一个大的数据集中抽取出一个小的样本集。它的原理是：从数据集的第一个元素开始，将第一个元素放入蓄水池中，然后从数据集中的第二个元素开始，以概率 p 将第二个元素替换掉蓄水池中的元素，以此类推，直到最后一个元素。

二、Python 实现蓄水池算法

Python 实现蓄水池算法的步骤如下：

1、建立一个蓄水池，将第一个元素放入蓄水池中；

2、从第二个元素开始，以概率 p 将第二个元素替换掉蓄水池中的元素；

3、以此类推，直到最后一个元素；

4、最后，蓄水池中的元素就是我们要的抽样结果。

三、Python 代码实现蓄水池算法

下面是一个 Python 实现蓄水池算法的代码示例：

1234567891011

import random

def reservoir_sampling(data, k):

sample = data[:k]

n = len(data)

for i in range(k, n):

m = random.randint(0, i)

if m < k:

sample[m] = data[i]

return sample

if __name__ == '__main__':

data = [i for i in range(1000)]

k = 10

sample = reservoir_sampling(data, k)

print(sample)

上面的代码实现了从 1000 个数据中抽取 10 个样本的蓄水池算法。