海量数据处理
时间（无法迅速解决）：Bloom filter/Hash/bit-map/堆/trie树。
空间（无法一次性载入内存）：大而化小，分而治之
bloom filter
定义：利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。
优势：Bloom Filter比其他常见的算法（如hash，折半查找）极大节省了空间。
判断：判断元素不在集合中，那肯定不在。如果判断元素存在集合中，有一定的概率判断错误。
应用：实现数据字典，进行数据的判重，或者集合求交集
Hash
一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
bitmap
用一个bit位来标记某个元素对应的值。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省
堆
完全二叉树，可用数组存储。
trie树：前缀树
应用：前缀统计，词频统计
外排序
步骤
首先按内存大小，将外存上含n个记录的文件分成若干长度L的子文件或段。依次读入内存并利用有效的内部排序对他们进行排序，并将排序后得到的有序字文件重新写入外存，通常称这些子文件为归并段。
对这些归并段进行逐趟归并，使归并段逐渐由小到大，直至得到整个有序文件为之。
优化：置换选择 败者树原理，最优归并树
Top K问题
解法：维护一个大小为 K 的小顶堆，依次将数据放入堆中，当堆的大小满了的时候，只需要将堆顶元素与下一个数比较：如果大于堆顶元素，则将当前的堆顶元素抛弃，并将该元素插入堆中。遍历完全部数据，Top K 的元素也自然都在堆里面了。
前K个最大的数，用小顶堆
前K个最小的数，用大顶堆
大数据（Hadoop）
分布式存储（HDFS，基于GFS）
分布式计算（MapReduce）
Map：转换数据为KV形式
Sort
Combine
Shuffle：数据移动（数量巨大的网络传输IO）
Reduce：聚合运算
一个MapReduce任务只有一次Map和Reduce，运算结果会写回到磁盘（分布式存储）供下次计算使用。如果所做的运算涉及大量循环（机器学习训练模型），那么整个计算过程会不断重复地往磁盘里读写中间结果。
整个算法的瓶颈是不必要的数据读写，而Spark 主要改进的就是这一点。具体地，Spark 延续了MapReduce 的设计思路：对数据的计算也分为Map 和Reduce 两类。但不同的是，一个Spark 任务并不止包含一个Map和一个Reduce，而是由一系列的Map、Reduce构成。这样，计算的中间结果可以高效地转给下一个计算步骤，提高算法性能。虽然Spark的改进看似很小，但实验结果显示，它的算法性能相比MapReduce 提高了10～100 倍。
Last updated