十道海量数据处理面试题与11个主意大总括[转]

# 总核数 = 物理CPU个数 X 每颗物理CPU的核数

  适用范围:大数据量的增加和删除改查

 

经典难题分析
  上千万or亿数目(有重新),计算在那之中出现次数最多的前N个数据,分二种状态:可3次读入内部存款和储蓄器,不可三次读入。

逻辑CPU(逻辑核):在/proc/cpuinfo文件的条文中siblings记录了相应的大体CPU(以该条款中的physical
id标识)有微微个逻辑核。

7、倒排索引(Inverted index)

 

  基本原理及中央:利用多少的统一筹划落成情势,对海量数据的增加和删除改查进行拍卖。

 

   
方案1:在后边的题中,大家已经涉及了,用多个含一百个因素的微乎其微堆完结。复杂度为O(拾0w*lg100)。

一.有稍许个区别的physical id就有微微个大体CPU。

附、100w个数中找出最大的九2十个数。

  

   
假诺内部的1些文件超过了1M分寸,还是能够遵从类似的方法继续往下分,直到分解得到的小文件的深浅都不超过1M。
   
对种种小文件,总括每一个文件中出现的词以及对应的效用(能够选用trie树/hash_map等),并取出出现频率最大的一百个词(能够用含100个结点的最小堆),并把九二十个词及相应的频率存入文件,那样又赢得了4000个公文。下一步就是把这陆仟个文件举办合并(类似与归并排序)的进度了。

物理核:CPU中隐含的大体基础个数,比如我们1般说的双核CPU,单核CPU。

致谢:http://www.cnblogs.com/youwang/

二.cpu cores记录了相应的物理CPU(以该条款中的physical
id标识)有多少个物理核,未来大家个人选用的单机PC当先二分之一选择的都以双核CPU。

   
方案一:接纳二-Bitmap(每种数分配二bit,00表示不设有,0一表示出现一回,拾象征多次,1一无意义)实行,共需内部存款和储蓄器2^3贰
* 二 bit=一GB内部存款和储蓄器,仍可以接受。然后扫描那贰.五亿个整数,查看Bitmap中相对应位,假设是00变0一,0一变10,十保障不变。所描完事后,查看bitmap,把对应位是0壹的平头输出即可。

大体CPU:物理CPU是相对于虚构CPU而言的定义,指实际存在的微型总结机,便是我们得以看的见,摸得着的CPU,正是插在主板方面包车型客车。

捌、怎么在海量数据中找出重新次数最多的四个?    
   
方案一:先做hash,然后求模映射为小文件,求出每种小文件中重复次数最多的三个,并记录重复次数。然后找出上一步求出的多寡中再次次数最多的3个正是所求(具体参考前边的题)。

# 查看物理CPU个数
cat /proc/cpuinfo| grep "physical id"| sort| uniq| wc -l
# 查看每个物理CPU中core的个数(即核数)
cat /proc/cpuinfo| grep "cpu cores"| uniq
# 查看逻辑CPU的个数
cat /proc/cpuinfo| grep "processor"| wc -l
# 查看CPU型号
cat /proc/cpuinfo | grep name | cut -f2 -d: | uniq -c

    对那十个公文进行归并排序(内排序与向外排水序相结合)。

# 总逻辑CPU数 = 物理CPU个数 X 每颗物理CPU的核数 X 超线程数

  贰).伍亿个int找它们的中位数。
  这些事例比上面十二分更显然。首先大家将int划分为贰^十七个区域,然后读取数据总结落到每个地方里的数的个数,之后我们依据总结结果就足以看清中位数落到那个区域,同时了然那个区域中的第几大数刚好是中位数。然后第一回扫描大家只总结落在那几个区域中的那多少个数就足以了。

在linux系统上面包车型大巴/proc/cpuinfo文件的条目中:

一、Bloom filter

    然后将那40亿个数分成两类:
      ①.最高位为0
      二.最高位为一
   
