从海量数据中查找top K大或者小的数
构建堆
找最大的数前K个构建最小堆，找K个最小的数构建最大堆
如果这些数据是分布在不同的机器上的。
先计算每个机器上的top K ,
再使用合并计算整体的top K
如果当前文件是个大文件：
方案1:先构建堆，再遍历进行堆的调整
方案2:分治法：
map[分为多个小文件,计算每个topk]
reduce[合并汇总]
Hash法。
如果这1亿个书里面有很多重复的数，先通过Hash法，把这1亿个数字去重复，这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间，
然后通过分治法或最小堆法查找最大的10000个数
海量数据查找中位数
如果这些数据是分布在不同的机器上的。
先堆每个机器进行排序,
再使用归并排序
如果当前文件是个大文件：
方案1:先分桶，根据
【前八位】【判断处于255个的哪个桶】
【次8位】【判断处于255个的哪个桶】
直到最后八位，依次排序即可
海量统计出现最多的top k 词
如果是大文件：
先根据hash并求模，将文件分解为多个小文件，对于单个文件利用下述的方法求出每个文件件中 K 个最常出现的词。然后再进行归并处理，找出最终的 K 个最常出现的词。
统计出现次数最多的词串
方案 1：采用 trie 树，关键字域存该查询串出现的次数，没有出现为 0。最后用 K 个元素的最小推来对出现频率进行排序。
统计出现次数最多的数字
读入部分文件，对数值模10.取值相同放入一个文件。然后处理10个文件
依次统计出现次数最多的。再进行比较输出
假设一种极端情况。文件内容全部取模值全部相同。或者超过2G就不在适用上面的方法了。而更适合将相同的数字放入同一个文件。
海量数据按照频度排序
方案 1：
hash分成小文件。hash(query)%10
依次统计每个 query 出现的次数。
利用快速/堆/归并排序按照出现次数进行排序。将排序好的 query 和对应的 query_cout 输出到文件中。这样得到了 10 个排好序的文件
对b0,b1,…,b9 这 10 个文件进行归并排序（内排序与外排序相结合）。
方案 2：
采用 trie 树/hash_map 等直接来统计每个 query出现的次数，然后按出现次数做快速/堆/归并排序就可以了
方案 3：
与方案 1 类似，但在做完 hash，分成多个文件后，可以交给多个文件来处理，采用分159布式的架构来处理（比如 MapReduce），最后再进行合并
海量数据找不重复的数
方案 1：采用 2-Bitmap（每个数2bit,0表示不存在,1 表示出现一次, 2 表示多次,3无意义)，共需内存 2^32*2bit=1GB 内存，还可以接受。
然后扫描这 2.5 亿个整数，查看 Bitmap 中相对应位，如果是 00 变 01， 01 变 10， 10 保持不变。事后，查看 bitmap，把对应位是 01 的整数输出即可。
方案 2：进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。
两个大文件，找出文件共同的数据
文件A，B分别分成小文件
依次计算每个小文件的共同数
如果允许有一定的错误率，可以使用 Bloom filter
原理：当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。它实际上是一个很长的二进制向量和一系列随机映射函数。优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
将多个集合合并成没有交集的集合
给定一个字符串的集合，格式如： {aaa,bbb,ccc},{bbb,ddd},{eee, fff },{ggg},{ddd,hhh}。要求将其中交集不为空的集合合并，要求合并完成的集合之间无交集，例如上例应输出{aaa,bbb,ccc,ddd,hhh},{eee, fff },{ggg}。
方案 1：
采用并查集。首先所有的字符串都在单独的并查集中。然后依扫描每个集合，顺序合并将两个相邻元素合并。例如，对于{aaa,bbb,ccc}，首先查看 aaa 和 bbb 是否在同一个并查集中，如果不在，那么把它们所在的并查集合并，然后再看 bbb 和 ccc 是否在同一个并查集中，如果不在，那么也把它们所在的并查集合并。接下来再扫描其他的集合，当所有的集合都扫描完了，并查集代表的集合便是所求。复杂度应该是 O(NlgN)的。改进的话，首先可以记录每个节点的根结点，改进查询。合并的时候，可以把大的和小的进行合，这样也减少复杂度。
|