海量数据处理
备忘
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 亿个不重复的... - CSDN博客
思路 1
BitMap
思路 2
Hash 分桶 + 排序 + 二分查找
思路 3
外部排序 + 结构存储 + 二分查找
int 型整数的范围是
2^32 ≈ 42亿
,那么对于 40 亿个整数,必然存在大量连续的范围排序后,必然存在大量以下情况:
对于这种形式的序列,可以构造如下结构
则上述示例,可以存储为
复杂度分析
这样最差情况存在
2(=42-40)
亿个断点,即2
亿个结构体,每个结构体占8
个字节,共400(MB) * 4 = 1.6(GB)
每次查找的时间复杂度为
O(logN)
思路 4
多机分布式
Reference
海量数据处理面试题集锦 - CSDN博客
十道海量数据处理面试题与十个方法大总结 - CSDN博客
最后更新于