专题-D-海量数据处理.md

专题-海量数据处理
===
备忘
---
- `1 GB`: 十亿个字节（Byte）
> `1(B) * 10*10^8 / 1024 / 1024 ≈ 953.67(MB) ≈ 1000(MB) ≈ 1(GB)`
- `400 MB`: 一亿个 4 字节（Byte） int 整型占用的内存
> `4(B) * 10^8 / 1024 / 1024 ≈ 381.57(MB) ≈ 382(MB) ≈ 400(MB)`
- 10 亿个整型 -> `400(MB) * 10 = 4(GB)`
- 40 亿个整型 -> `4(GB) * 4 = 16(GB)`
- `12 MB`: 一亿个比特（bit）占用的内存（相比于 int 型，节省了 32 倍内存）
> `1(b) * 10^8 / 8 / 1024 / 1024 ≈ 11.92(MB) ≈ 12(MB)`
- 10 亿个比特 -> `12(MB) * 10 = 120(MB) ≈ 4(GB)/32 = 128(MB)`
- 40 亿个整型 -> `120(MB) * 4 = 480(MB) ≈ 16(GB)/32 = 500(MB)`
Index
---

- [判断一个整数是否在给定的 40 亿个（不重复）整数中出现过](#判断一个整数是否在给定的-40-亿个不重复整数中出现过)
- [Reference](#reference)

## 判断一个整数是否在给定的 40 亿个（不重复）整数中出现过
> [腾讯面试题：给定 40 亿个不重复的...](https://blog.csdn.net/wenqiang1208/article/details/69669084) - CSDN博客
**思路 1**
- BitMap
**思路 2**
- Hash 分桶 + 排序 + 二分查找
**思路 3**
- 外部排序 + 结构存储 + 二分查找
- int 型整数的范围是 `2^32 ≈ 42亿`，那么对于 40 亿个整数，必然存在大量连续的范围
- 排序后，必然存在大量以下情况：
```
1 2 3 4 7 8 9 ...
```
- 对于这种形式的序列，可以构造如下结构
```
struct {
start; // 记录连续序列的开头
n_continue; // 连续字段的长度
}
```
- 则上述示例，可以存储为
```
(1, 4), (7, 3), ...
```
- 复杂度分析
- 这样最差情况存在 `2(=42-40)` 亿个断点，即 `2` 亿个结构体，每个结构体占 `8` 个字节，共 `400(MB) * 4 = 1.6(GB)`
- 每次查找的时间复杂度为 `O(logN)`
**思路 4**
- 多机分布式
## Reference
- [海量数据处理面试题集锦](https://blog.csdn.net/v_july_v/article/details/6685962) - CSDN博客
- [十道海量数据处理面试题与十个方法大总结](https://blog.csdn.net/v_JULY_v/article/details/6279498) - CSDN博客