当前位置: 首页 > 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;欢迎大…...

单一模型可能涌现不出超级智能,但 Agent 协作体却极有可能。

当 AI 把产品能力拉齐&#xff0c;注意力才是唯一的护城河 你有没有这种感觉&#xff1f;2025 年底&#xff0c;用 AI 一键生成一个完整 App 已经不是什么新闻&#xff0c;Vibe Coding 让普通开发者一天就能上线一个产品。可产品做出来了&#xff0c;下载量却像石沉大海&#x…...

Stable Diffusion像素艺术工作站:Pixel Fashion Atelier支持LoRA在线热切换

Stable Diffusion像素艺术工作站&#xff1a;Pixel Fashion Atelier支持LoRA在线热切换 1. 像素时装锻造坊简介 Pixel Fashion Atelier是一款基于Stable Diffusion与Anything-v5的图像生成工作站&#xff0c;专为像素艺术创作而设计。与传统AI工具不同&#xff0c;它采用了复…...

STM32危化品智能管理系统设计与实现

## 1. 项目概述### 1.1 系统背景 实验室危化品管理面临传统人工记录方式效率低下、易出错等问题&#xff0c;特别是在温湿度敏感、易燃易爆或有毒危化品的存储过程中存在重大安全隐患。基于STM32F103C8T6微控制器的智能管理系统通过集成多参数传感、无线通信和云平台技术&#…...

百川2-13B模型安全测试:OpenClaw在防御恶意指令方面的表现

百川2-13B模型安全测试&#xff1a;OpenClaw在防御恶意指令方面的表现 1. 为什么需要测试AI助手的安全性 去年我在本地部署了一个自动化助手&#xff0c;本想让它帮我整理文档和收发邮件。结果有次不小心让它执行了一个包含rm -rf的命令&#xff0c;差点把工作目录清空。这次…...

告别蓝牙!用STM32F103和NRF24L01搭建低成本2.4G无线通信,实测传输距离与稳定性

STM32F103与NRF24L01构建高性能2.4G私有通信系统实战指南 在物联网设备爆发式增长的今天&#xff0c;无线通信模块的选择成为硬件开发者面临的首要难题。面对市面上琳琅满目的蓝牙、Wi-Fi和私有协议模块&#xff0c;如何根据项目需求选择最具性价比的解决方案&#xff1f;本文将…...

驾驭AI引用:Geo优化中的内容评分机制与实战策略深度解析

在生成式人工智能&#xff08;Generative AI&#xff09;日益主导信息获取与分发路径的时代&#xff0c;传统搜索引擎优化&#xff08;SEO&#xff09;的范式正被生成式引擎优化&#xff08;Geo&#xff09;所颠覆。Geo不再仅仅关注关键词排名&#xff0c;而是深入探究内容如何…...

别再只懂概念了!用JSEncrypt库5分钟搞定前端RSA密码加密实战

前端RSA加密实战&#xff1a;用JSEncrypt保护用户密码传输安全 1. 为什么前端需要加密&#xff1f; 在Web应用开发中&#xff0c;用户登录是最基础也最敏感的操作之一。传统表单提交直接将密码以明文形式发送到服务器&#xff0c;这在网络传输过程中存在被截获的风险。即使使…...

深度学习模型压缩:从原理到实践

深度学习模型压缩&#xff1a;从原理到实践 1. 背景与动机 深度学习模型在各种任务上取得了显著的性能提升&#xff0c;但随之而来的是模型规模的不断增长。大型模型虽然性能优异&#xff0c;但也带来了以下问题&#xff1a; 存储需求大&#xff1a;大型模型需要大量存储空间&a…...

基于spring和vue的企业原材料库存盘点食品厂管理系统

目录技术选型与架构设计核心功能模块划分数据库设计要点关键技术实现前端交互优化系统安全措施测试与部署方案扩展性设计项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作技术选型与架构设计 后端采用Spring Boot框架&#xff0…...

C++ sort函数进阶指南:如何优雅地自定义结构体排序规则

C sort函数进阶指南&#xff1a;如何优雅地自定义结构体排序规则 在C开发中&#xff0c;数据排序是一个永恒的话题。当我们需要处理复杂数据结构时&#xff0c;标准库提供的默认排序方式往往无法满足需求。这时&#xff0c;掌握sort函数的高级用法就显得尤为重要。本文将深入探…...