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

类的内存对齐位段位图布隆过滤器哈希切割一致性哈希

文章目录

    • 一、类的内存对齐
      • 1.1规则
      • 1.2原因
    • 二、位段
      • 2.1介绍
      • 2.2内存分配问题
      • 2.3跨平台问题
      • 2.4使用的注意事项
    • 三、位图的应用
      • 3.1 给40亿个不重复的无符号整数,找给定的一个数。(int的范围可以到达42亿多)
      • 3.2 给定100亿个整数,设计算法找到只出现一次的整数
      • 3.3给两个文件,分别有100亿个整数,我们只有1G的内存,如何找到两个文件的交集
      • 3.4位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过两次的所有整数
    • 四、布隆过滤器
      • 4.1作用和介绍
      • 4.2误判的概率与什么有关?
      • 4.3布隆过滤器的实现
    • 五、哈希切割
      • 5.1给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?
      • 5.2给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?
    • 六、一致性哈希

在这里插入图片描述

一、类的内存对齐

1.1规则

1.类的第一个成员对齐到和类的起始位置偏移量为0的地址处
2.其他成员变量要对齐到某个数字(对齐数)的整数倍的地址处
对齐数 = 编译器默认的一个对齐数与该成员变量的大小的较小值

——VS中默认对齐数为8
——Linux中gcc没有默认对齐数,对齐数就是成员自身的大小
3.类的总大小为最大对齐数(类中每个成员变量都有一个对齐数,所有对齐数中最大的)的整数倍。
4.如果出现类的嵌套,嵌套的类的成员对齐到自己的成员中最大对齐数的整数倍处

offsetof(type,成员)计算偏移量
在这里插入图片描述
在这里插入图片描述

1.2原因

1.不是所有的硬件平台都能访问任意地址上的任意数据的;某些硬件平台只能在某些地址处取某些特定类型的数据,否则抛出硬件异常
2.数据结构(尤其是栈)应该尽可能的在边界对齐。因为为了访问未对齐的内存,编译器需要进行两次访问,对齐了的内存,编译器只需要进行一次访问。

在这里插入图片描述

二、位段

2.1介绍

在这里插入图片描述

2.2内存分配问题

在这里插入图片描述

2.3跨平台问题

在这里插入图片描述

2.4使用的注意事项

在这里插入图片描述

三、位图的应用

3.1 给40亿个不重复的无符号整数,找给定的一个数。(int的范围可以到达42亿多)

方法1(不可取):用二分的方法,80亿个字节大概需要7.4个G,没有那么大的存储空间,虽然二分的查找效率很高,但是需要数据处于有序的状态
在这里插入图片描述

方法2:位图
我们利用哈希桶的原理,用每一个数映射一个比特位,大概42亿个比特位,加起来应该是0.5个G左右,这样消耗的内存低,并且每一个数映射一个比特位,又保证了查找效率O(1)

在这里插入图片描述
在这里插入图片描述

3.2 给定100亿个整数,设计算法找到只出现一次的整数

用两个位图来表示这个整数出现的次数
在这里插入图片描述

3.3给两个文件,分别有100亿个整数,我们只有1G的内存,如何找到两个文件的交集

同上

3.4位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过两次的所有整数

同上

四、布隆过滤器

4.1作用和介绍

作用:可以提高测试数据在该数据库中是否存在,如果有上千百亿的数据都从数据库中寻找的话,那么效率就会非常非常低,用了布隆过滤器之后,可以排除掉一部分不在数据库里面的数据。
介绍:布隆过滤器就是一个字符串映射多个位,这个可以大大减少误判的可能性,一个字符串映射多个位可以降低误判的可能性,但是此时的空间效率就降低了,布隆过滤器的实质目的就是为了提高空间效率,这样得不偿失,我们只能根据适用情况判断到底映射几个位

4.2误判的概率与什么有关?

1.与映射的哈希函数的个数有关
2.与映射的位有关
3.与哈希函数的特性有关

4.3布隆过滤器的实现

用三种不同的哈希函数进行实现,一共映射3个比特位
在这里插入图片描述
在这里插入图片描述

五、哈希切割

5.1给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?

在这里插入图片描述

5.2给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?

在这里插入图片描述

六、一致性哈希

下面这篇别人讲的文章非常详细,可参考
一致性哈希的文章
在这里插入图片描述

相关文章:

类的内存对齐位段位图布隆过滤器哈希切割一致性哈希

文章目录 一、类的内存对齐1.1规则1.2原因 二、位段2.1介绍2.2内存分配问题2.3跨平台问题2.4使用的注意事项 三、位图的应用3.1 给40亿个不重复的无符号整数,找给定的一个数。(int的范围可以到达42亿多)3.2 给定100亿个整数,设计算…...

于ThinkPHP开发的赛事报名小程序

基于ThinkPHP开发的赛事报名微信小程序 功能包括 1、参赛公告 2、会员中心(会员注册、登录、成绩查询、资料管理、参赛记录管理) 3、个人报名和企业报名 (身份证验证防止重复报名) 4、培训报名 5、查询是否在库人员,根…...

前端学习--React部分

文章目录 前端学习--React部分前言1.React简介1.1React的特点1.2引入文件1.3JSX🍉JSX简介与使用🍉JSX语法规则 1.4模块与组件🍉模块🍉组件 1.5安装开发者工具 2.React面向组件编程2.1创建组件🍉函数式组件&#x1f349…...

24V_2A_1.2MHZ|PCD0303升压恒频LCD背光源专用电路超小体积封装

