- 如何从10G文件中统计出出现次数最多的QQ号，内存只有1G,外存无限。
可以逐行文件中的QQ号，然后hash到20个新的文件中，然后再对这20个文件进行Map统计，得到最大的值。
- 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）
- 在2.5亿个整数中找出不重复的整数
采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。
- 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
（1）bool数组：申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
（2）字典树：利用bool的0和1组成一个二叉树，先插入该数字，然后插入其他40亿数字，如果有重复的数则会发现之前该节点已被创建。一般20个亿应该就可以了，因为不需要一开始就预配那么多内存所以可以逐渐增加，理论上内存占用比数组少，但是速度不能保证....
- 其实逐行读取文件然后匹配理论上也可以啊....
- 怎么在海量数据中找出重复次数最多的一个？
先做hash，然后hash值模1000映射到0-999的文件夹，生成以该数值命名的文件，文件内容写入1，若已生成该文件，则++。最后统一读一遍文件内容。
- 如何统计出40亿个数里面出现两次的数？
unsigned int 大小的bit数组，每个元素包含两个bit位，统计0-3，大于3按3算，最后遍历一遍即可。
网友评论