海量数据处理思路「建议收藏」

海量数据处理思路「建议收藏」海量数据处理思路海量数据处理海量数据,不能一次加载到内存中海量数据topK(最大和最小k个数),第k大,第k小的数海量数据判断一个整数是否存在其中海量数据找出不重复的数字找出A,B两个海量url文件中共同的url海量数据topK最大K使用最小堆,最小K使用最大堆,这里以最大K为例海量数据hash分块维护最小堆的K个数据的数据容器堆中数据是topK大的数据,堆顶的数据是第K大数据先将海量数据hash再取模m,分成m个小文件,hash(num)%m,也可以直接取模在

大家好,又见面了,我是你们的朋友全栈君。

海量数据处理思路


海量数据处理

海量数据,不能一次加载到内存中

  • 海量数据topK(最大和最小k个数),第k大,第k小的数
  • 海量数据判断一个整数是否存在其中
  • 海量数据找出不重复的数字
  • 找出A,B两个海量url文件中共同的url

海量数据topK

最大K使用最小堆,最小K使用最大堆,这里以最大K为例

  • 海量数据hash分块
  • 维护最小堆的K个数据的数据容器
  • 堆中数据是topK大的数据,堆顶的数据是第K大数据
  1. 先将海量数据hash再取模m,分成m个小文件,hash(num)%m,也可以直接取模
  2. 在每个小文件中维护K个数据的最小堆,堆顶是当前堆中的最小值
  3. 遍历每个小文件中剩余的数据,与堆顶的数据进行比较,更新最小堆中的数据
  4. 生成m * K个数据,然后对这些数据再进行排序,或者再次通过维护最小堆

变形

  1. 第K大不只是topK,此时堆顶数据即是
  2. 只求最大或最小
  3. 海量数据不仅仅是整数,也可以是字符串
  4. 海量数据按照出现的次数或者频率排序,topK
  • 海量数据按照出现的次数或者频率排序,topK
  1. 先将海量数据hash再取模m,分成m个小文件,hash(num)%m
  2. 扫描每个小文件的数据,通过hash_map建立值和频率的键值对
  3. 以出现的频率维护最小堆的K个数据的数据容器
  4. 遍历每个小文件中剩余的数据,与堆顶的数据进行比较,更新最小堆中的数据
  5. 生成m * K个数据,然后对这些数据再进行排序,或者再次通过维护最小堆

找出A,B两个海量url文件中共同的url

题目:两个文件各存50亿个url,每个url64个字节,内存限制4G,找出A,B共同的url

  • 单个文件读取肯定超出内存大小,所以还是采取之前的分治思想,大化小,对A/B分别取模分成1000个文件存储,这样两个文件中相同的url都被分到相同的小文件中,若有一方的小文件还是太大,则可以扩大分块或者通过不同hash函数继续hash(若继续,两方应该一起),50亿url算下来每个文件300M。
  • 对小文件求公共url的时候可以使用hash_set去重。A文件Set建立后另外一个文件的内容遍历跟Set中内容比对,如果相等则记录

bitmap

bitmap一般是total/32 + 1个数组,从a[0]开始,每组是32bit表示,对应位的0或1表示十进制的0-31是否存在,可以用于快速排序,快速去重,快速查询

海量数据判断一个整数是否存在其中

  • 分治思想,首先分成小文件,然后建立HashTable进行统计
  • 可以使用BitMap,每个数分配1Bit,0不存在,1存在建立完毕扫描数据把对应位置的比特位描成0/1,最后查找整数的位置是否为1(通过商判断在哪个数组中,余数判断哪一位)

海量数据找出不重复的数字/仅出现一次的数据

  • 可以使用BitMap,每个数分配两Bit,00不存在,01出现一次,10出现多次,11没意义。需要内存2^32 * 8 * 2bit,建立完毕扫描数据把对应位置的比特位描成00/01/10/11,最后查找01
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/152458.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • c#程序中的AssemblyInfo.cs

    c#程序中的AssemblyInfo.cs在asp.net中有一个配置文件AssemblyInfo.cs主要用来设定生成的有关程序集的常规信息dll文件的一些参数,下面是默认的AssemblyInfo.cs文件的内容具体介绍//是否符合公共语言规范(CLS)[assembly:CLSCompliant(true)]//控制程序集中所有类型对COM的可访问性[assembly:ComVisible(false)]//代码的作者和这…

  • mysql索引类型和索引方式

    mysql索引类型和索引方式1.什么是索引在MySQL中,索引(index)也叫做“键(key)”,它是存储引擎用于快速找到记录的一种数据结构。2.索引的分类在MySQL中,通常我们所指的索引类型,有以下几种:主键索引(PRIMARYKEY)也简称主键。它可以提高查询效率,并提供唯一性约束。一张表中只能有一个主键。被标志为自动增长的字段一定是主键,但主键不一定是自动增长。一般把主键定义在无意义的字段上(如:编号)…

  • 视差Disparity与深度图

    视差Disparity与深度图转自:http://www.elecfans.com/d/863829.html双目立体视觉,在百度百科里的解释是这样解释的:双目立体视觉(BinocularStereoVision)是机器视觉的一种重要形式,它是基于视差原理并利用成像设备从不同的位置获取被测物体的两幅图像,通过计算图像对应点间的位置偏差,来获取物体三维几何信息的方法。一、视差Disparity与深度图提到双目视觉就不得不提视差图:双目立体视觉融合两只眼睛获得的图像并观察它们之间的差别,使我们可以获得明显的深度感,建立特征间的对

  • 华三vlan配置_路由器配置vlan的步骤

    华三vlan配置_路由器配置vlan的步骤基于MAC地址划分vlan配置思路:创建VLAN100、VLAN200。配置DeviceA和DeviceC的上行端口为Trunk端口,并允许VLAN100和VLAN200的报文通过。配置DeviceB的下行端口为Trunk端口,并允许VLAN100和VLAN200的报文通过;上行端口分别加入VLAN100、VLAN200。Laptop1和Laptop2的MAC地址分别与VLAN100、VLAN200关联。SWA与SWC的配置一致:创建vlan:vlan100

  • mybatis 分页原理_分页机结构原理

    mybatis 分页原理_分页机结构原理Mybatis可以通过传递RowBounds对象,来进行数据库数据的分页操作,然而遗憾的是,该分页操作是对ResultSet结果集进行分页,也就是人们常说的逻辑分页,而非物理分页。RowBo…

  • 常说的手机刷新率60Hz、120Hz有什么不同?

    常说的手机刷新率60Hz、120Hz有什么不同?在很长一段时间里,手机的刷新率都是60Hz,随着硬件设备性能的提升,各种高刷新率的移动设备层出不穷,移动端也能有120Hz的显示设备。那么手机上的游戏真的是FPS越高越好吗?本期我们就来…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号