> For the complete documentation index, see [llms.txt](https://shuixn.gitbook.io/notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shuixn.gitbook.io/notebook/da-shu-ju/hai-liang-shu-ju-chu-li.md).

# 海量数据处理

1. 时间（无法迅速解决）：Bloom filter/Hash/bit-map/堆/trie树。
2. 空间（无法一次性载入内存）：大而化小，分而治之

## bloom filter

* 定义：利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。
* 优势：Bloom Filter比其他常见的算法（如hash，折半查找）极大节省了空间。
* 判断：判断元素不在集合中，那肯定不在。如果判断元素存在集合中，有一定的概率判断错误。
* 应用：实现数据字典，进行数据的判重，或者集合求交集

## Hash

一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

## bitmap

用一个bit位来标记某个元素对应的值。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省

## 堆

完全二叉树，可用数组存储。

## trie树：前缀树

应用：前缀统计，词频统计

## 外排序

1. 步骤
   1. 首先按内存大小，将外存上含n个记录的文件分成若干长度L的子文件或段。依次读入内存并利用有效的内部排序对他们进行排序，并将排序后得到的有序字文件重新写入外存，通常称这些子文件为归并段。
   2. 对这些归并段进行逐趟归并，使归并段逐渐由小到大，直至得到整个有序文件为之。
2. 优化：置换选择 败者树原理，最优归并树

## Top K问题

解法：维护一个大小为 K 的小顶堆，依次将数据放入堆中，当堆的大小满了的时候，只需要将堆顶元素与下一个数比较：如果大于堆顶元素，则将当前的堆顶元素抛弃，并将该元素插入堆中。遍历完全部数据，Top K 的元素也自然都在堆里面了。

1. 前K个最大的数，用小顶堆
2. 前K个最小的数，用大顶堆

## 大数据（Hadoop）

1. 分布式存储（HDFS，基于GFS）
2. 分布式计算（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 倍。