首页 > 系统相关 >有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词

有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词

时间:2023-12-13 13:12:27浏览次数:31  
标签:文件 hash 每个 16 单词 1G 大小 1M

计算:
所以我们要按照1M的上限来计算,假设每个单词都为16个字节,那么1M的内存可以处理多少个单词呢?
1M = 1024 KB = 1024 * 1024 B 。然后1M / 16B = 2^16个单词
1G大概有多少个单词呢? 有2^26个单词
但是实际中远远不止这些,因为我们是按照最大单词长度算的。

我们需要把这1G的单词分批处理,根据上面的计算,可以分成大于2^10个文件。

索性就分成2000个文件吧,怎么分呢,不能随便分,不能简单的按照单词的顺序然后模2000划分,因为这样有可能相同的单词被划分到不同的文件中去了。

分而治之/hash映射:顺序读文件中,对于每个词x,取hash(x)%2000,然后按照该值存到2000个小文件(记为x0,x1,…x1999)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。
hash_map统计:对每个小文件,采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。
然后呢,我们对每个文件进行分别处理:按照key-value的方法处理每个单词,最终得出每个文件中包含每个单词和单词出现的次数。然后再建立大小为100的小根堆。一次遍历文件进行处理。

标签:文件,hash,每个,16,单词,1G,大小,1M
From: https://www.cnblogs.com/guoyu1/p/17898825.html

相关文章

  • Navicat16.1链接SQL server失败
    问题:[IM002][Microsoft][ODBC驱动程序管理器]未发现数据源名称并目未指定默认驱动程序(0) 解决办法:找到本地Navicat安装目录,搜索*.msi,双击进行安装(无脑安装)。安装成功后再去Navicat测试链接,应该就可以了。 ......
  • WSL更新失败(退出代码: 1603) - Error code: Wsl/CallMsi/E_ABORT
    Whathappened?WSL莫名其妙的更新了,完成更新以后莫名奇妙地启动不起来了。每次运行WSL的时候都会给我提示WSL正在完成升级...更新失败(退出代码:1603)。Errorcode:Wsl/CallMsi/E_ABORT抓耳挠腮找了半天,我甚至不管写了一半的代码和笔记,把WSL卸载后重装,结果居然无法启动......
  • CF1610H Squid Game
    题意给定一棵树,以及\(m\)条路径。让你选出最少的点,使得对于每一条路径,都有一个点距离链上的点离端点更近。Sol考虑将每一条路径分为直链和曲链考虑。注意到所有的曲链最多对答案有\(1\)的贡献。考虑直链的情况。注意到一个很显然的东西。对于一个选择的点,如果她的上方......
  • 16、Model_View_Delegate
    QT当中model-view-delegate(模型-视图-代理),此结构实现数据和界面的分离。Qt的模型-视图结构分为三部分:模型(model)-视图(view)-代理(Delegate)。其中模型与数据源通信;并为其它部件提供接口;视图从模型中引用数据条目的模型索引(ModelIndex)。在视图当中,代理负责绘制数据条目,比......
  • [CF1603E] A Perfect Problem
    APerfectProblem题面翻译一个序列是好的当且仅当集合最大值乘上集合最小值大于等于集合元素的加和;一个序列是完美的,当且仅当这个序列的任何子序列都是好的(包括自己不包括空集);你要求的是:长度为\(n\)的并且每一个元素都大于等于\(1\)并且小于等于\(n+1\)的完美序列的......
  • 用「傲梅轻松备份」克隆磁盘,并保持分区大小一致
    两个容量不同的磁盘(如931G和953G)进行对拷,如下图(例如将磁盘2中克隆到磁盘1),会造成原始磁盘中的分区大小在新磁盘中发生变化。为使两个硬盘中的分区尽量保持一致,可以考虑「逐个分区」进行备份。这样可以实现仅最后一个分区的大小不同。一、删除目标磁盘的所有分区备份目标磁盘......
  • css自适应文本大小
    div{width:500px;height:600px;resize:both;//可拖动方向overflow:hidden;padding:15px;background-color:red;container-type:size;//对}divp{//cqw表示根据container-type所选择的宽度作为参照,3cqw表示为500*0.03,//cqh表示根据container......
  • 1688订单详情对接及实现方案
    一、引言1688作为中国最大的B2B电子商务平台之一,提供了丰富的商品信息和订单详情。通过与1688订单详情接口的对接,电商企业可以实时获取订单详细信息,以便更好地了解客户需求、优化运营策略以及提高服务质量。本文将详细介绍如何实现1688订单详情的对接,包括注册与获取API密钥、环境准......
  • [ARC169E] Avoid Boring Matches
    题解链接非常厉害的一道题。考虑无解是什么情况?R的个数超过\(2^{n-1}\)先考虑如何判定。从前往后考虑,如果遇到一个B,那么如果后面有R,就选最靠前的R,否则选最靠后的一个B.如果遇到R,就选最靠后的一个B。但是这个判定很繁琐。我们考虑求出一个合法序列,使得他的B尽量靠后......
  • AtCoder Regular Contest 169
    A-PleaseSign某个\(A_i\)对\(A_1\)的贡献是\(\binom{10^{100}}{\mathrm{dep}_i}\),所以深度为\(d\)的节点的\(A_i\)之和只要不为\(0\),其贡献就一定远大于深度\(<d\)的所有点的贡献之和。从大到小找到第一个和非零的深度即可。B-SubsegmentswithSmallSums直......