网站设计速成,广州网站备案要多久,专业做运动服装的网站,内江 网站建设题目#xff1a; 假设有一组数据流元素有 N 个#xff08;事先不知道 N 具体值#xff09;#xff0c;我们希望选择 n 个样本#xff08;N n#xff09;#xff0c;使用怎样的策略进行抽样可以使得数据流中每个元素被选择的概率恰为 n / N 结论#xff1a; 创建大… 题目 假设有一组数据流元素有 N 个事先不知道 N 具体值我们希望选择 n 个样本N n使用怎样的策略进行抽样可以使得数据流中每个元素被选择的概率恰为 n / N 结论 创建大小为n的容器先把前n个放进去然后第i个从n1开始有n/i的概率保留随机和n个已保留的元素之一交换有1-n/i的概率舍弃 证明 1.数学归纳法 ①当Nn时每个样本都选择概率都为n/N显然成立。 ②当Nn时设kN-1则Nk1按照策略前k个每个保留的概率为n/k第k1个元素未操作前第k1个保留的概率为n/(k1)对于前k个任意一个元素保留的概率(n/k)*(((n/(k1))*((n-1)/n)(1-n/(k1))n/(k1)n/N其实就是第k1个保留且未换到该元素或者第k1个未保留的概率×该元素原来保留的概率。 ③所以当Nn时每个样本选择概率都为n/N。 2.分类推理法 按照该策略对于前n个元素第i个in个元素后还保留的概率为(n/i)*((n-1)/n)(i-n)/i(i-1)/i 那么到第N个元素还保留的概率1*(n/(n1)*((n1)/(n2))*...*(N-1)/Nn/N 那么对于第i个元素(in)最后保留的概率(n/i)*(i/(i1)*...*(N-1)/Nn/N 所以对于所有元素选择概率都为n/N 代码实现 import randomdef reservoir_sampling(stream, k):reservoir []# 填充蓄水池取前k个元素for i in range(k):reservoir.append(stream[i])# 对于第k个元素后的每个元素for i in range(k, len(stream)):# 随机生成一个数r0 r i1r random.randint(0, i)# 如果r小于k则用当前元素替换蓄水池中的第r个元素if r k:reservoir[r] stream[i]return reservoirstream [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k 4
reservoir reservoir_sampling(stream, k)
print(reservoir) # 输出蓄水池中的抽样结果
