海量数据处理

备忘

• 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 亿个（不重复）整数中出现过

• Reference

判断一个整数是否在给定的 40 亿个（不重复）整数中出现过

腾讯面试题：给定 40 亿个不重复的... - 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

• 海量数据处理面试题集锦 - CSDN博客
• 十道海量数据处理面试题与十个方法大总结 - CSDN博客