概述 PCD0303是一个恒定频率,6针SOT23电流模式升压转换器用于小型低功耗应用。PCD0303 以1.2MHz切换,并且允许使用微小的,低成本电容器和电感器2mm或更小,内部软启动会产生较小的涌入电流延长电池寿命。PCD0303具有自动切换至轻负载下的脉冲…...

python生成词云图

生成词云图的话需要先对数据进行分词处理 , 分词方法点击查看 import pandas as pd from collections import Counter from wordcloud import WordCloud import matplotlib.pyplot as plt# 假设您已经按照之前的步骤处理了数据,并且处理后的数据保存在comments_proc…...

【使用ChatGPT构建应用程序】应用程序开发概述:1. 管理秘钥、2. 数据安全、3. 与应用程序解耦、4. 注意提示语的注入攻击

文章目录 一. 首先注意的两个方面1. 管理API密钥1.1. 用户提供API密钥1.2. 你自己提供API密钥 2. 数据安全和数据隐私 二. 软件架构设计原则:与应用程序解耦三. 注意LLM提示语的注入攻击1. 分析输入和输出2. 监控和审计3. 其他要注意的注入情况 在了解了ChatGPT的文…...

【JavaScript脚本宇宙】不可或缺的Web开发工具:图表和可视化

图形化你的数据:六款顶级JavaScript库全接触 前言 在本文中,我们将深入探讨六个强大的JavaScript库,这些库被广泛应用于数据可视化和交互式图形展示。我们将了解每个库的概述、主要特性、使用示例以及使用场景,以帮助读者更全面…...

自然语言处理(NLP)中的迁移学习

Transfer Learning in NLP 迁移学习(Transfer Learning)无疑是目前深度学习中的新热点(相对而言)。在计算机视觉领域,它已经应用了一段时间,人们使用经过训练的模型从庞大的ImageNet数据集中学习特征&…...

PLC集成BL121PO网关优化智能电网的远程管理PLC转OPC UA协议

随着工业自动化技术的不断发展,智能电网等复杂系统对于设备之间高效通信的需求日益增加。PLC转OPC UA协议转换网关BL121PO作为一款领先的协议转换设备,通过其独特的设计和功能,为用户提供了高效、安全的PLC接入OPC UA的解决方案。 设备概述 …...

爬虫案例(读书网)

一.我们还是使用简单的bs4库和lxml,使用xpath: 导入下面的库: import requests from bs4 import BeautifulSoup from lxml import etree 我们可以看见它的div和每个书的div框架,这样会观察会快速提高我们的简单爬取能力。 二.实…...

Linux系统编程(五)多线程创建与退出

目录 一、基本知识点二、线程的编译三、 线程相关函数1. 线程的创建(1)整型的传入与接收(2)浮点数的传入与接收(3)字符串的传入与接收(4)结构体的传入与接收 2. 线程的退出3. 线程的…...

计算机毕业设计 | SpringBoot个人博客管理系统(附源码)

1,绪论 1.1 背景调研 在互联网飞速发展的今天,互联网已经成为人们快速获取、发布和传递信息的重要渠道,它在人们政治、经济、生活等各个方面发挥着重要的作用。互联网上发布信息主要是通过网站来实现的,获取信息也是要在互联网中…...

字母的大小写转换

自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 在Python中,字符串对象提供了lower()方法和upper()方法进行字母的大小写转换,即可用于将大写字母转换为小写字母或者将小写字…...

JTW结构

JTW(JSON Web Token)的结构 在这篇笔记中,我们将了解JTW(JSON Web Token)的结构。我们将看到JTW是如何创建的,令牌的各个部分是什么,以及您如何自己构建和构造JTW。您还将了解一些这种结构的含义,以及使用JTW进行授权时的一些结果优缺点。 基本上,JTW本质上就是一个…...

debian11安装留档@VirtualBox

因为debian12无法安装tpot,所以又把11重新安装一遍,以前的安装文档:安装Debian 11 留档-CSDN博客 下载光盘 华为云地址:https://repo.huaweicloud.com/debian-cd/11.0.0/amd64/iso-cd/ 使用了debian11 教育版,比较有…...

SpringBoot——整合Thymeleaf模板

目录 模板引擎 新建一个SpringBoot项目 pom.xml application.properties Book BookController bookList.html ​编辑 项目总结 模板引擎 模板引擎是为了用户界面与业务数据分离而产生的,可以生成特定格式的页面在Java中,主要的模板引擎有JSP&…...

电商推荐系统+电影推荐系统【虚拟机镜像分享】

电商推荐系统电影推荐系统【虚拟机镜像分享】 所有组件部署好的镜像下载(在下面),仅供参考学习。(百度网盘,阿里云盘…) 博主通过学习尚硅谷电商推荐电影推荐项目,将部署好的虚拟机打包成ovf文…...

(函数)判断素数(C语言)

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>//声明素数判断函数&#xff1b; void prime(int number);int main() {//初始化变量值&#xff1b;int number 0;//获取用户输入的数据&#xff1b;printf(&quo…...

git 学习随笔

git 学习随笔 基本概念 git 对待数据类似快照流的形式而不是类似 cvs 那样的纪录文件随时间逐步积累的差异 git 中所有数据在存储钱都会计算校验和&#xff08;hash) 三种状态&#xff1a;已提交(committed)&#xff0c;已修改(modified)&#xff0c;已暂存(staged)。 add…...

【因果推断python】1_因果关系初步1

目录 为什么需要关心因果关系&#xff1f; 回答不同类型的问题 当关联确实是因果时 为什么需要关心因果关系&#xff1f; 首先&#xff0c;您可能想知道&#xff1a;它对我有什么好处&#xff1f;下面的文字就将围绕“它”展开&#xff1a; 回答不同类型的问题 机器学习目…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...