做优化网站多少钱,南京网站公司,西安建站平台哪个好,浏览器下载视频本文可以认为是http://blog.csdn.net/v_JULY_v/article/details/6279498的读后感#xff0c;我是按照我理解的语言重新表述了一下而已。 海量数据处理的常用方法包括一下几种#xff1a; 1.分而治之/hash映射 hash统计 堆/快速/归并排序#xff1b;2.双层桶划分3.Bloom fi…本文可以认为是http://blog.csdn.net/v_JULY_v/article/details/6279498的读后感我是按照我理解的语言重新表述了一下而已。 海量数据处理的常用方法包括一下几种 1.分而治之/hash映射 hash统计 堆/快速/归并排序2.双层桶划分3.Bloom filter/Bitmap4.Trie树/数据库/倒排索引5.外排序6.分布式处理之Hadoop/Mapreduce。 1. 分而治之/hash映射 hash统计 堆/快速/归并排序分治是算法的核心思想不过需要证明分治是适用的才行。 如何分呢就是用Hash函数来做用hash函数把大数据集分成几个小数据集然后对小数据集进行统计将多个子数据集的统计结果进行归并排序。例如 海量日志数据提取出某日访问百度次数最多的那个IP 可以IP地址按照IP%100将IP地址分为100个子集对各个子集分别统计频度然后取出各个子集出现最多的IP进而得到整体出现最多的IP 假设目前有一千万个记录这些查询串的重复度比较高虽然总数是1千万但如果除去重复后不超过3百万个。一个查询串的重复度越高说明查询它的用户越多也就是越热门请你统计最热门的10个查询串要求使用的内存不能超过1G。 这个也可以使用Trie树, 有一个1G大小的一个文件里面每一行是一个词词的大小不超过16字节内存限制大小是1M。返回频数最高的100个词。 海量数据分布在100台电脑中想个办法高效统计出这批数据的TOP10。 有10个文件每个文件1G每个文件的每一行存放的都是用户的query每个文件的query都可能重复。要求你按照query的频度排序。 给定a、b两个文件各存放50亿个url每个url各占64字节内存限制是4G让你找出a、b文件共同的url 2.双层桶划分适用范围第k大中位数不重复或重复的数字 2.5亿个整数中找出不重复的整数的个数内存空间不足以容纳这2.5亿个整数。 有点像鸽巢原理整数个数为2^32,也就是我们可以将这2^32个数划分为2^8个区域(比如用单个文件代表一个区域)然后将数据分离到不同的区域然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间就可以很方便的解决。 5亿个int找它们的中位数。 这个例子比上面那个更明显。首先我们将int划分为2^16个区域然后读取数据统计落到各个区域里的数的个数之后我们根据统计结果就可以判断中位数落到那个区域同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。 实际上如果不是int是int64我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域然后确定区域的第几大数在将该区域分成2^20个子区域然后确定是子区域的第几大数然后子区域里的数的个数只有2^20就可以直接利用direct addr table进行统计了。 3.Bloom filter/Bitmap 适用范围可以用来实现数据字典进行数据的判重或者集合求交集 给你A,B两个文件各存放50亿条URL每条URL占用64字节内存限制是4G让你找出A,B文件共同的URL。如果是三个乃至n个文件呢 已知某个文件内包含一些电话号码每个号码为8位数字统计不同号码的个数。 8位最多99 999 999大概需要99m个bit大概10几m字节的内存即可。2.5亿个整数中找出不重复的整数的个数内存空间不足以容纳这2.5亿个整数。 将bit-map扩展一下用2bit表示一个数即可0表示未出现1表示出现一次2表示出现2次及以上。或者我们不用2bit来进行表示我们用两个bit-map即可模拟实现这个2bit-map。 4.Trie树/数据库/倒排索引 适用范围数据量大重复多但是数据种类小可以放入内存 Trie树主要用来实现词频统计 5.外排序 6.分布式处理之Hadoop/Mapreduce http://blog.csdn.net/v_july_v/article/details/7382693转载于:https://www.cnblogs.com/whyandinside/archive/2012/07/07/2580755.html
