random.sample() 函数原理
random.sample() 函数在 Python 中是基于 Fisher-Yates（或 Knuth）洗牌算法的一个变种实现的。这个算法可以高效地随机打乱一个序列，而 random.sample() 则利用这个算法来从序列中随机选择不重复的元素。以下是 random.sample() 的基本实现原理：
原理步骤：
- 初始化:
- 确定总体的长度
n和需要采样的数量k。 - 创建一个空列表
sample用于存放选中的样本。
- 确定总体的长度
- 选择第一个样本:
- 从
0到n-1的范围内随机选择一个索引i。 - 将
population[i]添加到sample列表中。 - 为了确保不会再次选择到这个元素，将
population[n-1]与population[i]交换位置，并将n减去1。
- 从
- 选择后续样本:
- 对于后续的每个样本，从
0到n-2的范围内随机选择一个索引（因为n每次都在减少）。 - 将
population[i]添加到sample列表中。 - 将
population[n-2]与population[i]交换位置，并将n减去1。
- 对于后续的每个样本，从
- 重复步骤:
- 重复步骤 3，直到
sample列表中有k个元素。
- 重复步骤 3，直到
- 完成:
- 当
sample列表中有k个元素时，停止抽样。
以下是这个算法的伪代码：
- 当
def random_sample(population, k):n = len(population)sample = []for i in range(k):# 从当前未选择的元素中随机选择一个j = random integer from 0 to n-1# 将选择的元素添加到样本列表sample.append(population[j])# 将选择的元素与未选择元素中的最后一个交换位置population[j], population[n-1] = population[n-1], population[j]# 减少未选择的元素数量n -= 1return sample
在 Python 的 random 模块中，random.sample() 函数的实现更加高效和优化，但基本原理是相同的。这个算法确保了每个元素都有相同的被选中的概率，并且每个元素最多被选中一次，从而实现了无放回的随机抽样。