大文件处理问题

最好的分类的讲解：

如何找出某一天访问百度网站最多的 IP？ (doocs.github.io)

海量数据大多数，分成小文件处理，分治

https://blog.csdn.net/wanger61/article/details/110004130

https://blog.csdn.net/v_JULY_v/article/details/7382693?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-1-7382693-blog-110004130.pc_relevant_3mothn_strategy_recovery&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-1-7382693-blog-110004130.pc_relevant_3mothn_strategy_recovery

1. 分治法 DivConquer

2. 位图法 BitMap

   拓展：布隆过滤器

   布隆过滤器由「初始值都为 0 的位图数组」和「 N 个哈希函数」

   • 如果布隆过滤器判断一个元素不在一个集合中，那这个元素一定不会再集合中。
   • 如果布隆过滤器判断一个元素在一个集合中，不一定在。

大文件排序

外排序

大文件找众数

摩尔投票法

两个大文件求交集

假设文件为a，b

1. 直接遍历法。一般人第一时间都是想遍历吧。读取每一行a，在b中遍历，这样时间复杂度为O（n^2），显然一般人都不能接受这个时间复杂度。

2. 哈希 + 分片的思想。先把a文件hash，在遍历b文件，去判断是否存在。

   时间复杂度降低为O（n） ，但是空间复杂度上来了，以空间换时间。

   1. 将文件A中的hash(url)%100，生成100个小文件。
   2. 文件B中也hash(url)%100，生成100个小文件。
   3. 然后将A子文件001和B子文件001求交集，放入一个结果文件即可。

3. 布隆过滤器。但是布隆过滤器是有可能出现错误的，当时应该问问他是否可以出现小的错误？

对于大文件的话，一般都是使用分治思想，将文件分割成多个小文件来处理。

题目背景
给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url

主体思路
分治+hash

实现步骤
遍历文件A，对每个url使用hash(url) % 1000，根据所得的取值将url存储到1000个小文件中（a1,a2,…,a1000）（根据内存大小设定hash函数）
遍历文件B，使用同样的hash函数将B中的url存储到1000个小文件中（b1,b2,…,b1000）（这样相同的url就会被映射到下标相同的小文件中）
读取文件a1，简历hash表，再读取文件b1，遍历其中的url，若url在hash表中出现，说明为两文件共有，存入结果中。

如何在大量的数据中判断一个数是否存在？

题目描述

给定 40 亿个不重复的没排过序的 unsigned int 型整数，然后再给定一个数，如何快速判断这个数是否在这 40 亿个整数当中？

解答思路

方法一：分治法

依然可以用分治法解决，方法与前面类似，就不再次赘述了。

方法二：位图法

由于 unsigned int 数字的范围是 [0, 1 << 32)，我们用 1<<32=4,294,967,296 个 bit 来表示每个数字。初始位均为 0，那么总共需要内存：4,294,967,296b≈512M。

我们读取这 40 亿个整数，将对应的 bit 设置为 1。接着读取要查询的数，查看相应位是否为 1，如果为 1 表示存在，如果为 0 表示不存在。

方法总结

判断数字是否存在、判断数字是否重复的问题，位图法是一种非常高效的方法。