海量数据处理常用思想及重要数据结构

1、大顶堆、小顶堆

特别适合topN问题,如求海量日志中最大的100个数。既然是海量数据,那么内存中一下子无法加载所有的数据集,此时可以先读取海量数据中的100个数,建立数据集为100的小顶堆(小顶堆的对顶比所有元素都小),然后依次往堆结构中读取数字,调整堆,使其保持小顶堆,最后得到top100的最大数。

2、hash映射进行分治,然后归并

hash映射按照数据特征把海量数据变的不海量,然后分别处理各段数据,再归并处理。例如:给定两个文件,各存放50亿个url,让你找出两个文件中共同的url,则可以根据url的特征,将两个文件分别映射到上千个小文件中,只要保证两个文件用的相同的hash映射方法,那么相同的url映射后一定在相同的小文件中,所以逐一比较各个小文件中的url,然后归并即可。

3、hash统计

以特征为key值利用hash表进行统计,比如,求一本书中26个字母出现的个数,可以以26个字母分别为key值,进行hash统计即可。

4、bloom filter

可以用于判重,此方法存在一定的误差,但是比较高效。方法是利用多种不同的hash方法对数据集做hash运算,将对应的结果为key,值为1,然后判断一个新数在不在这个数据集中,则用相同的n中hash方法进行计算,如果全为1则认为在,任何一个不为1,则认为不在。

5、外排序

外只的是外存,因为内存一下子放不下海量的数据,所以只好把大数据拆成小数据,在内存中进行排序,在外存中进行存储。基本思想是先对大数据拆分成n个小数据,然后对小数据排序,然后放入文件中,再用归并的方法,将已排序的小数据集进行归并。

6、bitmap

位图用一个bit位来标记某个元素所对应的value,而key即是该元素本身,位图可以节约大量的空间。例如判断一个32位的整数是否在海量的32位整数数据集中出现过,则可使用位图。

7、多层划分

和hash映射类似也是分而治之,只不过是如果数据集恰好有一些可以分层的特点,则可以直接分层化大为小。如,海量32位整数的数据集中找中位数,首先我们将int划分为2^16个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。最后再次扫描我们只统计落在这个区域中的那些数就可以了。

8、tire树

比较适合字符串类的查找,如把1000万个单词中的大量的重复单词去掉,可以使用tire树进行查重。

9、mapreduce

有现成的大数据计算框架。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券