[TOC]
- 问题： 在一个无限的整数数据流，如何从中等概率随机抽取 k 个整数出来？ -- 采样问题
抽样方法：
- 当第一个整数到达时，保存该整数
- 当第二个整数到达时，以
$\frac{1}{2}$ 的概率使用该整数替换第一个整数，以$\frac{1}{2}$ 的概率丢弃该整数 - 当第 i 个整数到达时，以
$\frac{1}{i}$ 的概率使用第 i 个整数替换被选中的整数， 以$1 - \frac{1}{i}$ 的概率丢弃 第i个整数
归纳法 - 验证分析
- n = 1 时， 被选中的概率为 100%， 成立
- 设
$n = m , m \ge 1$ 时，命题成立，即前 m 个数，每一个被选中的概率为$\frac{1}{m}$ - 当 $ n = m + 1 $ 时， 第
m + 1个数被选中的概率为$\frac{1}{m+1}$ ， 前 m 个数被选中的概率为$\frac{1}{m} * (1-\frac{1}{m+1}) = \frac{1}{m+1}$ , 成立。
抽样方法
- 前 k 个整数到达时，全部保留
- 第 i 个整数到达时， 以
$\frac{k}{i}$ 的概率替换 k 个数中的某一个，以 $1-\frac{k}{i} $ 丢弃
归纳法 - 验证分析
-
$n \le k$ 时， 被选中的概率为100%， 成立 -
假设
$n = m, m > k$ 时， 你命题成立， 即前m 个数， 每一个被选中的概率为$\frac{1}{m}$ -
当 $ n = m + 1 $ 时， 第 m+1 个数被选中的概率为
$\frac{k}{m+1}$ ， 前 m 个数被选中的概率为： $$ \frac{1}{m} * [ \frac{k}{m+1} * (1 - \frac{1}{k}) + 1 - \frac{k}{m+1}] = \frac{1}{m+1} $$
- 题目： 计算一个数据流中不同元素的个数？
采用 hashet，不断加入， 最终的hashset大小就是所求答案。 缺点： 单机内存存不下
- 前提： 假设已经知道不同元素的个数的上限，假设为 N
我们可以建立一个长度为N的 bit 数组， 每个元素与 bit 数组的某一位一一对应， 该位为1，则表示此元素在集合中，为 0 表示不再集合中，最终的答案为 bitmap 中1的个数。
- 缺点： bitmap 与实际情况下不同元素的个数无关，而与不同元素的个数上限有关。
基本思路：
- 选择一个哈希函数 h， 其结果服从均匀分布
- 开一个长度为 m 的bitmap，初始化为 0
- 数据流每来一个元素，计算哈希值并对m取模，然后将该位置置1
- 最后，若 bitmap 中还有 u 个bit 为 0， 则不同元素的总数近似为
$-m log\frac{u}{m}$
m的选择
对于 bitmap 长度的选择，主要由两个因素决定：基数大小以及容许的误差。 假设基数大小大约为n， 允许误差大约为
基本思路：
- 均匀随机化。 选择哈希函数 h 的几大条件：
- h 应该尽可能减少冲突
- h 的结果是几乎服从均匀分布的。
- 哈希后的结果是固定长度的。
- 对于每个元素，计算出哈希值，每个哈希值是等长的，长度为 L
- 题目： 计算数据流中任意元素的出现的次数
- 用 HashMap 来记录每个元素出现的次数。
- 缺点： 占用内存大，单机内存无法存下这个巨大的 HashMap
假设有 n 台机器， 那么每台机器都有一个HashMap， 第 i 台处理 hash(elem) % n == i-1 的元素。
查询时， 先计算元素在哪台机器上，然后去那台机器上的HashMap读取。
- 选定 d 个哈希函数， 并建立一个
d * m的二维整数数组作为哈希表 - 对于每个元素，分别使用 d 个hash 函数计算相应哈希值，并对 m 取余，然后在对应的位置上增1，二维数组中的每个整数称为 sketch。
- 对于要查询的元素，取出 d 个sketch， 返回最小的哪一个。（d 个sketch 都是该元素的近似频率，返回任意一个均可）
优点： 省内存；
缺点：对于出现次数较少的元素，准确性很差。主要是由于 hash 冲突比较严重
对 Count-Min Sketch 做了改进。
- 来了一个查询，按照 Count-Min Sketch 的正常流程，取出它的d个sketch
- 对于每个hash函数，估算一个噪音 = 该行所有整数（除了被查询的这个元素）的平均值
- 真正的sketch = 该行的sketch - 该行的噪音
- 返回 d 个sketch 的中位数
- 题目： 寻找数据流中出现最频繁的 k 个元素？
用一个 HashMap存放所有元素出现的次数，用一个小根堆，容量为k，存放目前出现过的最频繁的 k 个元素：
- 元素过来时，更新 HashMap， 并且在堆中查找该元素，如果找到，则+1并调整堆； 如果没有找到，则将该元素次数与堆顶元素比较，如果大于，则把堆顶元素替换为该元素，并调整堆。
- 时间复杂度为
$O(n (k + logk))$ ， 空间复杂度为$O(n)$
- 将数据分片， 第 i 台机器只处理
$hash(elem) % n == i-1$ 的元素 - 每台机器都有一个 HashMap 和 Heap， 格子计算出 top k 元素
- 将每台机器的 Heap， 通过网络汇总到一台机器上，并将多个Heap合成一个 Heap
- 题目：给定一个无限的整数数据流，如何查询在某个范围内的元素出现的总次数？
- 题目：给定一个无限的数据流和一个有限集合，如何判断数据流中的元素是否在这个集合中？
布隆过滤器本质上是二进制向量 + 一系列随机映射函数， 主要用于检测某元素是否在一个集合中。
- 优点： 空间效率和查询时间都远远超过一般的算法
布隆过滤器原理
- 加入元素：当一个元素被加入到集合时，通过 K 个哈希函数将这个元素映射成一个位数组中的K个点，把它们置为1。
- 检索元素：查看对应的 K 个点是否都为1 ： 如果存在任意一个为 0， 被检元素一定不在； 如果都为1，则很可能存在。
布隆过滤器与Bitmap 区别
布隆过滤器使用了 k 个哈希函数，每个元素对应 k 个bit，从而降低了冲突的概率
布隆过滤器缺点
- 存在误判：即可能要查找的元素不在容器内，但 k 个位置上都是 1
- 删除困难：一旦删除元素，不能简单将对应 k 个位置置为 0
布隆过滤器实现
假设要存的数据量为n， 期望的误判率为 fpp，我们需要计算 Bit 数组的大小 m， hash 函数的个数 k，并选择合适的哈希函数。
-
Bit 数组大小选择： $$ m = -\frac{nlnfpp}{(ln2)^2} $$
-
哈希函数选择： $$ k = \frac{m}{n}ln2 $$