大家好,又见面了,我是你们的朋友全栈君。
海量数据处理思路
海量数据处理
海量数据,不能一次加载到内存中
- 海量数据topK(最大和最小k个数),第k大,第k小的数
- 海量数据判断一个整数是否存在其中
- 海量数据找出不重复的数字
- 找出A,B两个海量url文件中共同的url
海量数据topK
最大K使用最小堆,最小K使用最大堆,这里以最大K为例
- 海量数据hash分块
- 维护最小堆的K个数据的数据容器
- 堆中数据是topK大的数据,堆顶的数据是第K大数据
- 先将海量数据hash再取模m,分成m个小文件,hash(num)%m,也可以直接取模
- 在每个小文件中维护K个数据的最小堆,堆顶是当前堆中的最小值
- 遍历每个小文件中剩余的数据,与堆顶的数据进行比较,更新最小堆中的数据
- 生成m * K个数据,然后对这些数据再进行排序,或者再次通过维护最小堆
变形
- 第K大不只是topK,此时堆顶数据即是
- 只求最大或最小
- 海量数据不仅仅是整数,也可以是字符串
- 海量数据按照出现的次数或者频率排序,topK
- 海量数据按照出现的次数或者频率排序,topK
- 先将海量数据hash再取模m,分成m个小文件,hash(num)%m
- 扫描每个小文件的数据,通过hash_map建立值和频率的键值对
- 以出现的频率维护最小堆的K个数据的数据容器
- 遍历每个小文件中剩余的数据,与堆顶的数据进行比较,更新最小堆中的数据
- 生成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账号...