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

[算法总结] - 蓄水池采样算法

问题描述

在长度为N的数组中,随机等概率选取K个元素,如何实现这个随机算法。 思路很简单,生成一个[0, N]的随机数index,然后返回index上的数值即可。

但是,如果输入是一个长度未知的数组比如stream,先遍历得到数组大小,在遍历进行K次采样显然不够高效,这就引出了蓄水池算法。

  • 蓄水池采样算法可以在一次遍历中得到K次采样结果并且保证等概率
  • N个样本 K次采样每一个元素被pick的概率是 k/N

实现方式为如下步骤:

  1. 构建一个长度为K的数组(蓄水池),保存采样结果
  2. 将数组[0, k]数值,赋值给蓄水池数组
  3. 遍历剩下[k+1, N],每一次迭代中产生一个[0, i), i\epsilon \left [k+1, N \right ] 的index, 如果index < K那么将原来处在该index的结果覆盖掉。以此类推
  4. 最后返回蓄水池数组结果

代码如下:

Leetcode 398. random pick index

class Solution {int[] reservior;Random rand = new Random();int[] copy;public Solution(int[] nums) {// 本题目只需要选取一个样本 k = 1copy = nums;reservior = new int[1];reservior[0] = -1;}public int pick(int target) {int cnt = 0;for (int i=0; i<copy.length; i++) {if (copy[i]==target) {cnt++;int randNum = rand.nextInt(cnt);if (randNum<=0) {reservior[0] = i;}}}return reservior[0];}
}

时间复杂度:O(N);空间复杂度:O(1)

数学原理

上述步骤中最难理解无非就是第三步,为什么这样做就可以实现每一个元素被选的概率是k/N。

对于 i < k 的元素, 在 k 步之前,他们被选中是没有随机性的 p = 100%;

  • 在 k+1 步时,被第k+1个元素替代的概率 = (k+1)元素被选中的概率 * i 这个index被选中的概率,根据上面实现,第 i 个index被选中概率为 1/k (Java中random.nextInt是左闭右开),而 k+1个元素被选中的概率为 k/k+1(random生成的随机数小于k都为选中) 
    • 被第k+1个元素替代的概率 = \frac{k}{k+1} \times \frac{1}{k} = \frac{1}{k+1}
    • 那么反过来第i个元素被保留的概率为 \frac{k}{k+1}
  • 那么在 N 步,第 i 个元素被保留的概率应该为:
    • k+1步被保留的概率 * k+2步被保留的概率 * ... * N步被保留的概率
    • 也就是 \frac{k}{k+1} \times \frac{k+1}{k+2} \times ... \times \frac{N-1}{N} = \frac{k}{N} 

对于 i >= k 的元素,在k步之前,是没有概率的因为不存在

  • 在 k+1步,第k+1个元素被选中的概率为 \frac{k}{k+1} ,由于第 k+1的元素原本不存在,没有先置概率。
  • 在 k+2步,第k+1个元素被保留的概率= 第k+1步被选中概率 * 第k+2步没有选中第k+2个元素的概率
    • 第k+1个元素被保留的概率 = \frac{k}{k+1} \times \frac{k+1}{k+2} = \frac{k}{k+2}
  • 在 N 步,第k+1个元素被保留的概率 = \frac{k}{k+1} \times \frac{k+1}{k+2} \times ... \times \frac{N-1}{N}= \frac{k}{N}

有几点细节需要留意