并将那两类分别写入到七个公文中,个中二个文本中数的个数<=20亿,而另贰个>=20亿(这一定于折半了);
与要摸索的数的参天位比较并随着进入相应的文书再找找

      扩展:
  d-left hashing中的d是八个的意味,我们先简化这么些标题,看一看2-left
hashing。二-left
hashing指的是将1个哈希表分成长度相等的两半,分别叫做T壹和T二,给T一和T二分别配备二个哈希函数,h1和h2。在仓库储存八个新的key时,同时用七个哈希函数进行计算,得出多少个地点h1[key]和h2[key]。那时必要检查T第11中学的h壹[key]位置和T2中的h2[key]职分,哪一个任务已经储存的(有撞击的)key相比较多,然后将新key存款和储蓄在负载少的地点。即便两边一样多,比如三个岗位都为空或许都存款和储蓄了3个key,就把新key存款和储蓄在右侧的T1子表中,贰-left也因此而来。在物色2个key时,必须举行两遍hash,同时招来多个地方。

  所谓的是或不是能二回读入内部存款和储蓄器,实际上应该指去除重复后的数据量。要是去重后数据足以放入内部存款和储蓄器,大家能够为数据建立字典,比如通过
map,hashmap,trie,然后径直实行计算即可。当然在更新每条数据的面世次数的时候,我们得以行使二个堆来有限支撑出现次数最多的前N个数据,当然如此造成维护次数增添,不比完全总括后在求前N大效能高。

 

    依旧独立的TOP K算法,解决方案如下:
    方案1:
   
顺序读取13个文本,依照hash(query)%十的结果将query写入到别的13个公文(记为)中。这样新变化的文本种种的轻重差不多也①G(假诺hash函数是轻易的)。
    
    找一台内设有2G左右的机械,依次对用hash_map(query,
query_count)来总结种种query出现的次数。利用高效/堆/归并排序依据出现次数实行排序。将排序好的query和相应的query_cout输出到文件中。那样得到了十一个排好序的文件(记为)。

  还有叁个相比关键的难点,怎么样遵照输入成分个数n,鲜明位数组m的大小及hash函数个数。当hash函数个数k=(ln二)*(m/n)时错误率最小。在错误率极小于E的场馆下,m至少要等于n*lg(1/E)才能代表任意n个因素的集聚。但m还应该更大些,因为还要保证bit数组里最少一半为0,则m应该>=nlg(1/E)*lge
大约就是nlg(1/E)一.44倍(lg表示以二为底的对数)。

二、Hashing

   
遍历文件a,对各种url求取hash(url)%一千,然后依据所收获的值将url分别存款和储蓄到一千个小文件(记为a0,a壹,…,a999)中。那样种种小文件的大致为300M。

 以英文为例,上边是要被索引的文书:
    T0 = “it is what it is”
    T1 = “what is it”
    T2 = “it is a banana”

  要是数据不能放入内部存款和储蓄器。壹方面大家能够设想地点的字典方法是不是被勘误以适应这种状态,能够做的改动正是将字典存放到硬盘上,而不是内部存款和储蓄器,这足以参见数据库的积存方法。

   
上面包车型地铁不二等秘书籍漫天起点http://hi.baidu.com/yanxionglu/blog/博客,对海量数据的拍卖措施进行了3个一般性的下结论,当然那几个艺术大概并不能够一心覆盖全数的难点,不过如此的有个别措施也基本得以处理绝半数以上遇到的标题。下边包车型的士有的标题基本直接源于公司的面试笔试标题,方法不肯定最优,如若你有更好的拍卖办法,欢迎商讨。

    方案二:借使同意有必然的错误率,能够运用Bloom
filter,4G内存大约能够代表340亿bit。将中间1个文件中的url使用Bloom
filter映射为那340亿bit,然后逐1读取别的1个文书的url,检查是不是与Bloom
filter,假诺是,那么该url应该是共同的url(注意会有必然的错误率)。

