107 lines (92 loc) · 4.88 KB

海量数据处理

题目特点：
- 需要查询的文件超大，可以认为内存放不下，比如 100GB，1TB 的文件，总之就是大到你内存放不下。
- 文件内容可以是以空格分隔，或者是按行分隔。
- 文件内容可以是整数、浮点数、字符串等，只要是可以排序的就行。

海量数据排序

例题：
- 例题一：按照从小到大给 100GB 的文件进行排序，文件里面是以空格分隔的 float64 类型的浮点数。
- 例题二：按照从大到小给 1TB 的文件排序，文件里面是每行一个字符串。
- 例题三：按照从小到大给 10GB 的文件进行排序，文件里面是每行一个 int32 类型的整数。
解题思路：
- 以例题三举例说明，文件大小是 10GB。
- 假设输入文件名为 input.bin。
- 假设内存有 2GB 可以使用。
- 我们从 input.bin 中每次读取大约 1GB 的数据到内存中进行处理。
  - 我们在内存中对 1GB 的数据使用快速排序进行排序。
  - 把排序好的的 1GB 数据写入文件 xx.bin 中。
  - 一共会得到 10 个排序好的文件 01.bin, 02.bin, ..., 09.bin, 10.bin。
- 对 10 个排序好的文件进行合并。
  - 把 10 个文件都打开，得到 10 个文件句柄。
  - 从 10 个文件句柄中各自读取出一个整数，对比这 10 个整数。
  - 把最小的整数写入 output.bin，同时最小的整数对应的文件句柄向后移动。
- 最后生成的 output.bin 就是排序好的文件。

# 生成测试数据
cd mockdata
cargo build
cd target/debug
./mockdata -o bigdata.txt gennum -c 1000000000

# 排序大文件
cd sortbigfile
cargo build
cd target/debug
./sortbigfile -i bigdata.txt -o sorted.txt

海量数据查询

例题：
- 例题一：1 亿个IP地址，查询某个IP地址是否在这里面？
- 例题二：10 亿个整数，判断某个整数是否在里面？
解题思路：
- 以例题二举例，假设整数类型是 uint32，也就是占用 4 个字节。
- 如果全部保存到内存中，用 set 来保存，那占用的内存大小就是:
  - 10亿个x4字节 = 40亿字节 = 大约 37.25GB
- 这个内存占用有点大了，使用位图来降低下内存的占用。
- 4 byte = 32 bit，最大的数字就是 pow(2, 32) = 4294967296
- 也就是说最多需要 4294967296 这么多 bit 才能表示 uint32 所有的整数
- 4294967296 bit = 512 MB 左右
- 这个内存大小差不多就可以接受了。

海量数据求 TopK

例题：
- 例题一：10 亿个整数，找出最大的 100 个整数？
- 例题一：10 亿个整数，找出最小的 100 个整数？
解题思路：
- 以例题一举例。
- 在内存中建一个小顶堆，也就是最小的整数放在堆顶。
- 从文件中不断读取整数，加入这个小顶堆。
- 当堆的大小超过 100 时，就把堆顶的元素移除，保存小顶堆的元素个数为 100。
- 最后处理完文件后，小顶堆中就是最大的 100 个整数。
注意：
- 如果是找最小的 100 个整数，那就是建立大顶堆。

海量数据求频率

例题
- 例题一：100GB 的搜索关键字文件，统计出现频率 TOP100 关键字。
解题思路
- 先用海量数据排序的方法，对文件进行排序，得到 sorted.bin 文件。
- 然后排序好的 sorted.bin 文件中，相同的关键字就会相邻在一起。
- 这样去遍历一次 sorted.bin 文件，就可以得到每个关键字出现的次数。
- 每处理好一个关键字，就写入到输出文件 output.bin 中。
- 输出文件 output.bin 的格式可以是：
  - 按行分隔。
  - 每行格式：关键字 = 频率
- 最后建立一个小顶堆，遍历一次 output.bin 文件，就可以得到 Top100 的关键字。

海量数据去重

例题
- 例题一：一个文件中包含 10 亿条 URL，有可能会重复，将重复的去掉。
解题思路：
- 先用海量数据排序的方法，对文件进行排序，得到 sorted.bin 文件。
- 然后排序好的 sorted.bin 文件中，相同的 URL 就会相邻在一起。
- 这样去遍历一次 sorted.bin 文件，把不同的写入 output.bin 就可以了。

两个海量文件找重复

例题
- 例题一：给你 a、b 两个文件，各自有 50 亿条 URL，每条 URL 占用 64 字节，内存限制是 4GB，找出 a、b 文件共同的 URL。
解题思路：
- 先用海量数据排序的方法，对文件进行排序，得到 sorted_A.bin, sorted_B.bin 文件。（应该还要去重）
- 然后排序好的 sorted_A.bin, sorted_B.bin 文件中，相同的 URL 就会相邻在一起。
- 然后用双指针的方法。
- 两个文件都打开，得到两个文件句柄。
- 分别读取一个 URL。
  - 如果相等则记录。并同时在读取下一个 URL。
  - 如果不相等，则把对比更小的那个指针后移。