  1. 所有的数值,只有一次选中的机会,就是数组遍历到那个index的时候,如果没有被选中,那么以后再也没有机会被重新选中。只有当时被选中才有保留的机会 
    1. [0, k]的元素第一次被选中概率为 100%
    2. [k+1, N]的元素第一次被选中概率为 \frac{k}{M} 
  2. 不管数组中那个元素只要被选中,保留到最后作为返回值的概率都是 \frac{k}{N}

相关文章:

[算法总结] - 蓄水池采样算法

问题描述 在长度为N的数组中&#xff0c;随机等概率选取K个元素&#xff0c;如何实现这个随机算法。 思路很简单&#xff0c;生成一个[0, N]的随机数index&#xff0c;然后返回index上的数值即可。 但是&#xff0c;如果输入是一个长度未知的数组比如stream&#xff0c;先遍历…...

【Dockerfile】将自己的项目构建成镜像部署运行

目录 1.Dockerfile 2.镜像结构 3.Dockerfile语法 4.构建Java项目 5.基于Java8构建项目 1.Dockerfile 常见的镜像在DockerHub就能找到&#xff0c;但是我们自己写的项目就必须自己构建镜像了。 而要自定义镜像&#xff0c;就必须先了解镜像的结构才行。 2.镜像结构 镜…...

flink和机器学习模型的常用组合方式

背景 flink是一个低延迟高吞吐的系统&#xff0c;每秒处理的数据量高达数百万&#xff0c;而机器模型一般比较笨重&#xff0c;虽然功能强大&#xff0c;但是qps一般都比较低&#xff0c;日常工作中&#xff0c;我们一般是如何把flink和机器学习模型组合起来一起使用呢? fli…...

自动驾驶学习笔记(十二)——定位技术

#Apollo开发者# 学习课程的传送门如下&#xff0c;当您也准备学习自动驾驶时&#xff0c;可以和我一同前往&#xff1a; 《自动驾驶新人之旅》免费课程—> 传送门 《Apollo Beta宣讲和线下沙龙》免费报名—>传送门 文章目录 前言 卫星定位 RTK定位 IMU定位 GNSS定…...

【MySQL系列】PolarDB入门使用

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

第二节HarmonyOS DevEco Studio创建项目以及界面认识

一、创建项目 如果你是首次打开DevEco Studio&#xff0c;那么首先会进入欢迎页。 在欢迎页中单击Create Project&#xff0c;进入项目创建页面。 选择‘Application’&#xff0c;然后选择‘Empty Ability’&#xff0c;单击‘Next’进入工程配置页。 配置页中&#xff0c;详…...

网页设计--第5次课后作业

1、快速学习JavaScript的基本知识第11-14章 JavaScript入门 - 绿叶学习网 2、使用所学的知识完成以下练习。 1&#xff09;点击 “点亮”按钮 点亮灯泡&#xff0c;点击“熄灭”按钮 熄灭灯泡 2&#xff09;输入框鼠标聚焦后&#xff0c;展示小写&#xff1b;鼠标离焦后…...

Spring Cache框架,实现了基于注解的缓存功能。

个人简介&#xff1a;Java领域新星创作者&#xff1b;阿里云技术博主、星级博主、专家博主&#xff1b;正在Java学习的路上摸爬滚打&#xff0c;记录学习的过程~ 个人主页&#xff1a;.29.的博客 学习社区&#xff1a;进去逛一逛~ Spring Cache框架 简介Spring Cache 环境准备S…...

CSS-鼠标属性篇

属性名&#xff1a;cursor 功能&#xff1a;设置鼠标光标的样式 属性值&#xff1a; pointer&#xff1a;小手move&#xff1a;移动图标text&#xff1a;文字选择器crosshair&#xff1a;十字架wait&#xff1a;等待help&#xff1a;帮助 eg.html{ cursor: wait;}(此处使用css改…...

Fiddler弱网测试究竟该怎么做?

前言 使用Fiddler对手机App应用进行抓包&#xff0c;可以对App接口进行测试&#xff0c;也可以了解App传输中流量使用及请求响应情况&#xff0c;从而测试数据传输过程中流量使用的是否合理。 抓包过程&#xff1a; 1、Fiddler设置 1&#xff09;启动Fiddler->Tools->…...

蓝桥杯-平方和(599)

【题目】平方和 【通过测试】代码 import java.util.Scanner; import java.util.ArrayList; import java.util.List; // 1:无需package // 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);//在此…...

从零构建属于自己的GPT系列1:预处理模块(逐行代码解读)、文本tokenizer化

1 训练数据 在本任务的训练数据中&#xff0c;我选择了金庸的15本小说&#xff0c;全部都是txt文件 数据打开后的样子 数据预处理需要做的事情就是使用huggingface的transformers包的tokenizer模块&#xff0c;将文本转化为token 最后生成的文件就是train_novel.pkl文件&a…...

STM32内存介绍

ROM是一种只读存储器&#xff0c;经历了从NOR Flash到NAND Flash再到现在的eMMC的发展。为了便于使用和大批量生产&#xff0c;ROM进一步分为了4种类型&#xff1a;PROM、EPROM、EEPROM和Flash。PROM只能被编程一次&#xff0c;EPROM可擦写可编程且可达1000次&#xff0c;EEPRO…...

Qt::Window 、Qt::Tool是 Qt 框架中的一个窗口标志(Window Flag),用于指定窗口的类型和行为

Qt::Window Qt::Window 是 Qt 框架中的一个窗口标志&#xff08;Window Flag&#xff09;&#xff0c;用于指定窗口的类型和行为。 在 Qt 中&#xff0c;窗口标志用于控制窗口的外观、行为和交互方式。通过使用不同的窗口标志组合&#xff0c;可以定制窗口的特性&#xff0c;…...

东胜物流软件 SQL注入漏洞复现

0x01 产品简介 东胜物流软件是一款致力于为客户提供IT支撑的 SOP&#xff0c; 帮助客户大幅提高工作效率&#xff0c;降低各个环节潜在风险的物流软件。 0x02 漏洞概述 东胜物流软件 TCodeVoynoAdapter.aspx、/TruckMng/MsWlDriver/GetDataList、/MvcShipping/MsBaseInfo/Sav…...

第1章 爬虫基础

目录 1. HTTP 基本原理1.1 URI 和 URL1.2 HTTP 和 HTTPS1.3 请求1.3.1 请求方法1.3.2 请求的网址1.3.3 请求头1.3.4 请求体 1.4 响应1.4.1 响应状态码1.4.2 响应头1.4.3 响应体 2. Web 网页基础2.1 网页的组成2.1.1 HTML2.1.2 CSS2.1.3 JavaScript 2.2 网页的结构2.3 节点树及节…...

Python教程---序列--序列修改元素

下面和大家讲一下如何进行序列修改元素。 序列修改元素可以进行两个操作。如下: 方法1:通过下标元素来修改 方法2:通过del来删除元素 # 创建一个原始的列表 stus [张三,李四,王五,赵六,王麻子,小红]#通过下标来直接修改元素中的内容 stus[0] 张三123 stus[2] 哈哈#通过d…...

Linux 中的 ls 命令使用教程

目录 前言 如何运用 ls 命令 1、列出带有所有权的文件和目录 2、获取以人类可读的方式显示的信息 3、列出隐藏文件 4、递归列出文件 5、在使用 ls 时对文件和目录做区分 6、列出指定扩展名的文件 7、基于大小对输出内容排序 8、根据日期和时间排序文件 让我们来总结…...

Kubernetes基础入门:Kubernetes的有关概述

Kubernetes基础入门&#xff1a;Kubernetes的有关概述 一、摘要二、为什么需要 Kubernetes&#xff1f;三、Kubernetes 的功能架构 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; 一、摘要 随着云计算和容器技术的快速发展&#xff0c;现代…...

C# 无法将“int[]“类型隐式转换为“int?[]“,无法将“string[]“类型隐式转换为“string?[]“

在 C# 中&#xff0c;不能将 int[] 隐式转换为 int?[]&#xff0c;因为它们是两种不同的类型。int[] 是一个整数数组&#xff0c;而 int?[] 是一个可空整数数组。要解决这个问题&#xff0c;你可以使用显式转换或创建一个新的可空整数数组。 两种解决方案供大家选择 // 示例…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...