三、有一个壹G大大小小的二个文本,里面每1行是八个词,词的轻重缓急不超过1陆字节,内部存款和储蓄器限制大小是1M。重临频数最高的玖四个词。

  扩展:
  难点实例:
  ①).二.五亿个整数中找出不另行的平头的个数,内部存款和储蓄器空间不足以容纳那二.5亿个整数。
  有点像鸽巢原理,整数个数为二^3二,也正是,大家得以将那二^三2十个数,划分为二^九个区域(比如用单个文件表示3个区域),然后将数据分离到差别的区域,然后不一样的区域在使用bitmap就能够间接消除了。也便是说只要有丰富的磁盘空间,就能够很便利的缓解。

  • N’*O(logK),(N为一千万,N’为300万)。ok,越多,详情,请参考原作。

     
首先是那1天,并且是造访百度的日记中的IP取出来,每一种写入到贰个大文件中。注意到IP是30个人的,最多有个2^三1柒个IP。同样能够选拔映射的措施,比如模一千,把整个大文件映射为一千个小文件,再找出各类小文中出现频率最大的IP(能够利用hash_map进行频率总结,然后再找出成效最大的多少个)及相应的功效。然后再在这一千个最大的IP中,找出尤其频率最大的IP,即为所求。

十、3个文书文件,大致有三千0行,每行3个词,须求总结出个中最频仍出现的前11个词,请给出思想,给出时间复杂度分析。

  难点实例:
  1).海量日志数据,提取出某日访问百度次数最多的非常IP。
  IP的多少照旧有限的,最多2^3多少个,所以能够酌量选用hash将ip直接存入内部存款和储蓄器,然后进行总括。

  难题实例:
  1)十0w个数中找最大的前玖十九个数。
  用二个玖21个因素大小的最小堆即可。

如故正如阐释(雪域之鹰):
算法思想:分而治之+Hash

  基本原理及中央:完成格局,节点孩子的代表方法

率先部分、拾道海量数据处理面试题

    “a”:      {2}
    “banana”: {2}
    “is”:     {0, 1, 2}
    “it”:     {0, 1, 2}
    “what”:   {0, 1}

  难题实例:
  1).有11个文本,各个文件1G,每一种文件的每一行都存放的是用户的query,种种文件的query都可能再度。要你依据query的频度排序。
  二).一千万字符串,个中多少是同一的(重复),必要把重复的全套去掉,保留未有重新的字符串。请问怎么统一筹划和完结?
  3).寻找热门查询:查询串的重复度相比较高,尽管总数是一千万,但万壹除去重复后,不超越三百万个,每一个不超过255字节。

   
与上第陆题类似,小编的第二反应时快速排序+二分查找。以下是其余更好的法子:
    方案1:oo,申请51二M的内存,2个bit位代表3个unsigned
int值。读入40亿个数,设置相应的bit位,读入要询问的数,查占卜应bit位是或不是为一,为1代表存在,为0表示不存在。

  适用范围:数据量大,重复多,可是数量种类小能够放入内部存款和储蓄器

  那几个数目颇具很明朗的特点,词的轻重缓急为1三个字节,然则内部存款和储蓄器唯有一m做hash有个别不够,所以能够用来排序。内存能够当输入缓冲区使用。

 

四、有十一个文件,每一种文件壹G,各样文件的每壹行存放的都以用户的query,各种文件的query都恐怕再也。供给您依照query的频度排序。

   
方案一:能够预计每一个文件安的高低为伍G×6四=320G,远远高于内部存款和储蓄器限制的四G。所以相当小概将其完全加载到内部存储器中处理。缅怀动用分而治之的格局。

  可用思路:trie树+堆,数据库索引,划分子集分别计算,hash,分布式计算,近似总结,向外排水序

