前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >海量数据处理

海量数据处理

作者头像
ClearSeve
发布2022-02-11 08:51:44
1.4K0
发布2022-02-11 08:51:44
举报
文章被收录于专栏:ClearSeve

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

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

海量数据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
  • 也可采用与第1题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。

如何根据时间先后顺序对一亿用户进行排序

10亿搜索关键词中热度最高的k个

  • 首先要统计每个搜索关键词出现的频率。我们可以通过散列表、平衡二叉查找树或者其他一些支持快速查找、插入的数据结构,来记录关键词及其出现的次数。
  • 假设我们选用散列表。我们就顺序扫描这 10 亿个搜索关键词。当扫描到某个关键词时,我们去散列表中查询。如果存在,我们就将对应的次数加一;如果不存在,我们就将它插入到散列表,并记录次数为 1。以此类推,等遍历完这 10 亿个搜索关键词之后,散列表中就存储了不重复的搜索关键词以及出现的次数。
  • 然后使用一个大小为K的小顶堆,遍历散列表,依次取出每个搜索关键词及对应出现的次数,然后与堆顶的搜索关键词对比。如果出现次数比堆顶搜索关键词的次数多,那就删除堆顶的关键词,将这个出现次数更多的关键词加入到堆中。

不知道你发现了没有,上面的解决思路其实存在漏洞。10 亿的关键词还是很多的。我们假设 10 亿条搜索关键词中不重复的有 1 亿条,如果每个搜索关键词的平均长度是 50 个字节,那存储 1 亿个关键词起码需要 5GB 的内存空间,而散列表因为要避免频繁冲突,不会选择太大的装载因子,所以消耗的内存空间就更多了。而我们的机器只有 1GB 的可用内存空间,所以我们无法一次性将所有的搜索关键词加入到内存中。

  • 相同数据经过哈希算法得到的哈希值是一样的。我们可以哈希算法的这个特点,将 10 亿条搜索关键词先通过哈希算法分片到 10 个文件中。
  • 具体可以这样做:我们创建 10 个空文件 00,01,02,……,09。我们遍历这 10 亿个关键词,并且通过某个哈希算法对其求哈希值,然后哈希值同 10 取模,得到的结果就是这个搜索关键词应该被分到的文件编号。
  • 对这 10 亿个关键词分片之后,每个文件都只有 1 亿的关键词,去除掉重复的,可能就只有1000 万个,每个关键词平均 50 个字节,所以总的大小就是 500MB。1GB 的内存完全可以放得下。
  • 我们针对每个包含 1 亿条搜索关键词的文件,利用散列表和堆,分别求出 Top 10,然后把这个 10 个 Top 10 放在一块,然后取这 100 个关键词中,出现次数最多的 10 个关键词,这就是这 10 亿数据中的 Top 10 最频繁的搜索关键词了。

10大海量数据处理方案

https://blog.csdn.net/luyafei_89430/article/details/13016093

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022年2月9日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 海量数据topK
  • 找出A,B两个海量url文件中共同的url
  • bitmap
  • 海量数据判断一个整数是否存在其中
  • 海量数据找出不重复的数字/仅出现一次的数据
  • 10亿搜索关键词中热度最高的k个
  • 10大海量数据处理方案
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档