当前位置: 首页 > news >正文

蓄水池算法

 题目:

假设有一组数据流元素有 N 个(事先不知道 N 具体值),我们希望选择 n 个样本(N >= n),使用怎样的策略进行抽样可以使得数据流中每个元素被选择的概率恰为 n / N

结论:

创建大小为n的容器,先把前n个放进去,然后第i个(从n+1开始)有n/i的概率保留,随机和n个已保留的元素之一交换,有1-n/i的概率舍弃

证明:

1.数学归纳法:

        ①当N=n时,每个样本都选择概率都为n/N,显然成立。

        ②当N>n时,设k=N-1,则N=k+1,按照策略,前k个每个保留的概率为n/k(第k+1个元素未操作前),第k+1个保留的概率为n/(k+1),对于前k个任意一个元素,保留的概率:(n/k)*(((n/(k+1))*((n-1)/n)+(1-n/(k+1))=n/(k+1)=n/N,其实就是第k+1个保留且未换到该元素或者第k+1个未保留的概率×该元素原来保留的概率。

        ③所以当N>=n时,每个样本选择概率都为n/N。

 2.分类推理法:

        按照该策略,对于前n个元素,第i个(i>n)个元素后还保留的概率为(n/i)*((n-1)/n)+(i-n)/i=(i-1)/i

那么到第N个元素还保留的概率:1*(n/(n+1)*((n+1)/(n+2))*...*(N-1)/N=n/N

那么对于第i个元素(i>n)最后保留的概率,(n/i)*(i/(i+1)*...*(N-1)/N=n/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)):# 随机生成一个数r,0 <= r < i+1r = 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)  # 输出蓄水池中的抽样结果

相关文章:

蓄水池算法

题目&#xff1a; 假设有一组数据流元素有 N 个&#xff08;事先不知道 N 具体值&#xff09;&#xff0c;我们希望选择 n 个样本&#xff08;N > n&#xff09;&#xff0c;使用怎样的策略进行抽样可以使得数据流中每个元素被选择的概率恰为 n / N 结论&#xff1a; 创建大…...

作业 day4

完成父子进程通信...

erlang练习题(四)

题目一 传入列表 L1[K|]、L2[V|]、L3[{K,V}|_]&#xff0c;L1和L2一一对应&#xff0c;L1为键列表&#xff0c;L2为值列表&#xff0c;L3为随机kv列表&#xff0c; 将L1和L2对应位合并成KV列表L4&#xff0c;再将L3和L4相加&#xff0c;相同key的value相加 如&#xff1a;L…...

YoloV5实时推理最短的代码

YoloV5实时推理最简单代码 import cv2 import torch# 加载YOLOv5模型 model torch.hub.load(ultralytics/yolov5, yolov5s)# 使用CPU或GPU进行推理 device cuda if torch.cuda.is_available() else cpu model.to(device)# 打开摄像头&#xff08;默认摄像头&#xff09; cap…...

Tensorflow、Pytorch和Ray(张量,计算图)

1.深度学习框架&#xff08;Tensorflow、Pytorch&#xff09; 1.1由来 可以追溯到2016年&#xff0c;当年最著名的事件是alphago战胜人类围棋巅峰柯洁&#xff0c;在那之后&#xff0c;学界普遍认为人工智能已经可以在一些领域超过人类&#xff0c;未来也必将可以在更多领域超过…...

TinyWebServer学习笔记-让程序跑起来

目标&#xff1a;通过这个HTTP项目熟悉网络编程 系统&#xff1a;Ubuntu20.04 首先&#xff0c;学习的第一步就是先让程序跑起来&#xff0c;使用git将项目下载到虚拟机内&#xff1a; git clone https://github.com/qinguoyi/TinyWebServer.git 提前把MySQL数据库安装好&am…...

_tkinter.TclError: no display name and no $DISPLAY environment variable 解决

启动kohya_ss时可能会发生错误&#xff1a; _tkinter.TclError: no display name and no $DISPLAY environment variable 解决办法&#xff1a; 1、apt-get install xvfb //安装xvfb // 启动虚拟显示器 2、Xvfb :99 -screen 0 1024x768x16 & export DISPLAY:99 ps aux…...

我出手了!

时光飞逝&#xff0c;程序员小灰这个微信公众号&#xff0c;已经运营整整7年时间了。 在这7年里&#xff0c;小灰输出过各种各样的文章和视频&#xff0c;有讲编程技术的&#xff0c;有讲职业规划的&#xff0c;有讲互联网行业新闻的&#xff0c;也有讲自己个人生活的。 不过&a…...

springboot的配置文件(properties和yml/yaml)

springboot的配置文件有两种格式分别是properties和yml/yaml 创建配置文件 在创建springboot项目时候&#xff0c;会默认生成application.properties这种格式 书写风格 端口 application.propertis server.port8080 application.yml server:port: 8080 连接数据库 applica…...

SLAM面试笔记(7) — Linux面试题

目录 问题1&#xff1a;Linux系统基本组件&#xff1f; 问题2&#xff1a;Linux和Unix有什么区别&#xff1f; 问题3&#xff1a;Linux下编译程序 问题4&#xff1a;gcc基本格式和常用指令 问题5&#xff1a;用什么命令查找内存和交换使用情况&#xff1f; 问题6&#xf…...

QUIC不是TCP的替代品

QUIC取代了TCP成为HTTP3的基础传输协议&#xff0c;不是因为QUIC能够取代TCP的所有应用场景&#xff0c;而是因为QUIC更适合HTTP的请求/响应业务模型。原文: QUIC Is Not a TCP Replacement TCP新规范(RFC 9293)的发布是网络界的一件大事&#xff0c;值得围绕这一主题发表第二篇…...

计算机竞赛 目标检测-行人车辆检测流量计数

文章目录 前言1\. 目标检测概况1.1 什么是目标检测&#xff1f;1.2 发展阶段 2\. 行人检测2.1 行人检测简介2.2 行人检测技术难点2.3 行人检测实现效果2.4 关键代码-训练过程 最后 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 行人车辆目标检测计数系统 …...

GPT系列模型解读:GPT-1

GPT系列 GPT&#xff08;Generative Pre-trained Transformer&#xff09;是一系列基于Transformer架构的预训练语言模型&#xff0c;由OpenAI开发。以下是GPT系列的主要模型&#xff1a; GPT&#xff1a;GPT-1是于2018年发布的第一个版本&#xff0c;它使用了12个Transformer…...

王杰国庆作业day3

父子进程对话 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <my_head.h> int main(int argc, const char *argv[]) {mkfifo("./fifo1",0664);mkfifo("./fifo2",0664);pid_t cpid fork();if(0 < cp…...

量子计算基础知识—Part1

1.什么是量子计算机&#xff1f; 量子计算机是基于量子力学原理构建的机器&#xff0c;采用了一种新的方法来处理信息&#xff0c;从而使其具有超强的功能。量子计算机使用Qubits处理信息。 2. 什么是量子系统&#xff1f; 一个量子系统指的是由量子力学规则描述和控制的物理…...

【PostgreSQL】【存储管理】表和元组的组织方式

外存管理负责处理数据库与外存介质(PostgreSQL8.4.1版本中只支持磁盘的管理操作)的交互过程。在PostgreSQL中&#xff0c;外存管理由SMGR(主要代码在smgr.c中)提供了对外存的统一接口。SMGR负责统管各种介质管理器&#xff0c;会根据上层的请求选择一个具体的介质管理器进行操作…...

VSCode安装图文详解教程

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl 教程说明 本教程旨在详细介绍VSCode的安装过程及其注意事项。 下载VSCode 请在官方网站 https://code.visualstudio.com/ 下载https://code.visualstudio.com/至本地&…...

vscode 无法打开源文件

以下是c/c插件的intelligense设置情况&#xff1a; 解决办法&#xff1a; 重新安装vsode无用&#xff1b;重新下载mingw64&#xff0c;管用了&#xff01;&#xff08;我猜可能是之前换电脑移植文件的时候导致了部分文件丢失&#xff09;...

1.8.C++项目:仿muduo库实现并发服务器之eventloop模块的设计

项目完整在&#xff1a; 文章目录 一、eventloop模块&#xff1a;进行事件监控&#xff0c;以及事件处理的模块二、提供的功能三、实现思想&#xff08;一&#xff09;功能&#xff08;二&#xff09;意义&#xff08;三&#xff09;功能设计 四、框架五、代码 一、eventloop模…...

Linux基本指令(二)

&#x1f493;博主个人主页:不是笨小孩&#x1f440; ⏩专栏分类:数据结构与算法&#x1f440; C&#x1f440; 刷题专栏&#x1f440; C语言&#x1f440; &#x1f69a;代码仓库:笨小孩的代码库&#x1f440; ⏩社区&#xff1a;不是笨小孩&#x1f440; &#x1f339;欢迎大…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...