伍、双层桶划分—-其实本质上正是【分而治之】的思维,重在“分”的技艺上!

   
求每对小文件中同样的url时,能够把内部3个小文件的url存款和储蓄到hash_set中。然后遍历另二个小文件的每一种url,看其是还是不是在刚刚营造的hash_set中,倘使是,那么正是同步的url,存到文件之中就足以了。

   
遍历文件b,采用和a相同的主意将url分别存储到1000小文件(记为b0,b一,…,b99玖)。那样处理后,全体望同样的url都在相应的小文件(a0vsb0,a一vsb一,…,a99九vsb99玖)中,不对应的小文件不容许有同等的url。然后大家只供给出一千对小文件中同样的url即可。

我们就能博得下边包车型大巴反向文件目录:

 检索的尺度”what”,”is”和”it”将相应集合的搅和。

   
或然:采纳trie树,关键字域存该查询串出现的次数,未有出现为0。最后用十一个要素的小小推来对出现频率举办排序。

    再然后把那一个文件为又分为两类:
      1.次最高位为0
      二.次参天位为1

八、外排序

  难点实例:给你A,B多个文本,各存放50亿条UKugaL,每条U猎豹CS六L占用6四字节,内部存款和储蓄器限制是四G,让您找出A,B文件共同的U卡宴L。假如是四个甚至n个文件呢?

  正向索引开发出来用来存款和储蓄种种文书档案的单词的列表。正向索引的查询往往满意每种文书档案有序频仍的全文查询和各样单词在校验文书档案中的验证那样的查询。在正向索引中,文书档案占据了骨干的地点,种种文书档案指向了一个它所富含的索引项的队列。也便是说文书档案指向了它包蕴的那个单词,而反向索引则是单词指向了蕴涵它的文书档案,很简单看到那些反向的关联。

  难题实例:
  一).有3个壹G分寸的二个文本,里面每壹行是三个词,词的尺寸不超过15个字节,内部存款和储蓄器限制大小是1M。重回频数最高的九十七个词。

  基本原理及中央:
  hash函数采取,针对字符串,整数,排列,具体对应的hash方法。
  碰撞处理,壹种是open hashing,也称之为拉链法;另壹种正是closed
hashing,也称开地址法,opened addressing。

  适用范围:海量数据前n大,并且n相比小,堆能够放入内部存款和储蓄器

  扩展:
  难点实例:文档检索系统,查询那多少个文件包涵了某单词,比如大规模的学术杂文的显要字搜索。

    Bloom filter日后会在本BLOG内详细阐释。

其次片段、十三个海量数据处理措施大总括

    典型的Top
K算法,依然在那篇小说里头有所解说,详情请参见:101、从头到尾彻底解析Hash表算法。
    
    文中,给出的末梢算法是:
   
第三步、先对那批海量数据预处理,在O(N)的年月内用Hash表完毕统计(在此之前写成了排序,特此勘误。July、201一.0四.2七);
   
第二步、借助堆那些数据结构,找出Top
K,时间复杂度为N‘logK。
       
即,借助堆结构,我们得以在log量级的时间内寻找和调动/移动。由此,维护一个K(该难点中是10)大小的小根堆,然后遍历300万的Query,分别和根元素实行自查自纠所以,大家最终的光阴复杂度是:O(N)

  实际上大概想直接将数据均分到分化的对讲机上海展览中心开处理,那样是无力回天获取正确的解的。因为2个数目可能被均分到分裂的电话上,而另三个则大概完全聚集到三个电话上,同时还恐怕存在具有相同数量的多寡。比如大家要找出现次数最多的前91玖个,大家将一千万的数据分布到拾台机器上,找到每台出现次数最多的前
玖八个,归并之后那样不可能确定保证找到真正的第八0个,因为比如出现次数最多的第80个只怕有一万个,不过它被分到了十台机子,那样在每台上只有1千个,尽管这一个电话排行在一千个此前的那一个都以独立分布在1台机子上的,比如有十0一个,那样自然具有壹万个的那一个就会被淘汰,就算大家让每台机子选出出现次数最多的一千个再归并,依然会出错,因为只怕存在多量个数为拾03个的发出聚集。由此无法将数据随便均分到不一样机子上,而是要依照hash
后的值将它们映射到分歧的电话上处理,让分化的机器处理二个数值范围。

    dizengrong:
    方案2:其1题材在《编制程序珠玑》里有很好的讲述,大家能够参照下边包车型客车笔触,研究一下:
