海量数据_海量数据处理 - CSDN
精华内容
参与话题
  • 教你如何迅速秒杀掉:99%的海量数据处理面试题

    万次阅读 多人点赞 2018-05-30 19:28:45
    教你如何迅速秒杀掉:99%的海量数据处理面试题作者:July出处:结构之法算法之道blog前言 一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢...

          教你如何迅速秒杀掉:99%的海量数据处理面试题

    本文经过大量细致的优化后,收录于我的新书《编程之法:面试和算法心得》第六章中,新书目前已上架京东/当当


    作者:July
    出处:结构之法算法之道blog



    前言

       一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢此文,却无任何收获,那么,我也甘愿背负这样的罪名 :-),同时,此文可以看做是对这篇文章:十道海量数据处理面试题与十个方法大总结的一般抽象性总结。

        毕竟受文章和理论之限,本文将摒弃绝大部分的细节,只谈方法/模式论,且注重用最通俗最直白的语言阐述相关问题。最后,有一点必须强调的是,全文行文是基于面试题的分析基础之上的,具体实践过程中,还是得具体情况具体分析,且各个场景下需要考虑的细节也远比本文所描述的任何一种解决方法复杂得多。

        OK,若有任何问题,欢迎随时不吝赐教。谢谢。



    何谓海量数据处理?

       所谓海量数据处理,无非就是基于海量数据上的存储、处理、操作。何谓海量,就是数据量太大,所以导致要么是无法在较短时间内迅速解决,要么是数据太大,导致无法一次性装入内存。

        那解决办法呢?针对时间,我们可以采用巧妙的算法搭配合适的数据结构,如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie树,针对空间,无非就一个办法:大而化小,分而治之(hash映射),你不是说规模太大嘛,那简单啊,就把规模大化为规模小的,各个击破不就完了嘛。

        至于所谓的单机及集群问题,通俗点来讲,单机就是处理装载数据的机器有限(只要考虑cpu,内存,硬盘的数据交互),而集群,机器有多辆,适合分布式处理,并行计算(更多考虑节点和节点间的数据交互)。

        再者,通过本blog内的有关海量数据处理的文章:Big Data Processing,我们已经大致知道,处理海量数据问题,无非就是:

    1. 分而治之/hash映射 + hash统计 + 堆/快速/归并排序;
    2. 双层桶划分
    3. Bloom filter/Bitmap;
    4. Trie树/数据库/倒排索引;
    5. 外排序;
    6. 分布式处理之Hadoop/Mapreduce。

        下面,本文第一部分、从set/map谈到hashtable/hash_map/hash_set,简要介绍下set/map/multiset/multimap,及hash_set/hash_map/hash_multiset/hash_multimap之区别(万丈高楼平地起,基础最重要),而本文第二部分,则针对上述那6种方法模式结合对应的海量数据处理面试题分别具体阐述。


    第一部分、从set/map谈到hashtable/hash_map/hash_set

        稍后本文第二部分中将多次提到hash_map/hash_set,下面稍稍介绍下这些容器,以作为基础准备。一般来说,STL容器分两种,

    • 序列式容器(vector/list/deque/stack/queue/heap),
    • 关联式容器。关联式容器又分为set(集合)和map(映射表)两大类,以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表),这些容器均以RB-tree完成。此外,还有第3类关联式容器,如hashtable(散列表),以及以hashtable为底层机制完成的hash_set(散列集合)/hash_map(散列映射表)/hash_multiset(散列多键集合)/hash_multimap(散列多键映射表)。也就是说,set/map/multiset/multimap都内含一个RB-tree,而hash_set/hash_map/hash_multiset/hash_multimap都内含一个hashtable

        所谓关联式容器,类似关联式数据库,每笔数据或每个元素都有一个键值(key)和一个实值(value),即所谓的Key-Value(键-值对)。当元素被插入到关联式容器中时,容器内部结构(RB-tree/hashtable)便依照其键值大小,以某种特定规则将这个元素放置于适当位置。

         包括在非关联式数据库中,比如,在MongoDB内,文档(document)是最基本的数据组织形式,每个文档也是以Key-Value(键-值对)的方式组织起来。一个文档可以有多个Key-Value组合,每个Value可以是不同的类型,比如String、Integer、List等等。 
    { "name" : "July",  
      "sex" : "male",  
        "age" : 23 }  

    set/map/multiset/multimap

        set,同map一样,所有元素都会根据元素的键值自动被排序,因为set/map两者的所有各种操作,都只是转而调用RB-tree的操作行为,不过,值得注意的是,两者都不允许两个元素有相同的键值。
        不同的是:set的元素不像map那样可以同时拥有实值(value)和键值(key),set元素的键值就是实值,实值就是键值,而map的所有元素都是pair,同时拥有实值(value)和键值(key),pair的第一个元素被视为键值,第二个元素被视为实值。
        至于multiset/multimap,他们的特性及用法和set/map完全相同,唯一的差别就在于它们允许键值重复,即所有的插入操作基于RB-tree的insert_equal()而非insert_unique()。

    hash_set/hash_map/hash_multiset/hash_multimap

        hash_set/hash_map,两者的一切操作都是基于hashtable之上。不同的是,hash_set同set一样,同时拥有实值和键值,且实质就是键值,键值就是实值,而hash_map同map一样,每一个元素同时拥有一个实值(value)和一个键值(key),所以其使用方式,和上面的map基本相同。但由于hash_set/hash_map都是基于hashtable之上,所以不具备自动排序功能。为什么?因为hashtable没有自动排序功能。
        至于hash_multiset/hash_multimap的特性与上面的multiset/multimap完全相同,唯一的差别就是它们hash_multiset/hash_multimap的底层实现机制是hashtable(而multiset/multimap,上面说了,底层实现机制是RB-tree),所以它们的元素都不会被自动排序,不过也都允许键值重复。

        所以,综上,说白了,什么样的结构决定其什么样的性质,因为set/map/multiset/multimap都是基于RB-tree之上,所以有自动排序功能,而hash_set/hash_map/hash_multiset/hash_multimap都是基于hashtable之上,所以不含有自动排序功能,至于加个前缀multi_无非就是允许键值重复而已。如下图所示:

        此外,

    • 关于什么hash,请看blog内此篇文章
    • 关于红黑树,请参看blog内系列文章
    • 关于hash_map的具体应用:请看这里,关于hash_set:请看此文

        OK,接下来,请看本文第二部分、处理海量数据问题之六把密匙。



    第二部分、处理海量数据问题之六把密匙

    密匙一、分而治之/Hash映射 + Hash_map统计 + 堆/快速/归并排序

    1、海量日志数据,提取出某日访问百度次数最多的那个IP。
        既然是海量数据处理,那么可想而知,给我们的数据那就一定是海量的。针对这个数据的海量,我们如何着手呢?对的,无非就是分而治之/hash映射 + hash统计 + 堆/快速/归并排序,说白了,就是先映射,而后统计,最后排序:
    1. 分而治之/hash映射:针对数据太大,内存受限,只能是:把大文件化成(取模映射)小文件,即16字方针:大而化小,各个击破,缩小规模,逐个解决
    2. hash_map统计:当大文件转化了小文件,那么我们便可以采用常规的hash_map(ip,value)来进行频率统计。
    3. 堆/快速排序:统计完了之后,便进行排序(可采取堆排序),得到次数最多的IP。

       具体而论,则是: “首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法,比如%1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map对那1000个文件中的所有IP进行频率统计,然后依次找出各个文件中频率最大的那个IP)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。”--十道海量数据处理面试题与十个方法大总结

        关于本题,还有几个问题,如下:

          1、Hash取模是一种等价映射,不会存在同一个元素分散到不同小文件中的情况,即这里采用的是mod1000算法,那么相同的IP在hash取模后,只可能落在同一个文件中,不可能被分散的。因为如果两个IP相等,那么经过Hash(IP)之后的哈希值是相同的,将此哈希值取模(如模1000),必定仍然相等。
          2、那到底什么是hash映射呢?简单来说,就是为了便于计算机在有限的内存中处理big数据,从而通过一种映射散列的方式让数据均匀分布在对应的内存位置(如大数据通过取余的方式映射成小树存放在内存中,或大文件映射成多个小文件),而这个映射散列方式便是我们通常所说的hash函数,设计的好的hash函数能让数据均匀分布而减少冲突。尽管数据映射到了另外一些不同的位置,但数据还是原来的数据,只是代替和表示这些原始数据的形式发生了变化而已。

        OK,有兴趣的,还可以再了解下一致性hash算法,见blog内此文第五部分:http://blog.csdn.net/v_july_v/article/details/6879101

    2、寻找热门查询,300万个查询字符串中统计最热门的10个查询

        原题:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门),请你统计最热门的10个查询串,要求使用的内存不能超过1G。

        解答:由上面第1题,我们知道,数据大则划为小的,如如一亿个Ip求Top 10,可先%1000将ip分到1000个小文件中去,并保证一种ip只出现在一个文件中,再对每个小文件中的ip进行hashmap计数统计并按数量排序,最后归并或者最小堆依次处理每个小文件的top10以得到最后的结。

        但如果数据规模比较小,能一次性装入内存呢?比如这第2题,虽然有一千万个Query,但是由于重复度比较高,因此事实上只有300万的Query,每个Query255Byte,因此我们可以考虑把他们都放进内存中去(300万个字符串假设没有重复,都是最大长度,那么最多占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理),而现在只是需要一个合适的数据结构,在这里,HashTable绝对是我们优先的选择。

        所以我们放弃分而治之/hash映射的步骤,直接上hash统计,然后排序。So,针对此类典型的TOP K问题,采取的对策往往是:hashmap + 堆。如下所示:

    1. hash_map统计:先对这批海量数据预处理。具体方法是:维护一个Key为Query字串,Value为该Query出现次数的HashTable,即hash_map(Query,Value),每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计;
    2. 堆排序:第二步、借助堆这个数据结构,找出Top K,时间复杂度为N‘logK。即借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比。所以,我们最终的时间复杂度是:O(N) + N' * O(logK),(N为1000万,N’为300万)。

        别忘了这篇文章中所述的堆排序思路:“维护k个元素的最小堆,即用容量为k的最小堆存储最先遍历到的k个数,并假设它们即是最大的k个数,建堆费时O(k),并调整堆(费时O(logk))后,有k1>k2>...kmin(kmin设为小顶堆中最小元素)。继续遍历数列,每次遍历一个元素x,与堆顶元素比较,若x>kmin,则更新堆(x入堆,用时logk),否则不更新堆。这样下来,总费时O(k*logk+(n-k)*logk)=O(n*logk)。此方法得益于在堆中,查找等各项操作时间复杂度均为logk。”--第三章续、Top K算法问题的实现
        当然,你也可以采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

    3、有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。
           由上面那两个例题,分而治之 + hash统计 + 堆/快速排序这个套路,我们已经开始有了屡试不爽的感觉。下面,再拿几道再多多验证下。请看此第3题:又是文件很大,又是内存受限,咋办?还能怎么办呢?无非还是:

    1. 分而治之/hash映射:顺序读文件中,对于每个词x,取hash(x)%5000,然后按照该值存到5000个小文件(记为x0,x1,...x4999)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。
    2. hash_map统计:对每个小文件,采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。
    3. 堆/归并排序:取出出现频率最大的100个词(可以用含100个结点的最小堆)后,再把100个词及相应的频率存入文件,这样又得到了5000个文件。最后就是把这5000个文件进行归并(类似于归并排序)的过程了。
    4、海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
        如果每个数据元素只出现一次,而且只出现在某一台机器中,那么可以采取以下步骤统计出现次数TOP10的数据元素:
    1. 堆排序:在每台电脑上求出TOP10,可以采用包含10个元素的堆完成(TOP10小,用最大堆,TOP10大,用最小堆,比如求TOP10大,我们首先取前10个元素调整成最小堆,如果发现,然后扫描后面的数据,并与堆顶元素比较,如果比堆顶元素大,那么用该元素替换堆顶,然后再调整为最小堆。最后堆中的元素就是TOP10大)。
    2. 求出每台电脑上的TOP10后,然后把这100台电脑上的TOP10组合起来,共1000个数据,再利用上面类似的方法求出TOP10就可以了。
        但如果同一个元素重复出现在不同的电脑中呢,如下例子所述:


        这个时候,你可以有两种方法:
    • 遍历一遍所有数据,重新hash取摸,如此使得同一个元素只出现在单独的一台电脑中,然后采用上面所说的方法,统计每台电脑中各个元素的出现次数找出TOP10,继而组合100台电脑上的TOP10,找出最终的TOP10。
    • 或者,暴力求解:直接统计统计每台电脑中各个元素的出现次数,然后把同一个元素在不同机器中的出现次数相加,最终从所有数据中找出TOP10。
    5、有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。

       方案1:直接上:

    1. hash映射:顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件(记为a0,a1,..a9)中。这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。
    2. hash_map统计:找一台内存在2G左右的机器,依次对用hash_map(query, query_count)来统计每个query出现的次数。注:hash_map(query,query_count)是用来统计每个query的出现次数,不是存储他们的值,出现一次,则count+1。
    3. 堆/快速/归并排序:利用快速/堆/归并排序按照出现次数进行排序,将排序好的query和对应的query_cout输出到文件中,这样得到了10个排好序的文件(记为)。最后,对这10个文件进行归并排序(内排序与外排序相结合)。根据此方案1,这里有一份实现:https://github.com/ooooola/sortquery/blob/master/querysort.py
         除此之外,此题还有以下两个方法:
        方案2:一般query的总量是有限的,只是重复的次数比较多而已,可能对于所有的query,一次性就可以加入到内存了。这样,我们就可以采用trie树/hash_map等直接来统计每个query出现的次数,然后按出现次数做快速/堆/归并排序就可以了。

        方案3:与方案1类似,但在做完hash,分成多个文件后,可以交给多个文件来处理,采用分布式的架构来处理(比如MapReduce),最后再进行合并。

    6、 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?

        可以估计每个文件安的大小为5G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

    1. 分而治之/hash映射遍历文件a,对每个url求取,然后根据所取得的值将url分别存储到1000个小文件(记为这里漏写个了a1)中。这样每个小文件的大约为300M遍历文件b,采取和a相同的方式将url分别存储到1000小文件中(记为)。这样处理后,所有可能相同的url都在对应的小文件()中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可
    2. hash_set统计:求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。

        OK,此第一种方法:分而治之/hash映射 + hash统计 + 堆/快速/归并排序,再看最后4道题,如下:

    7、怎么在海量数据中找出重复次数最多的一个?

        方案:先做hash,然后求模映射为小文件,求出每个小文件中重复次数最多的一个,并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求(具体参考前面的题)。

    8、上千万或上亿数据(有重复),统计其中出现次数最多的前N个数据。

        方案:上千万或上亿的数据,现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后利用堆取出前N个出现次数最多的数据。

    9、一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。

        方案1:如果文件比较大,无法一次性读入内存,可以采用hash取模的方法,将大文件分解为多个小文件,对于单个小文件利用hash_map统计出每个小文件中10个最常出现的词,然后再进行归并处理,找出最终的10个最常出现的词。
        方案2:通过hash取模将大文件分解为多个小文件后,除了可以用hash_map统计出每个小文件中10个最常出现的词,也可以用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度),最终同样找出出现最频繁的前10个词(可用堆来实现),时间复杂度是O(n*lg10)。

    10. 1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。请怎么设计和实现?

    • 方案1:这题用trie树比较合适,hash_map也行。
    • 方案2:from xjbzju:,1000w的数据规模插入操作完全不现实,以前试过在stl下100w元素插入set中已经慢得不能忍受,觉得基于hash的实现不会比红黑树好太多,使用vector+sort+unique都要可行许多,建议还是先hash成小文件分开处理再综合。
        上述方案2中读者xbzju的方法让我想到了一些问题,即是set/map,与hash_set/hash_map的性能比较?共计3个问题,如下:
    • 1、hash_set在千万级数据下,insert操作优于set? 这位blog:http://t.cn/zOibP7t 给的实践数据可靠不? 
    • 2、那map和hash_map的性能比较呢? 谁做过相关实验?
    • 3、那查询操作呢,如下段文字所述?

        或者小数据量时用map,构造快,大数据量时用hash_map?

    rbtree PK hashtable

        据朋友№邦卡猫№的做的红黑树和hash table的性能测试中发现:当数据量基本上int型key时,hash table是rbtree的3-4倍,但hash table一般会浪费大概一半内存。

        因为hash table所做的运算就是个%,而rbtree要比较很多,比如rbtree要看value的数据 ,每个节点要多出3个指针(或者偏移量) 如果需要其他功能,比如,统计某个范围内的key的数量,就需要加一个计数成员。

        且1s rbtree能进行大概50w+次插入,hash table大概是差不多200w次。不过很多的时候,其速度可以忍了,例如倒排索引差不多也是这个速度,而且单线程,且倒排表的拉链长度不会太大。正因为基于树的实现其实不比hashtable慢到哪里去,所以数据库的索引一般都是用的B/B+树,而且B+树还对磁盘友好(B树能有效降低它的高度,所以减少磁盘交互次数)。比如现在非常流行的NoSQL数据库,像MongoDB也是采用的B树索引。关于B树系列,请参考本blog内此篇文章:从B树、B+树、B*树谈到R 树。更多请待后续实验论证。

    11. 一个文本文件,找出前10个经常出现的词,但这次文件比较长,说是上亿行或十亿行,总之无法一次读入内存,问最优解。
        方案1:首先根据用hash并求模,将文件分解为多个小文件,对于单个文件利用上题的方法求出每个文件件中10个最常出现的词。然后再进行归并处理,找出最终的10个最常出现的词。

    12. 100w个数中找出最大的100个数。
        方案1:采用局部淘汰法。选取前100个元素,并排序,记为序列L。然后一次扫描剩余的元素x,与排好序的100个元素中最小的元素比,如果比这个最小的要大,那么把这个最小的元素删除,并把x利用插入排序的思想,插入到序列L中。依次循环,知道扫描了所有的元素。复杂度为O(100w*100)。
        方案2:采用快速排序的思想,每次分割之后只考虑比轴大的一部分,知道比轴大的一部分在比100多的时候,采用传统排序算法排序,取前100个。复杂度为O(100w*100)。
        方案3:在前面的题中,我们已经提到了,用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。

        接下来,咱们来看第二种方法,双层捅划分。


    密匙二、多层划分

    多层划分----其实本质上还是分而治之的思想,重在“分”的技巧上!
      适用范围:第k大,中位数,不重复或重复的数字
      基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。

    问题实例:

    13、2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
        有点像鸽巢原理,整数个数为2^32,也就是,我们可以将这2^32个数,划分为2^8个区域(比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。

    14、5亿个int找它们的中位数。

    1. 思路一:这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
      实际上,如果不是int是int64,我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域,然后确定区域的第几大数,在将该区域分成2^20个子区域,然后确定是子区域的第几大数,然后子区域里的数的个数只有2^20,就可以直接利用direct addr table进行统计了。
    2.   思路二@绿色夹克衫:同样需要做两遍统计,如果数据存在硬盘上,就需要读取2次。
      方法同基数排序有些像,开一个大小为65536的Int数组,第一遍读取,统计Int32的高16位的情况,也就是0-65535,都算作0,65536 - 131071都算作1。就相当于用该数除以65536。Int32 除以 65536的结果不会超过65536种情况,因此开一个长度为65536的数组计数就可以。每读取一个数,数组中对应的计数+1,考虑有负数的情况,需要将结果加32768后,记录在相应的数组内。
      第一遍统计之后,遍历数组,逐个累加统计,看中位数处于哪个区间,比如处于区间k,那么0- k-1的区间里数字的数量sum应该<n/2(2.5亿)。而k+1 - 65535的计数和也<n/2,第二遍统计同上面的方法类似,但这次只统计处于区间k的情况,也就是说(x / 65536) + 32768 = k。统计只统计低16位的情况。并且利用刚才统计的sum,比如sum = 2.49亿,那么现在就是要在低16位里面找100万个数(2.5亿-2.49亿)。这次计数之后,再统计一下,看中位数所处的区间,最后将高位和低位组合一下就是结果了。

    密匙三:Bloom filter/Bitmap

    Bloom filter

    关于什么是Bloom filter,请参看blog内此文:

      适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集
      基本原理及要点:
      对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。
      还有一个比较重要的问题,如何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
      举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。
      注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。

      扩展:

      Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

       可以看下上文中的第6题:

    “6、给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?

      根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。

        同时,上文的第5题:给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?如果允许有一定的错误率,可以使用Bloom filter,4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。”

    Bitmap

        下面关于Bitmap的应用,可以看下上文中的第13题,以及另外一道新题:

    “13、在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数。

        方案1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32 * 2 bit=1 GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。
        方案2:也可采用与第1题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。

    15、给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
        方案1:frome oo,用位图/Bitmap的方法,申请512M的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。


    密匙四、Trie树/数据库/倒排索引

    Trie树

      适用范围:数据量大,重复多,但是数据种类小可以放入内存
      基本原理及要点:实现方式,节点孩子的表示方式
      扩展:压缩实现。
      问题实例:

    1. 上面的第2题:寻找热门查询:查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个,每个不超过255字节。
    2. 上面的第5题:有10个文件,每个文件1G,每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。要你按照query的频度排序。
    3. 1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。请问怎么设计和实现?
    4. 上面的第8题:一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词。其解决方法是:用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度),然后是找出出现最频繁的前10个词。

        更多有关Trie树的介绍,请参见此文:从Trie树(字典树)谈到后缀树

    数据库索引
      适用范围:大数据量的增删改查
      基本原理及要点:利用数据的设计实现方法,对海量数据的增删改查进行处理。

    倒排索引(Inverted index)
      适用范围:搜索引擎,关键字查询
      基本原理及要点:为何叫倒排索引?一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
     以英文为例,下面是要被索引的文本:
        T0 = "it is what it is"
        T1 = "what is it"
        T2 = "it is a banana"
        我们就能得到下面的反向文件索引:
        "a":      {2}
        "banana": {2}
        "is":     {0, 1, 2}
        "it":     {0, 1, 2}
        "what":   {0, 1}
     检索的条件"what","is"和"it"将对应集合的交集。

      正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中,文档占据了中心的位置,每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词,而反向索引则是单词指向了包含它的文档,很容易看到这个反向的关系。
      扩展:
      问题实例:文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字搜索。

        关于倒排索引的应用,更多请参见:


    密匙五、外排序

      适用范围:大数据的排序,去重
      基本原理及要点:外排序的归并方法,置换选择败者树原理,最优归并树
    问题实例:
      1).有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存限制大小是1M。返回频数最高的100个词。
      这个数据具有很明显的特点,词的大小为16个字节,但是内存只有1M做hash明显不够,所以可以用来排序。内存可以当输入缓冲区使用。

        关于多路归并算法及外排序的具体应用场景,请参见blog内此文:


    密匙六、分布式处理之Mapreduce

        MapReduce是一种计算模型,简单的说就是将大批量的工作(数据)分解(MAP)执行,然后再将结果合并成最终结果(REDUCE)。这样做的好处是可以在任务被分解后,可以通过大量机器进行并行计算,减少整个操作的时间。但如果你要我再通俗点介绍,那么,说白了,Mapreduce的原理就是一个归并排序。

    适用范围:数据量大,但是数据种类小可以放入内存
    基本原理及要点:将数据交给不同的机器去处理,数据划分,结果归约。
    问题实例:

    1. The canonical example application of MapReduce is a process to count the appearances of each different word in a set of documents:
    2. 海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
    3. 一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)?

        更多具体阐述请参见blog内:

    其它模式/方法论,结合操作系统知识

        至此,六种处理海量数据问题的模式/方法已经阐述完毕。据观察,这方面的面试题无外乎以上一种或其变形,然题目为何取为是:秒杀99%的海量数据处理面试题,而不是100%呢。OK,给读者看最后一道题,如下:
        非常大的文件,装不进内存。每行一个int类型数据,现在要你随机取100个数
        我们发现上述这道题,无论是以上任何一种模式/方法都不好做,那有什么好的别的方法呢?我们可以看看:操作系统内存分页系统设计(说白了,就是映射+建索引)。
        Windows 2000使用基于分页机制的虚拟内存。每个进程有4GB的虚拟地址空间。基于分页机制,这4GB地址空间的一些部分被映射了物理内存,一些部分映射硬盘上的交换文 件,一些部分什么也没有映射。程序中使用的都是4GB地址空间中的虚拟地址。而访问物理内存,需要使用物理地址。 关于什么是物理地址和虚拟地址,请看:
    • 物理地址 (physical address): 放在寻址总线上的地址。放在寻址总线上,如果是读,电路根据这个地址每位的值就将相应地址的物理内存中的数据放到数据总线中传输。如果是写,电路根据这个 地址每位的值就将相应地址的物理内存中放入数据总线上的内容。物理内存是以字节(8位)为单位编址的。 
    • 虚拟地址 (virtual address): 4G虚拟地址空间中的地址,程序中使用的都是虚拟地址。 使用了分页机制之后,4G的地址空间被分成了固定大小的页,每一页或者被映射到物理内存,或者被映射到硬盘上的交换文件中,或者没有映射任何东西。对于一 般程序来说,4G的地址空间,只有一小部分映射了物理内存,大片大片的部分是没有映射任何东西。物理内存也被分页,来映射地址空间。对于32bit的 Win2k,页的大小是4K字节。CPU用来把虚拟地址转换成物理地址的信息存放在叫做页目录和页表的结构里。 
        物理内存分页,一个物理页的大小为4K字节,第0个物理页从物理地址 0x00000000 处开始。由于页的大小为4KB,就是0x1000字节,所以第1页从物理地址 0x00001000 处开始。第2页从物理地址 0x00002000 处开始。可以看到由于页的大小是4KB,所以只需要32bit的地址中高20bit来寻址物理页。 
        返回上面我们的题目:非常大的文件,装不进内存。每行一个int类型数据,现在要你随机取100个数。针对此题,我们可以借鉴上述操作系统中内存分页的设计方法,做出如下解决方案:

        操作系统中的方法,先生成4G的地址表,在把这个表划分为小的4M的小文件做个索引,二级索引。30位前十位表示第几个4M文件,后20位表示在这个4M文件的第几个,等等,基于key value来设计存储,用key来建索引。

        但如果现在只有10000个数,然后怎么去随机从这一万个数里面随机取100个数?请读者思考。更多海里数据处理面试题,请参见此文第一部分:http://blog.csdn.net/v_july_v/article/details/6685962



    参考文献

    1. 十道海量数据处理面试题与十个方法大总结
    2. 海量数据处理面试题集锦与Bit-map详解
    3. 十一、从头到尾彻底解析Hash表算法
    4. 海量数据处理之Bloom Filter详解
    5. 从Trie树(字典树)谈到后缀树
    6. 第三章续、Top K算法问题的实现
    7. 第十章、如何给10^7个数据量的磁盘文件排序
    8. 从B树、B+树、B*树谈到R 树
    9. 第二十三、四章:杨氏矩阵查找,倒排索引关键词Hash不重复编码实践
    10. 第二十六章:基于给定的文档生成倒排索引的编码与实践
    11. Hadhoop框架与MapReduce模式中谈海量数据处理
    12. 第十六~第二十章:全排列,跳台阶,奇偶排序,第一个只出现一次等问题
    13. http://blog.csdn.net/v_JULY_v/article/category/774945
    14. STL源码剖析第五章,侯捷著;
    15. 2012百度实习生招聘笔试题:http://blog.csdn.net/hackbuteer1/article/details/7542774
    16. Redis/MongoDB绝佳站点:http://blog.nosqlfan.com/
    17. 国外一面试题网站:http://www.careercup.com/


    后记

        经过上面这么多海量数据处理面试题的轰炸,我们依然可以看出这类问题是有一定的解决方案/模式的,所以,不必将其神化。然这类面试题所包含的问题还是比较简单的,若您在这方面有更多实践经验,欢迎在本文评论下与大家不吝分享
        不过,相信你也早就意识到,若单纯论海量数据处理面试题,本blog内的有关海量数据处理面试题的文章已涵盖了你能在网上所找到的70~80%。但有点,必须负责任的敬告大家:无论是这些海量数据处理面试题也好,还是算法也好,面试时70~80%的人不是倒在这两方面,而是倒在基础之上(诸如语言,数据库,操作系统,网络协议等等),所以,无论任何时候,基础最重要,没了基础,便什么都不是
        最后,推荐几个求职/算法/刷题的相关课程,包括LeetCode直播刷题等等,感兴趣的可以看下:https://www.julyedu.com/category/index/1
        OK,本文若有任何问题,欢迎随时不吝留言,评论,赐教,谢谢。完。

    重大消息:我的新书《编程之法:面试和算法心得》终于在2015年10月14日起上架开卖了!京东抢购地址http://item.jd.com/11786791.html。京东、当当、亚马逊等各大网店均已有现货销售。

    展开全文
  • 海量数据问题总结

    千次阅读 2019-05-11 16:20:01
    本博客已弃用,当时存在一些小细节错误后期也不再修改了 欢迎来我的新博客 前言:在这个用户量爆炸、并发极高的互联网时代,对于如今...海量数据处理能力是一家大公司必须要做得非常硬的一个技术块,这样才能在互...

    本博客已弃用,当时存在一些小细节错误后期也不再修改了

    欢迎来我的新博客

    前言:在这个用户量爆炸、并发极高的互联网时代,对于如今的IT行业,在极大量的数据处理这一块的能力,无疑某些程度上是其技术实力的体现。例如淘宝、支付宝在双十一这天的峰值时期,每秒要处理的数据量几乎都是百亿级别,新浪微博在春晚将要处理一亿左右人的抢红包活动。海量数据处理能力是一家大公司必须要做得非常硬的一个技术块,这样才能在互联网行业的激烈竞争中站稳脚跟。因此,海量数据问题在面试中也是经常问到的,并且也是很能体现你的知识底蕴的一个方面。

    下面我们通过七个问题来进行讲解。

    Ps:本文需要堆、哈希、位图、布隆这些知识基础,若你不明白这些目前还是先不要看下去了,当然,没有耐心去一个一个方法看的肯定也看不下去。

    正文:

    海量数据的定义:内存里存不下或者会占用太多内存的数据量。(注意:我们说的是内存,因为这些数据都是要拿来直接用的)

    注意:在这里讲的是方法,因为别人问你也不是要你自己能实现一个处理海量的数据的轮子,重要的是能表述清楚原理,因此无关紧要的细节各位自行忽略(比如下面的log file怎么取模,log file中的IP怎么提取之类的问题)

    1)给⼀一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址。如何找到top K的IP?

            这样的问题如果出现在数据量较小的情形下,用一个map或者unordered_map都能很快的处理,但是100G这样的量级放在一个map里是绝对不可行的。因此,我们采用哈希切分。

            什么是哈希切分?

            100G文件我们无法处理,是1G文件我们能处理,100M文件我们能处理

            因此,哈希切分的第一步:映射切分(分治)

            首先把所有log file中的IP挨个提取出来,然后这个总量为100G的IP文件,我们通过对所有进行IP%1000这样一个操作,把100G的大文件切分成了1000个100M的小文件

            第二步:对每个切分小文件进行统计

            这个统计过程一般直接用unordered_map<IP,size_t>就能完成,然后在每个切分小文件里,我们很快就能找到出现次数最多的那个IP

            第三步:排序

            由第二步得到了1000个出现频率最高的IP后,由于我们在这里只用找出出现次数最多的IP,那么O(n)次内遍历一趟就能找出来,当然,如果找前k个,那就用一个容量为k的小堆就能完成。

            过程如图(后面大部分题都是这么个模式,就不再画图了)

            

            好了,思考的同学肯定会有疑问,这样做难道不会出现相同的IP没有被映射到一个文件的问题嘛?当然不会啦。因为第一步的哈希映射是等价映射,相同的IP%1000后是一定会被映射到同一小文件里的,因此不存在这种问题。同时,我们这里%1000改成%100也是同样可以的,只不过%1000比%100更能避免同一小文件里映射了太多IP的问题。

            总得来说就是:映射->统计->排序

            OK,有了对哈希切分的基础,后面的好几个问题用哈希切分就迎刃而解了,但是这些问题我们就不说哈希切分这个方法了,对于这类问题,你会发现哈希切分几乎是个万金油的方法╭(′▽`)╭(′▽`)╯

    2)给定100亿个整数,设计算法找到只出现一次的整数

            这个问题如果出现在数据量比较小的情况下,把位图(BitSet)进行扩展无疑是最节省空间与时间的方法。

            把位图每个标记位由普通位图的一个变为两个,因为普通位图只能标记在或不在,而我们的要求是判断是否只出现一次,因此我们用两个位来标记就好啦,因为两个位可以表示:0次、1次、2次、3次,但这是100亿个整数诶!

            我们先做个计算:假定我们的位图用两个位为来标记一个数字,一个字节就能标记4个正数,而我们有100亿个,那么就需要100/4 = 25亿字节,10亿字节约等于1g,也就是说我们的位图也至少要开2.5个g左右的内存空间。2.5g内存对如今的计算机似乎也不大,但如果我就是要你不用超过1g内存呢 ◔ ‸◔?

            机灵的你一定想到了哈希切分!没错,我们先哈希切分,然后每次用位图统计只出现一次的正数,即使我们切10份,每次用位图也就需要250M空间,这样就能把内存占用控制在250M左右,这样问题就解决了。

     

     3)给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集 

            有了前面两题的基础,这个问题是不是就迎刃而解了,这道题在上题的基础上,我们只要把位图改为用普通位图,然后该切分还是切分,我们再来计算一下:现在一个字节可以标记八个整数,那么我们对于每个文件需要  100/8 = 12.5亿字节,约等于1.25g左右,因为有两个文件,我们需要两个位图,那么我们要就要2.5g左右空间。

            同样,我们对两个文件分别分10份,每次使用两个位图,这两个位图按位与得到的结果就记录好了交集,每次我们又把交集里出现的正数统计好,记录下来,这样内存也可以很好的控制在1g以下。

    4)1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数

            这个问题非常简单了,就是把第二题中要找的只出现一次的整数,改成找出现一次、出现两次的整数,其他的就不符合哦我们要求啦,方法仍然就是把普通位图进行扩展。

    5)给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法

            为了方便讲解,避免不必要的讨论,我们假定这个query就是字符串类型。

            首先,对于字符串类型,直接用位图肯定是没法用了,那我们就用布隆过滤器(BloomFilter)

            布隆的特点:存在不一定是准确的(虽然一般几率较小),不存在是一定准确的

            因此,对于近似算法,我们用普通的布隆过滤器能做到的就是近似准确的,毕竟HasnFunc对于字符串的映射到整型是无限集到有限集的映射,是有可能出现不同字符串映射到同一个位的,即使几率很小。

            同样,都不用我说你也知道,先哈希切分,再布隆,每次把两个布隆按位与的结果记录下来即可。

            对于精确算法,我们是这样实现的,把布隆进行扩展,原来用一个HashFunc映射一次来映射一个位,那么我们用N个字符串HashFunc来映射N个位,(N的取值是有具体理论的,这里不进行赘述),占用的空间回事原来的N倍,但是这样出现误判的几率就几乎是不可能有了。做了这个处理后,后面的步骤是相同的。

    6)如何扩展BloomFilter使得它支持删除元素的操作?如何扩展BloomFilter使得它支持计数操作?

            在这道题里说的布隆当然是说的精确的布隆过滤器,它是不支持删除的,因为删除的时候会产生对其他数据的连锁效应,比两个字符串经过三个映射后,其可能有一个映射位是相同的,这个时候删除这两个字符串中的哪一个字符串都不太好处理。这两个问题其实问的是同一件事,只要支持了计数,那么就必然是置产删除的。   

            那么怎么使它支持计数呢?我们原来是每个HashFunc会映射到一个位,现在每个HashFunc映射到n个位来计数(类似位图的扩展),比如n为2,那么就能表示这个映射到的位被标记了0、1、2、3次,每次Set操作,该位+1,每次ReSet操作,该位-1,这样就能做到计数与删除了,当然,对空间的消耗也是成倍的,并且,这个计数位到底应该有几个对于要处理的问题是合适的也是一个要考虑的问题,比如n为2最多才能被标记三次。

    7)与(1)题条件相同,如何直接用Linux系统命令实现找到top K的IP?

            第一步要做的仍然是哈希切分,然后每一组文件里要用到awk sort uniq  具体要怎么用还得看Log file 中每一行的格式。

            

    展开全文
  • 海量数据中找出前k大数(topk问题)

    千次阅读 2019-02-25 20:58:16
    前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些。  先拿10000个数建堆,然后一...

    https://www.cnblogs.com/qlky/p/7512199.html

    前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些。

            先拿10000个数建堆,然后一次添加剩余元素,如果大于堆顶的数(10000中最小的),将这个数替换堆顶,并调整结构使之仍然是一个最小堆,这样,遍历完后,堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O(mlogm),算法的时间复杂度为O(nmlogm)(n为10亿,m为10000)。

            优化的方法:可以把所有10亿个数据分组存放,比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数,合并到一起在再找出最终的结果。

            以上就是面试时简单提到的内容,下面整理一下这方面的问题:

    top K问题

            在大规模数据处理中,经常会遇到的一类问题:在海量数据中找出出现频率最好的前k个数,或者从海量数据中找出最大的前k个数,这类问题通常被称为top K问题。例如,在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载最高的前10首歌等。

            针对top K类问题,通常比较好的方案是分治+Trie树/hash+小顶堆(就是上面提到的最小堆),即先将数据集按照Hash方法分解成多个小数据集,然后使用Trie树活着Hash统计每个小数据集中的query词频,之后用小顶堆求出每个数据集中出现频率最高的前K个数,最后在所有top K中求出最终的top K。

    eg:有1亿个浮点数,如果找出期中最大的10000个?

            最容易想到的方法是将数据全部排序,然后在排序后的集合中进行查找,最快的排序算法的时间复杂度一般为O(nlogn),如快速排序。但是在32位的机器上,每个float类型占4个字节,1亿个浮点数就要占用400MB的存储空间,对于一些可用内存小于400M的计算机而言,很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求(我机器内存都是8GB),该方法也并不高效,因为题目的目的是寻找出最大的10000个数即可,而排序却是将所有的元素都排序了,做了很多的无用功。

            第二种方法为局部淘汰法,该方法与排序方法类似,用一个容器保存前10000个数,然后将剩余的所有数字——与容器内的最小数字相比,如果所有后续的元素都比容器内的10000个数还小,那么容器内这个10000个数就是最大10000个数。如果某一后续元素比容器内最小数字大,则删掉容器内最小元素,并将该元素插入容器,最后遍历完这1亿个数,得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O(n+m^2),其中m为容器的大小,即10000。

            第三种方法是分治法,将1亿个数据分成100份,每份100万个数据,找到每份数据中最大的10000个,最后在剩下的100*10000个数据里面找出最大的10000个。如果100万数据选择足够理想,那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下:用快速排序的方法,将数据分为2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大堆个数N小于10000个,就在小的那堆里面快速排序一次,找第10000-n大的数字;递归以上过程,就可以找到第1w大的数。参考上面的找出第1w大数字,就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^6*4=4MB,一共需要101次这样的比较。

            第四种方法是Hash法。如果这1亿个书里面有很多重复的数,先通过Hash法,把这1亿个数字去重复,这样如果重复率很高的话,会减少很大的内存用量,从而缩小运算空间,然后通过分治法或最小堆法查找最大的10000个数。

            第五种方法采用最小堆。首先读入前10000个数来创建大小为10000的最小堆,建堆的时间复杂度为O(mlogm)(m为数组的大小即为10000),然后遍历后续的数字,并于堆顶(最小)数字进行比较。如果比最小的数小,则继续读取后续数字;如果比堆顶数字大,则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为O(nmlogm),空间复杂度是10000(常数)。

    实际运行:

            实际上,最优的解决方案应该是最符合实际设计需求的方案,在时间应用中,可能有足够大的内存,那么直接将数据扔到内存中一次性处理即可,也可能机器有多个核,这样可以采用多线程处理整个数据集。

           下面针对不容的应用场景,分析了适合相应应用场景的解决方案。

    (1)单机+单核+足够大内存

            如果需要查找10亿个查询次(每个占8B)中出现频率最高的10个,考虑到每个查询词占8B,则10亿个查询次所需的内存大约是10^9 * 8B=8GB内存。如果有这么大内存,直接在内存中对查询次进行排序,顺序遍历找出10个出现频率最大的即可。这种方法简单快速,使用。然后,也可以先用HashMap求出每个词出现的频率,然后求出频率最大的10个词。

    (2)单机+多核+足够大内存

            这时可以直接在内存总使用Hash方法将数据划分成n个partition,每个partition交给一个线程处理,线程的处理逻辑同(1)类似,最后一个线程将结果归并。

            该方法存在一个瓶颈会明显影响效率,即数据倾斜。每个线程的处理速度可能不同,快的线程需要等待慢的线程,最终的处理速度取决于慢的线程。而针对此问题,解决的方法是,将数据划分成c×n个partition(c>1),每个线程处理完当前partition后主动取下一个partition继续处理,知道所有数据处理完毕,最后由一个线程进行归并。

    (3)单机+单核+受限内存

            这种情况下,需要将原数据文件切割成一个一个小文件,如次啊用hash(x)%M,将原文件中的数据切割成M小文件,如果小文件仍大于内存大小,继续采用Hash的方法对数据文件进行分割,知道每个小文件小于内存大小,这样每个文件可放到内存中处理。采用(1)的方法依次处理每个小文件。

    (4)多机+受限内存

            这种情况,为了合理利用多台机器的资源,可将数据分发到多台机器上,每台机器采用(3)中的策略解决本地的数据。可采用hash+socket方法进行数据分发。

     

            从实际应用的角度考虑,(1)(2)(3)(4)方案并不可行,因为在大规模数据处理环境下,作业效率并不是首要考虑的问题,算法的扩展性和容错性才是首要考虑的。算法应该具有良好的扩展性,以便数据量进一步加大(随着业务的发展,数据量加大是必然的)时,在不修改算法框架的前提下,可达到近似的线性比;算法应该具有容错性,即当前某个文件处理失败后,能自动将其交给另外一个线程继续处理,而不是从头开始处理。

            top K问题很适合采用MapReduce框架解决,用户只需编写一个Map函数和两个Reduce 函数,然后提交到Hadoop(采用Mapchain和Reducechain)上即可解决该问题。具体而言,就是首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上,最好可以让数据划分后一次读入内存,这样不同的机器负责处理不同的数值范围,实际上就是Map。得到结果后,各个机器只需拿出各自出现次数最多的前N个数据,然后汇总,选出所有的数据中出现次数最多的前N个数据,这实际上就是Reduce过程。对于Map函数,采用Hash算法,将Hash值相同的数据交给同一个Reduce task;对于第一个Reduce函数,采用HashMap统计出每个词出现的频率,对于第二个Reduce 函数,统计所有Reduce task,输出数据中的top K即可。

            直接将数据均分到不同的机器上进行处理是无法得到正确的结果的。因为一个数据可能被均分到不同的机器上,而另一个则可能完全聚集到一个机器上,同时还可能存在具有相同数目的数据。

     

    以下是一些经常被提及的该类问题。

    (1)有10000000个记录,这些查询串的重复度比较高,如果除去重复后,不超过3000000个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。请统计最热门的10个查询串,要求使用的内存不能超过1GB。

    (2)有10个文件,每个文件1GB,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。按照query的频度排序。

    (3)有一个1GB大小的文件,里面的每一行是一个词,词的大小不超过16个字节,内存限制大小是1MB。返回频数最高的100个词。

    (4)提取某日访问网站次数最多的那个IP。

    (5)10亿个整数找出重复次数最多的100个整数。

    (6)搜索的输入信息是一个字符串,统计300万条输入信息中最热门的前10条,每次输入的一个字符串为不超过255B,内存使用只有1GB。

    (7)有1000万个身份证号以及他们对应的数据,身份证号可能重复,找出出现次数最多的身份证号。

     

    重复问题

            在海量数据中查找出重复出现的元素或者去除重复出现的元素也是常考的问题。针对此类问题,一般可以通过位图法实现。例如,已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。
     

            本题最好的解决方法是通过使用位图法来实现。8位整数可以表示的最大十进制数值为99999999。如果每个数字对应于位图中一个bit位,那么存储8位整数大约需要99MB。因为1B=8bit,所以99Mbit折合成内存为99/8=12.375MB的内存,即可以只用12.375MB的内存表示所有的8位数电话号码的内容。

     

    Top K问题的两种解决思路

     

    Top K问题在数据分析中非常普遍的一个问题(在面试中也经常被问到),比如:

    从20亿个数字的文本中,找出最大的前100个。

    解决Top K问题有两种思路,

    • 最直观:小顶堆(大顶堆 -> 最小100个数);
    • 较高效:Quick Select算法。

    LeetCode上有一个问题215. Kth Largest Element in an Array,类似于Top K问题。

    1. 堆

    小顶堆(min-heap)有个重要的性质——每个结点的值均不大于其左右孩子结点的值,则堆顶元素即为整个堆的最小值。JDK中PriorityQueue实现了数据结构堆,通过指定comparator字段来表示小顶堆或大顶堆,默认为null,表示自然序(natural ordering)。

    小顶堆解决Top K问题的思路:小顶堆维护当前扫描到的最大100个数,其后每一次的扫描到的元素,若大于堆顶,则入堆,然后删除堆顶;依此往复,直至扫描完所有元素。Java实现第K大整数代码如下:

    public int findKthLargest(int[] nums, int k) {
      PriorityQueue<Integer> minQueue = new PriorityQueue<>(k);
      for (int num : nums) {
        if (minQueue.size() < k || num > minQueue.peek())
          minQueue.offer(num);
        if (minQueue.size() > k)
          minQueue.poll();
      }
      return minQueue.peek();
    }

    2. Quick Select

    Quick Select [1]脱胎于快排(Quick Sort),两个算法的作者都是Hoare,并且思想也非常接近:选取一个基准元素pivot,将数组切分(partition)为两个子数组,比pivot大的扔左子数组,比pivot小的扔右子数组,然后递推地切分子数组。Quick Select不同于Quick Sort的是其没有对每个子数组做切分,而是对目标子数组做切分。其次,Quick Select与Quick Sort一样,是一个不稳定的算法;pivot选取直接影响了算法的好坏,worst case下的时间复杂度达到了O(n2)。下面给出Quick Sort的Java实现:

    public void quickSort(int arr[], int left, int right) {
      if (left >= right) return;
      int index = partition(arr, left, right);
      quickSort(arr, left, index - 1);
      quickSort(arr, index + 1, right);
    }
    
    // partition subarray a[left..right] so that a[left..j-1] >= a[j] >= a[j+1..right]
    // and return index j
    private int partition(int arr[], int left, int right) {
      int i = left, j = right + 1, pivot = arr[left];
      while (true) {
        while (i < right && arr[++i] > pivot)
          if (i == right) break;
        while (j > left && arr[--j] < pivot)
          if (j == left) break;
        if (i >= j) break;
        swap(arr, i, j);
      }
      swap(arr, left, j);  // swap pivot and a[j]
      return j;
    }
    
    private void swap(int[] arr, int i, int j) {
      int tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
    }

    Quick Select的目标是找出第k大元素,所以

    • 若切分后的左子数组的长度 > k,则第k大元素必出现在左子数组中;
    • 若切分后的左子数组的长度 = k-1,则第k大元素为pivot;
    • 若上述两个条件均不满足,则第k大元素必出现在右子数组中。

    Quick Select的Java实现如下:

    public int findKthLargest(int[] nums, int k) {
      return quickSelect(nums, k, 0, nums.length - 1);
    }
    
    // quick select to find the kth-largest element
    public int quickSelect(int[] arr, int k, int left, int right) {
      if (left == right) return arr[right];
      int index = partition(arr, left, right);
      if (index - left + 1 > k)
        return quickSelect(arr, k, left, index - 1);
      else if (index - left + 1 == k)
        return arr[index];
      else
        return quickSelect(arr, k - index + left - 1, index + 1, right);
    
    }

    上面给出的代码都是求解第k大元素;若想要得到Top K元素,仅需要将代码做稍微的修改:比如,扫描完成后的小顶堆对应于Top K,Quick Select算法用中间变量保存Top K元素。

    展开全文
  • 大数据与海量数据的区别

    千次阅读 2019-06-12 23:37:14
    如果仅仅是海量的结构性数据,那么解决的办法就比较的单一,用户通过购买更多的存储设备,提高存储设备的效率等解决此类问题。然而,当人们发现数据库中的数据可以分为三种类型:结构性数据、非结构性数据以及半结构...

    如果仅仅是海量的结构性数据,那么解决的办法就比较的单一,用户通过购买更多的存储设备,提高存储设备的效率等解决此类问题。然而,当人们发现数据库中的数据可以分为三种类型:结构性数据、非结构性数据以及半结构性数据等复杂情况时,问题似乎就没有那么简单了。

    大数据汹涌来袭

    当类型复杂的数据汹涌袭来,那么对于用户IT系统的冲击又会是另外一种处理方式。很多业内专家和第三方调查机构通过一些市场调查数据发现,大数据时代即将到来。有调查发现,这些复杂数据中有85%的数据属于广泛存在于社交网络、物联网、电子商务等之中的非结构化数据。这些非结构化数据的产生往往伴随着社交网络、移动计算和传感器等新的渠道和技术的不断涌现和应用。

    如今大数据的概念也存在着很多的炒作和大量的不确定性。为此,编者详细向一些业内专家详细了解有关方面的问题,请他们谈一谈,大数据是什么和不是什么,以及如何应对大数据等问题,将系列文章的形式与网友见面。

    有人将多TB数据集也称作”大数据”。据市场研究公司IDC统计,数据使用预计将增长44倍,全球数据使用量将达到大约35.2ZB(1ZB
    = 10亿TB)。然而,单个数据集的文件尺寸也将增加,导致对更大处理能力的需求以便分析和理解这些数据集。

    EMC曾经表示,它的1000多个客户在其阵列中使用1PB(千兆兆)以上的数据数据,这个数字到2020年将增长到10万。一些客户在一两年内还将开始使用数千倍多的数据,1EB(1艾字节
    = 10亿GB)或者更多的数据。

    对大企业而言,大数据的兴起部分是因为计算能力可用更低的成本获得,且各类系统如今已能够执行多任务处理。其次,内存的成本也在直线下降,企业可以在内存中处理比以往更多的数据,另外是把计算机聚合成服务器集群越来越简单。IDC认为,这三大因素的结合便催生了大数据。同时,IDC还表示,某项技术要想成为大数据技术,首先必须是成本可承受的,其次是必须满足IBM所描述的三个”V”判据中的两个:多样性(variety)、体量(volume)和速度(velocity)。

    大数据与海量数据的区别

    多样性是指,数据应包含结构化的和非结构化的数据。

    体量是指聚合在一起供分析的数据量必须是非常庞大的。

    而速度则是指数据处理的速度必须很快。

    大数据”并非总是说有数百个TB才算得上。根据实际使用情况,有时候数百个GB的数据也可称为大数据,这主要要看它的第三个维度,也就是速度或者时间维度。

    Garter表示,全球信息量正在以59%以上的年增长率增长,而量是在管理数据、业务方面的显著挑战,IT领袖必须侧重在信息量、种类和速度上。

    量:企业系统内部的数据量的增加是由交易量、其它传统数据类型和新的数据类型引发的。过多的量是一个存储的问题,但过多的数据也是一个大量分析的问题。

    种类:IT领袖在将大量的交易信息转化为决策上一直存在困扰 – 现在有更多类型的信息需要分析 –
    主要来自社交媒体和移动(情景感知)。种类包括表格数据(数据库)、分层数据、文件、电子邮件、计量数据、视频、静态图像、音频、股票行情数据、金融交易和其它更多种类。

    速度:这涉及到数据流、结构化记录的创建,以及访问和交付的可用性。速度意味着正在被生成的数据有多快和数据必须被多快地处理以满足需求。

    虽然大数据是一个重大问题,Gartner分析师表示,真正的问题是让大数据更有意义,在大数据里面寻找模式帮助组织机构做出更好的商业决策。

    诸子百家谈如何定义”大数据”

    尽管”Big Data”可以翻译成大数据或者海量数据,但大数据和海量数据是有区别的。

    定义一:大数据 = 海量数据 + 复杂类型的数据

    Informatica中国区首席产品顾问但彬认为:”大数据”包含了”海量数据”的含义,而且在内容上超越了海量数据,简而言之,”大数据”是”海量数据”+复杂类型的数据。

    但彬进一步指出:大数据包括交易和交互数据集在内的所有数据集,其规模或复杂程度超出了常用技术按照合理的成本和时限捕捉、管理及处理这些数据集的能力。

    大数据是由三项主要技术趋势汇聚组成:

    海量交易数据:在从
    ERP应用程序到数据仓库应用程序的在线交易处理(OLTP)与分析系统中,传统的关系数据以及非结构化和半结构化信息仍在继续增长。随着企业将更多的数据和业务流程移向公共和私有云,这一局面变得更加复杂。
    
    海量交互数据:这一新生力量由源于
    Facebook、Twitter、LinkedIn
    及其它来源的社交媒体数据构成。它包括了呼叫详细记录(CDR)、设备和传感器信息、GPS和地理定位映射数据、通过管理文件传输(Manage
    File Transfer)协议传送的海量图像文件、Web 文本和点击流数据、科学信息、电子邮件等等。
    
    海量数据处理:大数据的涌现已经催生出了设计用于数据密集型处理的架构,例如具有开放源码、在商品硬件群中运行的
    Apache Hadoop。对于企业来说,难题在于以具备成本效益的方式快速可靠地从 Hadoop 中存取数据。

    定义二:大数据包括A、B、C三个要素

    如何理解大数据?NetApp
    大中华区总经理陈文认为,大数据意味着通过更快获取信息来使做事情的方式变得与众不同,并因此实现突破。大数据被定义为大量数据(通常是非结构化的),它要求我们重新思考如何存储、管理和恢复数据。那么,多大才算大呢?考虑这个问题的一种方式就是,它是如此之大,以至于我们今天所使用的任何工具都无法处理它,因此,如何消化数据并把它转化成有价值的洞见和信息,这其中的关键就是转变。

    基于从客户那里了解的工作负载要求, NetApp所理解的大数据包括A、B、C三个要素:分析(Analytic),带宽(Bandwidth)和内容(Content)。

    1. 大分析(Big Analytics),帮助获得洞见 –
      指的是对巨大数据集进行实时分析的要求,它能带来新的业务模式,更好的客户服务,并实现更好的结果。

    2. 高带宽(Big Bandwidth),帮助走得更快 –
      指的是处理极端高速的关键数据的要求。它支持快速有效地消化和处理大型数据集。

    3. 大内容(Big Content),不丢失任何信息-
      指的是对于安全性要求极高的高可扩展的数据存储,并能够轻松实现恢复。它支持可管理的信息内容存储库、而不只是存放过久的数据,并且能够跨越不同的大陆板块。

    大数据是一股突破性的经济和技术力量,它为 IT
    支持引入了新的基础架构。大数据解决方案消除了传统的计算和存储的局限。借助于不断增长的私密和公开数据,一种划时代的新商业模式正在兴起,它有望为大数据客户带来新的实质性的收入增长点以及富于竞争力的优势。

    转载于:https://blog.51cto.com/10975663/2085253

    展开全文
  • Mysql海量数据处理

    千次阅读 2019-03-02 11:20:20
    一说海量数据有人就说了直接用大数据,那只能说不太了解这块,为此我们才要好好的去讲解一下海量的处理 海量数据的处理分为两种情况 1)表中有海量数据,但是每天不是很快的增长 2)表中有还流量数据,而且每天很...
  • 海量数据处理算法总结【超详解】

    千次阅读 2018-05-04 11:05:37
    1. Bloom Filter【Bloom Filter】Bloom Filter(BF)是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。它是一个判断元素是否存在集合的快速的概率算法。...
  • 海量数据处理技巧

    千次阅读 2018-08-02 20:07:18
    当高性能硬件的普及还跟不上这样的数据大潮时,如何在有限的时空资源内处理海量数据成为了计算机科学以及数理统计等领域最大的挑战。 所谓“数据处理”,在本文中特指通过计算机技术,对海量数据进行存储、统计、...
  • 随着互联网应用的广泛普及,海量数据的存储和访问成为了系统设计的瓶颈问题。对于一个大型的互联网应用,每天几十亿的PV无疑对数据库造成了相当高的负载。对于系统的稳定性和扩展性造成了极大的问题。 水平切分...
  • 腾讯云图(TCV)使用指南

    千次阅读 2019-12-09 09:34:01
    腾讯云图(Tencent Cloud Visualization,TCV) 是腾讯云旗下的一站式数据可视化展示平台,旨在帮助用户快速通过可视化图表展示海量数据,10 分钟零门槛打造出专业大屏数据展示。精心预设多种行业模板,极致展示数据...
  • 1、海量日志数据,提取出某日访问百度次数最多的那个IP。 此题,在我之前的一篇文章算法里头有所提到,当时给出的方案是:IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进行统计。...
  • 十道海量数据处理面试题与十个方法大总结

    万次阅读 多人点赞 2013-08-01 14:27:34
    海量数据处理:十道面试题与十个海量数据处理方法总结作者:July、youwang、yanxionglu。时间:二零一一年三月二十六日本文之总结:教你如何迅速秒杀掉:99%的海量数据处理面试题。有任何问题,欢迎随时交流、指正。...
  • 海量数据处理面试题集锦

    万次阅读 多人点赞 2012-09-11 23:17:34
    十七道海量数据处理面试题与Bit-map详解作者:小桥流水,redfox66,July。前言 本博客内曾经整理过有关海量数据处理的10道面试题(十道海量数据处理面试题与十个方法大总结),此次除了重复了之前的10道面试题之后...
  • 声明: 原文引用参考July大神的csdn博客文章 => 海量处理面试题 海量数据处理概述所谓海量数据处理,就是数据量太大,无法在较短时间内迅速解决,无法一次性装入内存。本文在前人的基础上总结一下解决此类问题的办法...
  • 从hadoop框架与MapReduce模式中谈海量数据处理前言 几周前,当我最初听到,以致后来初次接触Hadoop与MapReduce这两个东西,我便稍显兴奋,觉得它们很是神秘,而神秘的东西常能勾起我的兴趣,在看过介绍它们的文章或...
  • 什么是海量数据

    2018-04-18 15:38:15
    1.什么是海量数据? 海量数据,顾名思义,数据量一般大得多. 海量数据一般是相对当前计算机处理能力而言 的,今天看来是海量数据,也许随着计算机硬件能力的提升在不久的将来就不算海量数据了.即使是同一时期,...
  • 海量数据处理之Bloom Filter详解

    万次阅读 多人点赞 2013-10-21 10:20:19
    海量数据处理之Bloom Filter详解 前言 本博客内曾已经整理过十道海量数据处理面试题与十个方法大总结。接下来,本博客内会重点分析那些海量数据处理的方法,并重写十道海量数据处理的面试题。如果有任何问题,欢迎...
  • 海量数据处理算法

    千次阅读 2017-08-14 20:00:43
    海量信息即大规模数据,随着互联网技术的发展,...在海量数据中提取信息,不同于常规量级数据中提取信息,在海量信息中提取有用数据,会存在以下几个方面的问题: (1)数据量过大,数据中什么情况都可能
  • 海量数据的存储 海量数据的计算 大数据处理的主要应用场景 前言:大数据技术诞生之初,就是为了解决海量数据的存储和计算问题。 大数据起源于Google。 Google是当时世界上(尽管目前也是)最大的搜索引擎公司...
  • 如何应对海量数据时代的挑战

    万次阅读 2012-06-29 17:48:54
    如何应对海量数据时代的挑战? 大数据的浪潮有多迅猛?IDC在2006年估计全世界产生的数据量是0.18ZB(1ZB=100万PB),而今年这个数字已经提升了一个数量级,达到1.8ZB,差不多对应全世界每个人一块100多GB的硬盘。...
  • 海量数据处理方案

    千次阅读 2018-03-17 22:21:28
    什么是海量数据? 正如《逍遥游》中的一句话:北冥有鱼,其名为鲲,鲲之大,一锅炖不下,化而为鸟,其名为鹏,鹏之大,需要两个烧烤架;简单的可以把这里的海量数据理解为这里的鲲鹏 ,数据大到一个服务器存不下,...
1 2 3 4 5 ... 20
收藏数 218,763
精华内容 87,505
关键字:

海量数据