专题-海量数据处理

备忘

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)

腾讯面试题：给定 40 亿个不重复的... - CSDN博客

思路 1

思路 2

思路 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