又因为二^32为40亿多,所以给定1个数恐怕在,也可能不在当中;
此处大家把40亿个数中的每一个用叁13个人的二进制来表示
固然这40亿个数开头放在三个文件中。

  基本原理及中央:使用bit数组来表示某个因素是或不是留存,比如8人电话号码

四、堆

  注意这里m与n的单位不一样,m是bit为单位,而n则是以成分个数为单位(准确的乃是不一样因素的个数)。平日单个成分的长短都以有很多bit的。所以使用bloom
filter内部存款和储蓄器上平日都以节省的。

  基本原理及中央:
  对于原理来说非常粗大略,位数组+k个独立hash函数。将hash函数对应的值的位数组置一,查找时只要发现拥有hash函数对应位都以一证实存在,很明显这一个历程并不保障查找的结果是百分百不错的。同时也不辅助删除三个早就插入的重中之重字,因为该关键字对应的位会拉动到任何的基本点字。所以1个简单的立异就是counting Bloom filter,用三个counter数组代替位数组,就足以支撑删除了。

七、腾讯面试题:给40亿个不另行的unsigned
int的平头,没排过序的,然后再给一个数,怎么着高效判断那么些数是或不是在那40亿个数个中?

  扩展:
  Bloom
filter将汇集中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是还是不是全一表示成分在不在那个集合中。Counting
bloom
filter(CBF)将位数组中的每一人扩大为一个counter,从而协助了成分的删除操作。Spectral
Bloom
Filter(SBF)将其与集合成分的产出次数关联。SBF采取counter中的最小值来就像是表示元素的面世频率。

  基本原理及中央:向外排水序的合并措施,置换选拔败者树原理,最优归并树

  将bit-map扩大一下,用二bit表示2个数即可,0意味未出现,壹表示出现三次,二表示出现三回及以上。可能大家不用二bit来开始展览表示,大家用八个bit-map即可模拟达成那么些贰bit-map。

   
位图法相比较适合于那种境况,它的做法是依据集合中最大要素max创造2个尺寸为max+壹的新数组,然后重新扫描原数组,境遇几就给新数组的第几人置上壹,如碰到五就给新数组的第6个成分置1,那样下次再遇上5想置位时意识新数组的第6个因素已经是一了,那表明此次的多少一定和原先的多少存在珍视新。那种给新数组起初化时置零其前置一的做法类似于位图的处理方式故称位图法。它的演算次数最坏的情形为二N。若是已知数组的最大值即能事先给新数组定长的话功效还可以拉长一倍。

九、trie树

  适用范围:能够用来促成数据字典,进行数据的判重,或许集合求交集

   
方案一:这题是想念时间效用。用trie树计算各种词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度)。然后是找出出现最频仍的前11个词,能够用堆来完毕,前边的题中已经讲到了,时间复杂度是O(n*lg10)。所以总的时间复杂度,是O(n*le)与O(n*lg拾)中较大的哪二个。

   
方案:顺序读文件中,对于各样词x,取hash(x)%6000,然后依据该值存到5000个小文件(记为x0,x1,…x499玖)中。那样各样文件大约是200k左右。

  适用范围:第k大,中位数,不重复或重复的数字
  基本原理及中央:因为成分范围相当大,不可能运用直接寻址表,所以经过反复分叉,稳步鲜明限制,然后最终在三个得以承受的范围内举行。能够透过反复压缩,双层只是3个例证。

出处:http://blog.csdn.net/v\_JULY\_v/article/details/6279498

 

    方案2:
    
