Big Data 海量数据题
何为big data
数据量太大
- 要么是无法再较短时间内解决（时间）
可以采取巧妙地算法搭配合适的数据结构，比如
- bloom filter
- hash
- bitmap
- heap
- 数据库或倒排索引（inverted index)
trie
要么是数据太大，无法一次性读到memory中（空间）
对空间来说，无非就一个办法，大而化小，分而治之（hash映射）
单机，集群问题
单机就是处理转载数据的机器有限（只要考虑CPU,memory,disk data交互)
- 集群就是机器多，适合分布是处理，并行计算（节点交互）
处理海量数据问题，无非就是：
- 分而治之/hash映射(mapping) + hash统计 + 堆/快速/归并排序；
- 双层桶划分
- Bloom filter/Bitmap；
- Trie树/数据库/倒排索引；
- 外排序；
- 分布式处理之Hadoop/Mapreduce。
从set/map到hashtable/hash_map/hash_set， 基础
c++的概念？
因为set/map/multiset/multimap都是基于RB-tree之上，所以有自动排序功能，而hashset/hash_map/hash_multiset/hash_multimap都是基于hashtable之上，所以不含有自动排序功能，至于加个前缀multi无非就是允许键值重复而已。
big data问题处理 6种方法
1. divide & conquer/hash映射+hash_map统计+heap/quicksort/mergesort
题目1
海量日志数据，提取出某日访问百度次数最多的那个IP。
Solution
- divide & conquer/hash映射
针对数据太大无法读到内存中，将大文件分为（module映射）小文件，比如IP可能
有2^32个，那么采取%1000的方法分为1000个小文件。
- hash_map统计
找出小文件中的最大频率IP
- heap/quicksort/mergesort
在这1000个IP中找出频率最高的IP
hash映射，便于计算机在有限内存处理big data,将data通过hash function均匀分布在 对应的内存位置
题目2
寻找热门query, 300万个query中找top 10的, 1千万个记录（有重复）， 内存不超过 1G
Solution
对于top k的问题，采取的对策往往是 hashmap + heap
- hash_map统计
先对这批数据进行次数的统计, 当然，你也可以采用trie树，关键字域存该查询串出现的次数， 没有出现为0。最后用10个元素的最小推来对出现频率进行排序。
- heapsort
找出top k, 时间复杂度为Nlogk, 维护一个k大小的min heap
题目3
1G大小的一个文件，每一行是一个词，词的大小不超过16B，内存限制是1M，返回 频率最高的100个词。
同样的套路
题目4
海量数据存在100台电脑中，想办法高效统计出这批数据的top 10。
- 每个数据元素只出现在某一台机器中
还是采用分别在每台电脑上heapsort求出top 10,然后再合并100个的数据，再heapsort
- 同一个元素可能出现在不同的电脑中
方法1： 遍历一遍所有数据，hash取模分配，使同一个元素只出现在一台电脑上
方法2： 暴力brute force, 直接统计每台电脑中各个元素的出现次数，然后把同一个 元素的出现次数相加，最终从所有数据中找出top 10。
题目5
10个文件，每个1G，每一行是用户的query,每个文件的query都可能重复，要求按照 query的频率排序。
方案1
- hash mapping: 顺序读取10个文件，按照hash % 10的结果将query写入到另10个文件中
- hash_map统计: 找一台内存2G左右的机器，用hashtable(query, query_count)统计 query出现的次数，然后根据这个次数排序
- heapsort/mergesort: 这样我们得到10个排好序的文件，然后对他们进行merge sort
方案2
有可能query只是重复次数多，可以一次性就加入到内存中，这样就可以采用trie树/hashtable 的方法统计次数了，然后按照次数排序就可以。
方案3
与1相似，但是多个文件可以分到多个机器上map/reduce计算。
题目6
给点a,b两个文件，歌存放50亿个url,每个url占64B，内存是4G，让你 找出a,b共同的url.
- 分成小文件
对a和b都做遍历，对每个url做hash, module 1000,存到1000个小文件中。 a1,a2...a1000和b1,b2,.....b1000。因为现在所有可能相同的url都应该在 对应的小文件里，所以就变成求对应的小文件里的相同的url.
- hashtable统计， 然后再Merge就可以了
题目7，8，9，10， 11， 12
海量数据求重复次数最多的，求top k的，都是这种思想
- rbtree比hashtable慢一些，因为还要看value的数据
- 但速度一般可以忍，而且B+ tree还对磁盘友好
2. 多层划分
本质还是divide and conquer，重点是“分”的技巧
适用范围： top k, median number, 不重复或重复的数字
基本原理：因为元素范围太大，不能直接寻址，所以通过多次划分，逐步 确定范围，然后在可接受的范围内求解。
题目13
2.5亿个整数中找出不重复的整数的个数，内存不足以容纳2.5亿个整数
Solution
有点像Pigeonhole principle， 整数有2^32个（4 bytes integer), 可以将 他们分为2^8个区域(用单个文件代表一个区域)，然后将数据分离到不同 的区域，然后不同的区域利用bitmap解决。
题目14
5亿个int找中位数。
方案1
将int划分为2^16个区域，然后读取数据落在各个区域里的个数，根据统计 结果就可以知道Median落在哪个区域，并且知道这个区域第几个数是median。
再扫描一次只统计这个区域里的数就可以了。
即使是int64,也可以通过多次划分(2^64 -> 2^40 -> 2^20)就可以了。
3. bloomfilter/bitmap
题目15
给你A,B两个文件，各存放50亿条URL，每条URL 64B，memory 4G, 找出A,B文件共同的URL。如果三个乃至N个文件呢？
solution
我们可以大概算一下Memory的占用：
4G = 2^32 * 8 ~= 340亿 bits, n=50亿，如果按error rate 0.01来算
的话，大概需要50 * 13 ~= 650亿的bit array. 现在大概有一半的size,
所以error rate要上升一些。
将a文件中的url映射为这340亿个Bits，然后再读b文件，来判断 是否有重合。
题目13
2.5亿个整数中找出不重复的整数。
solution
将Bitmap扩展一下，2个bit对应1个整数
- 0, 未出现
- 1, 出现1次
- 2, 出现多次
- 3, 无意义
4. trie tree/database/inverted index
Trie
适用: 数据量大，但重复多，种类少，可以放进Memory
database index
适用: 大数据量的search, insert, delete, update
inverted index
适用: search engine, keyword查询
例子：
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"将对应集合的交集。
正向索引中，文档占据了中心的位置，每个文档指向了一个它所 包含的索引项的序列。
反向索引中，单词指向包含它的文档
5 外排序(external sorting)
适用：大数据的排序，去重
A term for a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the memory and instead they must reside in slower extrenal memory(hard drive).
Usually use sort-merge strategy. chunks of data small enough to fit into memory are read, sorted and written out to a temp file. The merge these files into a single larger file.
6 map/reduce
可以通过大量机器进行parallel computing,然后再reduce合并
知识点
- hashtable
- heapsort
- bitmap
- bloomfilter
- trie
- database
- inverted index
- external sorting