Methodology
一. Bloom Filter
1. 适用范围
可以用来实现数据字典，进行数据的判重，或者集合求交集
所以就适用于一些黑名单,垃圾邮件(只关键字，地址黑名单)等的过滤
2. 公式
举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。
3. 实例1
给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？
类似问题都要计算内存空间.
50亿条URL 内存空间: 5G * 64Bytes = 320 GB. 内存才4G. 不能一次load进入对比.
Solution1: Bloom Filter (允许错误率)
4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。
将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url (注意会有一定的错误率)
另外如果这些url ip是一一对应的，就可以转换成ip，则大大简单了(这句没懂)
这题原则上Bit-Map也可以，4G可以有340亿bit, 是不是知识因为 单Hash冲突率高放弃呢？
4. 实例2
If you were designing a web crawler, how would you avoid getting into infinite loops?
网络爬虫web crawler 在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道爬虫程序已经访问过那些URL. 问题转换成, 给一个URL，怎样知道爬虫程序是否已经访问过呢？
这是道CC150上面原题, 题目非常开放, 讨论的重心多有不同. CC150上和我们下面说的两个重点，根据面试实际情况来考虑。
web crawler原理一般就是BFS, 抓取一个页面，insert all links into queue, 然后再 抓取queue中剩余页面，如果没有visited标记url, 就会形成infinite loops. 所以每次访问一个url, 标记一下就可以，答成这种程度，真是去死吧，完全不行，要深入细节讨论. See following
方向1: 如何定义一个page 是否被访问过，link 还是 content？ 相似度权重
link: https://docs.google.com/1 和 https://docs.google.com/2 不一样，但是我们可以随意加 parameter 比如，https://docs.google.com/1?hehe=hehe 这其实和 https://docs.google.com/1 是一样的，如果以这个为标准，这样还是loop了.
content: 对于每一个link, 又有一些 random 生成的东西, 但是确实是一个页面. 所以没有best perfect way to define a “different” page.
解决方法: have some sort of estimation for degree of similarity.
Based on the content and the url, 如果page 跟其他pages相同的花，我们deprioritize its children.
For each page, we would come up with some sort of signature based on snippets of the content and the pages’s link. (这里我不懂怎么根据content和url产生签名，怎么用)
1. 每次打开一个page， 按照上述方法生成signature
2. 查询数据库，有没有这个签名的信息最近查询过得，
3. 如果有，insert page back at a low priority
4. 如果没有，爬虫抓取页面，insert it’s links into the database.
这样是不会终止的，但是我们can set a minimum priority that a page must have to be crawled.
数据库表应该至少是有url, signature两个字段， 每次读最上面的link, 然后计算signature，比较，如果有, 插入到前面, 没有，把当前这条记录放在后面.
方向2: 面对海量url, 如何确保visited url 有效存储？海量数据处理方案
稍微想想，就会有如下几种方案：
1. 将访问过的URL保存到数据库。
2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。
3. URL经过MD5或SHA-1等单向Hash希后再保存到HashSet或数据库. (对1, 2的空间优化)
4. Bit-Map方法。建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。
方法1~3都是将访问过的URL完整保存，方法4则只标记URL的一个映射位。以上方法在数据量较小的情况下都能完美解决问题，但是当数据量变得非常庞大时问题就来了。
各方法缺点：
方法1: 数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了？
这里要有概念，数据库的IO操作跟下面HashSet.contains 的内存操作相比非常耗时.
方法2: 太消耗内存。随着URL的增多，占用的内存会越来越多。就算只有1亿个URL，每个URL只算50个字符，就需要5GB内存。
HashSet需要放在内存，这样根本没有足够的空间存放.
方法3: 由于字符串经过MD5处理后的信息摘要长度只有128Bit，SHA-1处理后也只有160Bit，因此方法3比方法2节省了好几倍的内存。
50 Bytes → 128Bits (16 Bytes) 几乎三倍空间. 虽然OK了，但是作为设计题目，还是不够好，如果是一套题目给了我们数据，操作题目的话，我们可以用这种方法解决.
方法4: 消耗内存是相对较少的，但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么？若要降低冲突发生的概率到1%，就要将BitSet的长度设置为URL个数的100倍。
最终解决方法: Bloom Filter
假设4G 内存, 0.01出错率
40亿 Byte -> 320亿 Bit. 假设20亿 url. n = 20, 需要 260亿bit 做bit array. 320 > 260 可以，即便是空间小于260亿，也是可以的，知识出错率会上升.
1. 建立Bloom Filter
2. 从queue中取出link, 只需要对url 执行Bloom Filter集合查询即可.
3. visited, skip. not visited. 插入page into bloom filter. 抓取内容, children link 插入queue.
二. 分而知之 + Hash + HashMap 统计 + 堆/快速/ 归并排序
Hash自己没什么特别的，需要跟其他配合起来适用, 所以这里配合了 分治, HashMap, 排序等方法一起来讨论一类题目
1. 适用范围
几乎所有可以分治的海量数据题目. 这类题目一般都是求最值, top 10 等统计性的.
2. 基本方法
总体方法: 分而治之/hash映射 + hash统计 + 堆/快速/归并排序，说白了，就是先映射，而后统计，最后排序
- 分而治之/hash映射: 针对数据太大，内存受限，只能是：把大文件化成(取模映射)小文件，即16字方针：大而化小，各个击破，缩小规模，逐个解决
- hashMap统计: 当大文件转化了小文件，那么我们便可以采用常规的hash_map(ip，value)来进行频率统计。
- 堆/快速排序: 统计完了之后，便进行排序(可采取堆排序)，得到统计结果-- 最值。
3. 实例
海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是指定的 那一天，并且是访问百度的日志中的IP取出来(log一般按天排序，所以应该较好取出)，逐个写入到一个大文件中, 大文件体积未知，我们假设他是非常大不能存入内存的.
注意到IP是32位的，最多有个2^32个IP. 可以采用映射的方法，比如%1000，把整个大文件映射为1000个小文件. 对于每个小文件，我们假设size是可以load入内存的.
我们用HashMap 对每个小文件的所有IP进行频率统计，这样就可以得到各个文件中频率最大的那个IP. 最后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。
这里之前有个疑惑，有没有情况，IP再不同文件，都是第二大频率..然后和最大，我这种想法纯属是弱智，因为 hash的部分已经将相同日志存入同一个小的file中，所以跟求和无关！每个IP不可能分布在不同文件！
一定注意:
Hash取模是一种等价映射，不会存在同一个元素分散到不同小文件中去的情况，即这里采用的是mod1000算法，那么相同的IP在hash后，只可能落在同一个文件中，不可能被分散的。
4. 其他适用题目
具体分析见Problems 部分
寻找热门查询，300万个查询字符串中统计最热门的10个查询
有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词
海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10
有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序
a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
怎么在海量数据中找出重复次数最多的一个？
上千万或上亿数据（有重复），统计其中出现次数最多的钱N个数据。
一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？
一个文本文件，找出前10个经常出现的词，但这次文件比较长，说是上亿行或十亿行，总之无法一次读入内存，问最优解。
100w个数中找出最大的100个数。
三. Bit-Map
1. 适用范围:
可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下. Bit-Map 能删除，比如Bloom-Filter这点上好. 这类题目一般会找不重复的个数，很大一堆数里面缺少的几个数. 是不是有重复.
2. 方法
基于数据所有的可能性，建立bit 数组, 有多少可能就是多少bit, 同时要考虑bit数组的容量是不是过大. 如果大于memory，需要分割一段一段的再去处理, 这个题目得会算时间，几次可以找到target
3. 实例
已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数
一共8位数字，每位有10种可能, 10^8 = 100 milion bit 约等于 12.5 MB. 我们一共需要12.5 MB没存就可以存下所有电话号码.
遍历文件，每次根据电话号码，计算是第多少个, bit array[index] = 1, 重复号码时候，不变
最后遍历bit array, 统计1的个数.
BitMap到底用不用Hash？如果不用，每次都需要计算电话号码再第几位才能赋值，
如果用了, 方便很多. hash 直接依次存在位上就好， 每位可以直接递增, 根本不用%分布
这块有时间再去深入了解
一般题目都是很简单的int, 所以index 的值就是int的值，非常好对应，根本不用hash，但是电话号码这个就复杂一些. 不好看出index value.
实际变成过程中，没有bit的数据结构，一般都是用byte[] 来表示bit-Map, 这样用一个byte 来标记 8个bit的值，比如 0 和 7 bit上是1， 那么这个byte的值应该是1 + 128 = 129. 这样也可以反向查出来，有点费劲，但是如果涉及程序，只能这么来操作
4.其他使用题目
2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数
Giving an input file with four billion non-negative integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1GB of memory avaiable for this task.
Follow up: What if you have only 10MB memeory? Assume that all the values are distinct.
四. Heap
1. 适用范围
海量数据前k大，并且k比较小，堆可以放入内存
别看到top k 就觉得是heap, 很多题目用分而知之 + Hash + HashMap 统计 + 堆/快速/ 归并排序做的，因为需要统计，heap直接做的适合于比较简单的数据类型.
2. 基本方法
初始化Heap，容量为k, 往里放值，heap自动维护，最后剩下top k.
3. 实例
100w个数中找最大的前100个数
用一个100个元素大小的最小堆即可, 这题没什么好说的
4. 其他适用题目
暂无
五. 双层桶划分
1. 适用范围
第k大，中位数，不重复或重复的数字。重复不重复一般可以用BitMap/ Bloom Filter直接解决，这里知识怕BitMap不够大，可以划分后结合BitMap处理，中位数这种应用场景就非常明显了.
我理解的这类题目，跟一般 分支的还略有不同，确实是只分不治，数据类型上来说，一般是int，或者什么数一类的采用这种方式，向url什么的一般都是分治，从所求结果上来说，都是不需要统计的，比如第K大，中位数等.
2. 一般方法
需要划分 2^8, 2^16个区域，可以用单个文件代表一个区域，具体情况看题目
3. 实例
1).2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
有点像鸽巢原理，整数个数为2^28,也就是，我们可以将这2^28个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。 当然这个题也可以用我们前面讲过的BitMap方法解决，正所谓条条大道通罗马~~~
这个题目我理解的就是，数字太大，直接用bitMap太费劲，寻址太长了，所以分割一下，分割时候需要用Hash保证重复整数落到相同区间，然后分别直接在小的区域中用BitMap. 除掉重复的数字(Bit-Map 可以方便删除)，即可求出. (这个实际挺麻烦，因为重复可能多次，需要标记一下重复元素，最后删除，然后剩下是1的才是不重复的元素)
2).5亿个int找它们的中位数。
这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几 大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。
这题目如果所有int是排好序的就非常好做，直接划分空间，因为每个空间是数目是固定的，所以我们从两边往中间一直走，相遇的时候那个组就是median所在组，这样范围一下缩小非常多，然后正常的找就可以了。
这块我不是很明白，再查资料回来补充
3).现在有一个0-30000的随机数生成器。请根据这个随机数生成器，设计一个抽奖范围是0-350000彩票中奖号码列表，其中要包含20000个中奖号码。
这个题刚好和上面两个思想相反，一个0到3万的随机数生成器要生成一个0到35万的随机数。那么我们完全可以将0-35万的区间分成35/3=12个区间，然后每个区间的长度都小于等于3万，这样我们就可以用题目给的随机数生成器来生成了，然后再加上该区间的基数。那么要每个区间生成多少个随机数呢？计算公式就是：区间长度*随机数密度，在本题目中就是30000*（20000/350000）。最后要注意一点，该题目是有隐含条件的：彩票，这意味着你生成的随机数里面不能有重复，这也是我为什么用双层桶划分思想的另外一个原因。
这里的意思是说，随机数生成器的确有可能有重复数据，但是我们加上了base，就不可能相同.
第一段是 0 - 30000. 第二段是 30000 - 60000，也就是说 30000 + (random(0,30000))
六. External Sort
1. 适用范围
大数据的排序，去重复.
2. 方法
文件分割，每份 < memory, 内排，merge
3. 实例
eBay的一道题目, 给一台内存很小(100MB)，外存无限大的机器，把一个很大的数组（如10GB）排序。
- 读入 100 MB 的数据至内存中，用某种常规方式（如快速排序、堆排序、归并排序等方法）在内存中完成排序。
- 将排序完成的数据写入磁盘。
- 重复步骤 1 和 2 直到所有的数据都存入了不同的 100 MB 的块（临时文件）中。在这个例子中，有 10 GB 数据，单个临时文件大小为 100 MB，所以会产生 100 个临时文件。
- 读入每个临时文件（顺串）的前 10 MB （ = 100 MB / (9 块 + 1)）的数据放入内存中的输入缓冲区，最后的 10 MB 作为输出缓冲区。（实践中，将输入缓冲适当调小，而适当增大输出缓冲区能获得更好的效果。）
- 执行九路归并算法，将结果输出到输出缓冲区。一旦输出缓冲区满，将缓冲区中的数据写出至目标文件，清空缓冲区。一旦9个输入缓冲区中的一个变空，就从这个缓冲区关联的文件，读入下一个10M数据，除非这个文件已读完。这是“外归并排序”能在主存外完成排序的关键步骤 -- 因为“归并算法”(merge algorithm)对每一个大块只是顺序地做一轮访问(进行归并)，每个大块不用完全载入主存。
这里用9路来做，用2路是一样的道理
4. 其他适用题目
1). 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词
2). 有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
七. Map Reduce Framework
1. 适用范围
数据量大，但是数据种类小可以放入内存的
2. 方法
需要写 Map 函数和 Reduce函数，不过海量数据题目说思路就可以了.
3. 实例
The canonical example application of MapReduce is a process to count the appearances of
each different word in a set of documents:
4. 其他适用题目:
1). 海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
2). 一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)？
八. Trie Tree
1. 适用范围
数据量大，重复多，但是种类小可以放入内存
2. 实例
一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词。其解决方法是：用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度），然后是找出出现最频繁的前10个词
搞定后补上.. 这块我缺失...没弄明白
3. 其他适用问题
1).有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序。
2).1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？
3).寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。
九. Database Index and Optimization
1. 适用范围
大数据量的CRUD
2. 基本方法
这部分要看具体的情形，来设计不同的数据库方法，比如index，查询优化
3. 实例
这部分还没有找到题目，我回尽心收集的，所有跟海量数据数据库设计相关的，以及优化，都会放在这.
暂时的例子主要是 什么情况下分库，什么情况下横向分表，纵向分表.
http://www.blogjava.net/jack2007/archive/2009/04/12/265075.html 这也是篇很好的数据库优化的文章，带有一定的案例，可以看看
十. Inverted Index (倒排索引)
1. 适用范围
搜索引擎，关键字查询
2. 基本方法
需要对数据的预处理，首先需要分词，然后对每个文本查找，生成类似HashMap的映射关系，
key 为关键词，value 是文本 or 文档的索引值。
3. 实例
文档检索系统，查询哪些文件包含了某单词，比如常见的学术论文的关键字搜索.
还没有题目，下面就举个小例子好了，在Background Knowledge中也有相应的例子
为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
以英文为例，下面是要被索引的文本：
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"将对应集合的交集。
正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档，很容易看到这个反向的关系。
No comments:
Post a Comment