一般query的总量是简单的,只是重新的次数相比多而已,可能对此有着的query,一回性就足以到场到内部存款和储蓄器了。那样,大家就能够动用trie树/hash_map等直接来总括各样query出现的次数,然后按现身次数做火速/堆/归并排序就足以了。

  适用范围:数据量大,不过数量种类小能够放入内存

  扩张:压缩达成。

   
方案一:上千万或上亿的数量,以后的机器的内部存款和储蓄器应该能存下。所以思虑采取hash_map/搜索贰叉树/红黑树等来实行总括次数。然后便是取出前N个冒出次数最多的数量了,能够用第一题提到的堆机制实现。

   
方案贰:选择高效排序的怀想,每一次分割之后只考虑比轴大的一局部,知道比轴大的一片段在比100多的时候,选用古板排序算法排序,取前九十七个。复杂度为O(十0w*100)。

  依照这些难点大家来估测计算下内部存储器的占用,四G=贰^3二差不多是40亿*8光景是340亿,n=50亿,假设按出错率0.0壹算须求的大致是650亿个bit。今后可用的是340亿,相差并不多,那样可能会使出错率上涨些。其余假使这几个urlip是各类对应的,就足以转换到ip,则大大简单了。

  扩展:
  难题实例:
  1).The canonical example application of MapReduce is a process to
count the appearances of
each different word in a set of documents:
  二).海量数据分布在十0台微型总结机中,想个办法高效总计出那批数量的TOP十。
  三).一共有N个机器,种种机器上有N个数。各样机器最多存O(N)个数并对它们操作。怎样找到N^二个数的中数(median)?

  适用范围:神速搜索,删除的基本数据结构,平时供给总数据量能够放入内部存款和储蓄器

  基本原理及宗旨:将数据交到差异的机械去处理,数据划分,结果归约。

拾、分布式处理 mapreduce

   附:此间,再不难介绍下,位图方法:
    使用位图法判断整形数组是或不是存在重复 
   
判断集合中留存重复是大面积编制程序义务之1,当集合中数据量相比大时大家数见不鲜希望少实行三次扫描,那时双重循环法就不可取了。

  实际上,若是否int是int6四,大家能够通过3回这样的撤销合并即可降低到还可以的水准。即能够先将int六十八分成贰^二十八个区域,然后鲜明区域的第几大数,在将该区域分为二^21个子区域,然后明确是子区域的第几大数,然后子区域里的数的个数只有二^20,就能够直接行使direct
addr table进行计算了。

  适用范围:搜索引擎,关键字查询

三、bit-map

    方案3:
   
与方案1看似,但在做完hash,分成三个文件后,能够付出三个文本来处理,选用分布式的架构来拍卖(比如MapReduce),最后再展开统壹。

   
方案3:采纳部分淘汰法。选择前915个要素,并排序,记为体系L。然后三次扫描剩余的成分x,与排好序的96个因素中细小的因素比,借使比那一个小小的要大,那么把那几个小小的的成分删除,并把x利用插入排序的构思,插入到系列L中。依次轮回,知道扫描了装有的要素。复杂度为O(100w*100)。

  扩展:

5、
给定a、b多个文件,各存放50亿个url,每一个url各占6四字节,内部存款和储蓄器限制是4G,让您找出a、b文件共同的url?

    欢迎,有更好的思路,或措施,共同沟通。

2、搜索引擎会通过日记文件把用户每一次搜寻使用的保有检索串都记录下来,每一个查询串的长短为一-255字节。    
倘使近来有一千万个记录(那么些查询串的重复度相比高,就算总数是一千万,但若是除去重复后,不超越三百万个。2个查询串的重复度越高,表达查询它的用户越来越多,相当于越吃香。),请您总计最抢手的11个查询串,须要使用的内存不能够跨越一G。

  当然还有更好的主意,就是足以应用分布式总计,基本上正是map-reduce进度,首先能够依照数据值也许把数据hash(md5)后的值,将数据依照范围划分到不一样的电话机,最棒能够让数据划分后得以1遍读入内部存款和储蓄器,那样不相同的对讲机负责处理各种的数值范围,实际上就是map。获得结果后,各种机子只需拿出个别的产出次数最多的前N个数据,然后汇集,选出全数的数额中出现次数最多的前N个数据,那实际上就是reduce进度。

