Big Data Processing
方法：
- 分治/hash映射 + hash统计 + 堆/快速/归并排序
- Bloom filter: 可以用来实现数据字典，进行数据的判重，或者集合求交集，允许有一定错误的情况
- Bitmap
- Trie树： 数据量大，重复多，但是数据种类小可以放入内存
- 数据库索引： 大数据量的增删改查
- 倒排索引： 搜索引擎，关键字查询；用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
- 外排序： 大数据的排序，去重； 归并排序
- 分布式处理之Hadoop/Mapreduce：
- 双层桶划分
TOPK 大数据的排序
1） 海量数据中找出最大的 k 个数 2） 一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前 10 个词 3） 有一个 1G 大小的一个文件，里面每一行是一个词，词的大小不超过 16 字节，内存限制大小是 1M。返回频数最高的 100 个词。
思路：都是要先统计出每个元素的出现次数，再用 TOPK 去求最大的 k 个数。
- 对于有内存要求的，需要将大文件划分为小文件： 顺序遍历这个 1G 的大文件中的每个词，计算 hash(x)%2000，按照得到的值分别存储到 2000 个小文件中（x0,x1,…x1999），这样得到的每个文件大小大概是 500k，如果发现有文件大于 1M，就再按照这个方法进行划分，直到所有小文件都小于 1M
- 对每个小文件，用 dict 统计每个词出现的频率（文件大小小于内存，可以直接计算，也可以用 tire 树）
- 对每个小文件，用堆排序方法选出频率最大的 100 个词（TOPK 用最小堆），并存入一个文件中，这样就得到了 2000 个文件
- 合并小文件，两两合并选出 200 个词中的前 100 个词（类似归并）
找出现次数最多的数
海量日志数据，提取出某日访问百度次数最多的那个IP（其实和 TOPK 一样）
思路： IP 是 32 位，总共有 2^32 个不同的 IP，每个 IP 大小为 4 个字节，2^32 * 4 = 16G，很难全部加载到内存中，因此考虑分治。（1G = 2^10M = 2^20KB = 2^30B）
- 顺序遍历每个 IP，计算 hash(ip)%1000，分到 1000 个小文件（具体分多少个文件，还是要可用内存大小）
- 然后构建一个 key-value 的哈希表（python 直接用 Counter 计数），找到最大的数，这样得到 1000 个出现最多的 IP
- 从 1000 个 IP 中找到出现次数最多的
两个文件 a 和 b，各存放 50 亿条 URL，每条 URL 占用 64 字节，内存限制是 4G，找出 a,b 文件共同的 URL
估计每个文件大小为 50亿 * 64k 约等于 320G，远大于内存 4G，因此不可能将其完全加载到内存中处理，考虑分治。
- 遍历文件 a，对每个 url 求 hash(url)%1000，根据得到的值把 url 分别存储到 1000 个小文件中(a0,a1,…a999)
- 遍历文件 b，同样把 b 中的 url 分别存储到 1000 个小文件中(b0,b1,…,b999)
- 求每对小文件 ai 和 bi 中相同的 url，可以用 set 存储 ai 的 url，然后遍历 bi 中的每个元素，找到相同的就记录下来。
1-2 步处理后： 所有可能相同的 url 就会被分到对应的小文件中，也就只要去找 a0 和 b0 中相同的 url，ai 和 bi 中相同的 url。 因此相同的 url 的 hash 值是相同的，hash 是随机的，因此理论上可以看到平均分配。
一个大文件，包含一些列搜索关键词，给定一个关键词，如何判断是否在这个大文件中
有一个大文件，里面含有一些列搜索关键词，如何判断一个给定的关词是否包含在内（使用哈希表），使用什么哈希函数，是否存在冲突，如何解决冲突. 在上述的基础上，数据中还包含ip，时间段，如何根据ip查找相应关键词以及时间段，如何根据关键词查找某个时间段内的所有ip
使用 hash 来判断
在允许一定错误的情况下，可以用布隆过滤器，遍历文件的每个词，使用 k 个哈希函数将元素映射到位数组中，用 k 个映射位是否全为 1 来表示元素是否在集合中。
一个很大的文本，比如 log 数据，以行存储，如何快速计算一个字段的平均值
按行切分文件： linux 中的 split 命令
1 | wc -l big.txt # 先计算出文件的行数 |