{"action":"opened","issue":{"url":"https://api.github.com/repos/DreamClubFrom2015/ForumDreamCode/issues/11","labels_url":"https://api.github.com/repos/DreamClubFrom2015/ForumDreamCode/issues/11/labels{/name}","comments_url":"https://api.github.com/repos/DreamClubFrom2015/ForumDreamCode/issues/11/comments","events_url":"https://api.github.com/repos/DreamClubFrom2015/ForumDreamCode/issues/11/events","html_url":"https://github.com/DreamClubFrom2015/ForumDreamCode/issues/11","id":119514563,"number":11,"title":"### 大数据处理方法---面试题目","user":{"login":"nijiazhi","id":10481927,"avatar_url":"https://avatars.githubusercontent.com/u/10481927?v=3","gravatar_id":"","url":"https://api.github.com/users/nijiazhi","html_url":"https://github.com/nijiazhi","followers_url":"https://api.github.com/users/nijiazhi/followers","following_url":"https://api.github.com/users/nijiazhi/following{/other_user}","gists_url":"https://api.github.com/users/nijiazhi/gists{/gist_id}","starred_url":"https://api.github.com/users/nijiazhi/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nijiazhi/subscriptions","organizations_url":"https://api.github.com/users/nijiazhi/orgs","repos_url":"https://api.github.com/users/nijiazhi/repos","events_url":"https://api.github.com/users/nijiazhi/events{/privacy}","received_events_url":"https://api.github.com/users/nijiazhi/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2015-11-30T15:27:36Z","updated_at":"2015-11-30T15:27:36Z","closed_at":null,"body":"### 1、\t海量日志数据，提取出某日访问百度次数最多的那个IP。\r\n\r\n既然是海量数据处理，那么可想而知，给我们的数据那就一定是海量的。针对这个数据的海量，我们如何着手呢?对的，无非就是分而治之/hash映射 + hash统计 + 堆/快速/归并排序，说白了，就是先映射，而后统计，最后排序：\r\n1.分而治之/hash映射：针对数据太大，内存受限，只能是：把大文件化成(取模映射)小文件，即16字方针：大而化小，各个击破，缩小规模，逐个解决\r\n2.hash_map统计：当大文件转化了小文件，那么我们便可以采用常规的hash_map(ip，value)来进行频率统计。\r\n3.堆/快速排序：统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP。\r\n   具体而论，则是： “首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如%1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map对那1000个文件中的所有IP进行频率统计，然后依次找出各个文件中频率最大的那个IP）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。\r\n\r\n### 2、\t搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门），请你统计最热门的10个查询串，要求使用的内存不能超过1G\r\n\r\n\r\n由上面第1题，我们知道，数据大则划为小的，如如一亿个Ip求Top 10，可先%1000将ip分到1000个小文件中去，并保证一种ip只出现在一个文件中，再对每个小文件中的ip进行hashmap计数统计并按数量排序，最后归并或者最小堆依次处理每个小文件的top10以得到最后的结。\r\n但如果数据规模比较小，能一次性装入内存呢?比如这第2题，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query为255Byte，因此我们可以考虑把他们都放进内存中去（300万个字符串假设没有重复，都是最大长度，那么最多占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理），而现在只是需要一个合适的数据结构，在这里，HashTable绝对是我们优先的选择。\r\n所以我们放弃分而治之/hash映射的步骤，直接上hash统计，然后排序。\r\n针对此类典型的TOP K问题，采取的对策往往是：hashmap + 堆。如下所示：\r\n1.\thash_map统计：先对这批海量数据预处理。具体方法是：维护一个Key为Query字串，Value为该Query出现次数的HashTable，即hash_map(Query，Value)，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计；\r\n2.\t堆排序：第二步、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。即借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比。所以，我们最终的时间复杂度是：O（N） + N' * O（logK），（N为1000万，N’为300万）。\r\n\r\n### 3、2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。\r\n有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。\r\n\r\n### 4、5亿个int找它们的中位数。\r\n这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nBloom Filter\r\n------\r\nBloom Filter是一种空间效率很高的随机数据结构，它的原理是，当一个元素被加入集合时，通过K个Hash函数将这个元素映射成一个位阵列（Bit array）中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检索元素一定不在；如果都是1，则被检索元素很可能在。这就是布隆过滤器的基本思想。\r\n    但Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。\r\n有人可能想知道它的中文叫法，倒是有被译作称布隆过滤器。该不该译，译的是否恰当，由诸君品之。下文之中，如果有诸多公式不慎理解，也无碍，只作稍稍了解即可。\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n### 1、集合表示和元素查询\r\n下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。\r\n \r\n为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位，即第二个“1“处）。   \r\n \r\n在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有hi(y)的位置都是1（1≤i≤k），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素（因为y1有一处指向了“0”位）。y2或者属于这个集合，或者刚好是一个false positive。\r\n \r\n### 2、错误率估计（不讲）\r\n前面我们已经提到了，Bloom Filter在判断一个元素是否属于它表示的集合时会有一定的错误率（false positive rate），下面我们就来估计错误率的大小。在估计之前为了简化模型，我们假设kn<m且各个哈希函数是完全随机的。当集合S={x1, x2,…,xn}的所有元素都被k个哈希函数映射到m位的位数组中时，这个位数组中某一位还是0的概率是：\r\n \r\n其中1/m表示任意一个哈希函数选中这一位的概率（前提是哈希函数是完全随机的），(1-1/m)表示哈希一次没有选中这一位的概率。要把S完全映射到位数组中，需要做kn次哈希。某一位还是0意味着kn次哈希都没有选中它，因此这个概率就是（1-1/m）的kn次方。令p = e-kn/m是为了简化运算，这里用到了计算e时常用的近似：\r\n \r\n \r\n令ρ为位数组中0的比例，则ρ的数学期望E(ρ)= p’。在ρ已知的情况下，要求的错误率（false positive rate）为：\r\n \r\n(1-ρ)为位数组中1的比例，(1-ρ)k就表示k次哈希都刚好选中1的区域，即false positive rate。上式中第二步近似在前面已经提到了，现在来看第一步近似。p’只是ρ的数学期望，在实际中ρ的值有可能偏离它的数学期望值。M. Mitzenmacher已经证明[2] ，位数组中0的比例非常集中地分布在它的数学期望值的附近。因此，第一步的近似得以成立。分别将p和p’代入上式中，得：\r\n   \r\n \r\n相比p’和f’，使用p和f通常在分析中更为方便。\r\n\r\n### 3、 适用范围\r\n可以用来实现数据字典，进行数据的判重，或者集合求交集 \r\n还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况 下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=n*lg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。 \r\n\r\n举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。 \r\n\r\n    注意这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。\r\n\r\n\r\n### 4、给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。\r\n\r\n根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿，*8大概是320亿，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。 现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。 \r\n"}}