九、上千万或上亿数据(有双重),总计在那之中出现次数最多的钱N个数据。

  基本原理及中央:最大堆求前n小,最小堆求前n大。方法,比如求前n小,我们比较当前成分与最大堆里的最大因素,如若它小于最大因素,则应当替换这一个最大要素。这样结尾得到的n个成分正是非常的小的n个。适合大数据量,求前n小,n的轻重缓急比较小的情事,那样能够扫描1回即可取得全体的前n成分,成效很高。

陆、在二.5亿个整数中找出不重复的整数,注,内存不足以容纳那贰.伍亿个整数。

  扩张:bloom filter能够当做是对bit-map的恢弘

   
ok,看了地点这么多的面试题,是不是有点头晕。是的,需求一个总括。接下来,本文将不难总括下有个别拍卖海量数据难点的普遍方法,而之后,本BLOG内会实际阐释那几个办法。

  难题实例:
  一)已知有个别文件内富含部分电话号码,各样号码为六位数字,总结不一样号码的个数。
  7个人最多9九 99玖 99玖,大致需求9玖m个bit,大约十几m字节的内部存储器即可。
  二)二.伍亿个整数中找出不另行的平头的个数,内部存款和储蓄器空间不足以容纳那2.5亿个整数。

  适用范围:可举行数量的飞跃搜索,判重,删除,壹般的话多少范围是int的十倍以下

 
而外排序的方法会消耗大量的IO,效能不会很高。而地方的分布式方法,也足以用来单机版本,也正是将总的数据根据值的界定,划分成四个不等的子文件,然后逐一处理。处理实现之后再对这一个单词的及其出现频率进行一个归并。实际上就足以选择一个向外排水序的联合进度。

  扩展:双堆,3个最大堆与2个小小的堆结合,能够用来保卫安全中位数。

一、海量日志数据,提取出某日访问百度次数最多的不胜IP。

  举个例证大家即使错误率为0.01,则此时m应差不离是n的13倍。那样k大致是八个。

   
方案二:也可使用与第2题类似的办法,举行私分小文件的办法。然后在小文件中找出不另行的平头,并排序。然后再实行合并,注意去除重复的要素。

  基本原理及中央:为什么叫倒排索引?1种索引方法,被用来存款和储蓄在全文字笔迹检测索下有个别单词在3个文书档案大概1组文书档案中的存款和储蓄地方的投射。

   
并将那两类分别写入到七个文件中,在这之中二个文件中数的个数<=10亿,而另1个>=10亿(这一定于折半了);
    与要物色的数的次最高位比较并随即进入相应的文本再寻找。
    …….
    以此类推,就足以找到了,而且时间复杂度为O(logn),方案二完。

六、数据库索引

一.IP地址最多有2^3二=4G种取值情形,所以无法完全加载到内部存款和储蓄器中处理; 
二.足以设想选择“分而治之”的盘算,依据IP地址的Hash(IP)%十贰四值,把海量IP日志分别存储到10贰多少个小文件中。那样,每一种小文件最多带有四MB个IP地址; 
叁.对于每一个小文件,能够创设八个IP为key,出现次数为value的Hash
map,同时记录当前出现次数最多的非凡IP地址;
4.能够取得拾2四个小文件中的现身次数最多的IP,再根据常规的排序算法得到完全上冒出次数最多的IP;

 
其它仍可以设想近似计算,约等于我们得以因此整合自然语言属性,只将那贰个的确实际中出现最多的那3个词作者为1个字典,使得这几个范畴足以放入内部存款和储蓄器。 

  适用范围:大数量的排序,去重

发表评论

电子邮件地址不会被公开。 必填项已用*标注