【数据结构】哈希应用-海量数据处理

目录

1、10亿个整数里面求最大的100个

2、求大文件交集

3、查找出现次数前210的ip地址


1、10亿个整数里面求最大的100个

经典的tok问题,可以使用堆来解决

2、求大文件交集

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

这里的query是查询,理解为字符串即可,所以不能使用位图

分析:假设平均每个query字符串50byte,100亿个query就是5000亿byte,约等于500G(1G 约等于 10亿多Byte)
哈希表/红⿊树等数据结构肯定是⽆能为⼒的

法一:使用布隆过滤器,⼀个⽂件中的query放进布隆过滤器,另⼀个⽂件依次查找,在的就是交集。此时在交集中的query一定能被找到,但找出来的并不一定是交集,因为存在误判
法二:使用哈希切分

⾸先内存的访问速度远⼤于硬盘,⼤⽂件放到内存搞不定,那么我们可以考虑切分为小文件,再放进内存处理

因为这一个大文件的大小大约是500G,所以可以将一个大文件切分成1000个小文件,这样就可以让小文件一个是500MB。将大文件A平均切分成A1,...,A999这1000个文件,大文件B平均切分成B1,...,B999这1000个文件,此时再将A1与大文件B切分出来的1000个文件比较,如何A2,...,A999一样,时间复杂度是O(N^2),时间复杂度太高了

此时可以使用哈希切分。

先将大文件A和B里面的query映射为整数,根据映射的值放进小文件中,每次只比较一组Ai和Bi,相同的就是交集。时间复杂度是O(N)。

此时会有一个问题,就是现在并不是平均切分,所以每个小文件的大小是不确定的,如果有某一组小文件Ai和Bi之和的大小大于1G了,要如何处理呢?此时就需要就行二次切分,将过大的这一组Ai和Bi重新映射到新的小文件中。此时可以解决大部分情况,但是假如Ai有5G,其中有4G都是同一个query,这样二次切分是解决不了的,所以我们不能用Ai和Bi之和的大小来判断是否需要二次切分,因为这里面太大可能是因为重复的query造成的,而找交集并不需要重复元素,并且哈希表和红黑树都是不允许数据冗余的。所以,我们不管Ai和Bi的和是多大,直接将其往哈希表或者红黑树中放,当哈希表或者红黑树的大小大于1G了,此时再进行二次切分,因为此时一定不是由于重复的query造成的内存太大

3、查找出现次数前10的ip地址

给⼀个超过100G⼤⼩的log file, log中存着ip地址, 设计算法找到出现次数最多的ip地址?查找出现次数前10的ip地址

本题的思路跟上题完全类似,依次读取⽂件A中ip,i = HashFunc(ip)%500,ip放进Ai号⼩⽂件(这样小文件中的就是相同的ip或冲突的ip),然后依次⽤map<string, int>对每个Ai⼩⽂件统计ip次数,同时求出现次数最多的ip或者topk ip。本质是相同的ip在哈希切分过程中,⼀定进⼊的同⼀个⼩⽂件Ai,不可能出现同⼀个ip进⼊Ai和Aj的情况,所以对Ai进⾏统计次数就是准确的ip次数
注意:这里是模500,不是一定要像上一题一样模1000,上一题是为了让一个小文件大概是500MB

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/395283.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何用 CocosCreator 对接抖音小游戏的侧边栏复访

前言 最近小游戏的软著下来了&#xff0c;用 CocosCreator 做的游戏也完成了 1.0 版本。而当我打包成抖音小游戏进行提交时&#xff0c;还没到初审就给拒了&#xff0c;因为还有一个机审&#xff0c;机器检测到代码中没有接入 “侧边栏复访功能”。这个我还真不知道&#xff0…

不要问人工智能能为你做什么,而要问你能用人工智能实现什么?

​新前沿 欢迎来到雲闪世界。在过去的一年半里&#xff0c;我一直在向我认识的每个人讲述人工智能的潜力&#xff0c;尤其是大型语言模型 (LLM)。无论技术背景如何&#xff0c;现在是时候让每个人学习 LLM 的基础知识以及如何有效地使用它们了。 20 世纪 60 年代&#xff0c;我…

美国服务器稳定么?影响服务器稳定性的6个因素

美国服务器稳定么&#xff1f;美国服务器的稳定性是相当不错的&#xff0c;这主要得益于其先进的技术、成熟的基础设施以及严格的管理措施。美国拥有众多知名的服务器提供商&#xff0c;这些提供商通常会采用顶级的硬件设施&#xff0c;如英特尔、AMD等知名品牌的处理器&#x…

以树莓集团的视角:探索AI技术如何重塑数字媒体产业发展

在科技日新月异的今天&#xff0c;AI技术如同一股不可阻挡的潮流&#xff0c;正深刻改变着我们的世界&#xff0c;尤其是数字媒体产业发展。作为数字产业生态链的杰出建设者&#xff0c;树莓集团始终站在时代前沿&#xff0c;积极探索AI技术如何为数字媒体产业注入新活力。 在树…

NFTScan 正式上线 Gravity NFTScan 浏览器和 NFT API 数据服务

2024 年 8 月 9 号&#xff0c;NFTScan 团队正式对外发布了 Gravity NFTScan 浏览器&#xff0c;将为 Gravity 生态的 NFT 开发者和用户提供简洁高效的 NFT 数据搜索查询服务。NFTScan 作为全球领先的 NFT 数据基础设施服务商&#xff0c;Gravity 是继 Bitcoin、Ethereum、BNBC…

修改nacos实力权重或者对某实例下线报错

在Nacos控制台进行上述操作&#xff0c;错误信息 caused: errCode: 500, errMsg: do metadata operation failed ;caused: com.alibaba.nacos.consistency.exception.ConsistencyException: The Raft Group [naming_instance_metadata] did not find the Leader node;caused:…

IIS部署Linux环境下的cer证书步骤

1. 获取Linux环境的cer证书 Linux环境下的cer证书位于&#xff1a;root/.acme.sh 下&#xff0c;下载到Windows服务器。 2. 将cer证书转为pfx证书 IIS导入证书的时候只支持pfx格式证书&#xff0c;所以需要转换一下&#xff0c;确保Windows服务器上已安装openssl工具&#x…

GD 32 IIC通信协议

前言&#xff1a; ... 通信方式 通信方式分为串行通信和并行通信。常见的串口就是串行通信的方式 常用的串行通信接口 常用的串行通信方式有USART,IIC,USB,CAN总线 同步与异步 同步通信&#xff1a;IIC是同步通信&#xff0c;有两个线一个是时钟信号线&#xff0c;一个数数据…

【工具类】JAVA (Android Studio )+ JS 加密解密 AES + Base 64

JAVA &#xff08;Android Studio &#xff09; JS 加密解密 AES Base 64 前言JAVA 代码&#xff08;解密&#xff09;JS代码&#xff08;加密&#xff09; 前言 整个过程&#xff1a; JS 接口先用AES加密&#xff0c;然后加密内容转Base64 编码&#xff1b;JAVA进行Base64解…

三十二、【人工智能】【机器学习】【监督学习】- XGBoost算法模型

系列文章目录 第一章 【机器学习】初识机器学习 第二章 【机器学习】【监督学习】- 逻辑回归算法 (Logistic Regression) 第三章 【机器学习】【监督学习】- 支持向量机 (SVM) 第四章【机器学习】【监督学习】- K-近邻算法 (K-NN) 第五章【机器学习】【监督学习】- 决策树…

将PPT中的元素保存为高清图片

PPT制作流程图&#xff0c;思维导图或者演示图片非常方便&#xff0c;本文主要记录如何将一个在PPT中画好的图片导出为高清图片。 1.在ppt中设计图片 以我在PPT中画的图片为例&#xff0c;将所有元素选中&#xff0c;右键组合&#xff0c;成为一个整体 2.另存为增强型元文件 …

vscode 快速生成vue 格式

1.用快捷Ctrl Shift P唤出控制台 输入“Snippets”并选择 Snippets: Configure User Snippets 2.输入vue&#xff0c;选中vue.json vs code自动生成vue.json文件 3.在 vue.json 中添加模板 {"Print to console": {"prefix": "vue2","b…

AI大语言模型对消防工程知多少?

在过去2年的时间里&#xff0c;大语言模型受到前所未有的关注。ChatGPT的出现更是让人工智能对话风靡一时。我们不再把搜索引擎当作求解问题的唯一途径&#xff0c;AI聊天成为了当前最受欢迎的问题求助工具。 让ChatGPT用通俗的语言解释什么是ChatGPT 什么是大语言模型&#x…

如何看待“低代码”开发平台的兴起

目录 1.概述 1.1.机遇 1.2.挑战 1.3.对开发者工作方式的影响 2.技术概览 2.1.主要特点 2.2.市场现状 2.3.主流低代码平台 2.4.分析 3.效率与质量的权衡 3.1.提高开发效率 3.2.质量与安全隐患 3.3.企业应用开发的利弊分析 4.挑战与机遇 4.1.机遇 4.2.挑战 4.3.…

PHP相关漏洞

一、PHP漏洞原理 1.PHP命令执行漏洞 PHP应用程序有时需要调用一些执行系统命令的函数&#xff0c;如php中的system&#xff0c;exec&#xff0c;shell exec&#xff0c;passthru&#xff0c;popen等&#xff0c;当用户可以控制这些函数的参数时&#xff0c;就可以将恶意系统命…

xlua使用

1. 安装 到 github 移动三个文件夹过去即可 Assets -》Plugins Assets -》Xlua Tools 移动到 unity里面的Assets目录即可 会在工具栏出现Xlua即安装成功 2. 引入基础类 ABMgr.cs using System.Collections; using System.Collections.Generic; using UnityEngine; using Un…

【数据结构之带头双向循环链表的实现】

1.链表的分类 链表的结构有多种多样&#xff0c;以下情况组合起来就有8种&#xff08;2x2x2&#xff09;链表结构&#xff1a; 虽然有这么多的链表结构&#xff0c;但是我们实际中最常用的还是两种结构&#xff1a;单链表和双向带头循环链表。 无头单向非循环链表&#xff1a;结…

C#TreeView控件应用

1、代码 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.IO; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Windows.Forms;namespace TestApp…

IoTDB 入门教程 基础篇②——IoTDB 企业版比开源版本值在哪?

文章目录 一、前文二、功能对比三、可视化控制台四、白名单五、审计日志六、数据备份七、机器学习八、总结 一、前文 IoTDB入门教程——导读 二、功能对比 由天谋科技官网得知&#xff0c;IoTDB&#xff08;开源版&#xff09;与TimechoDB&#xff08;企业版&#xff09;的功能…

10+ Midjourney V6.1 提示:生成精美的角色海报

前言 近期图像生成界最大的更新是MidjourneyV6.1&#xff01;我迫不及待地想要开始创作和分享&#xff0c;这次分享的重点是V6.1在角色创作方面的增强。 以下是半天测试的结果&#xff0c;包括提示&#xff0c;专注于角色摄影照片和角色插图。 网上关于这方面的教程虽然很多&…