Top100URL

100 GB 的 URL 文件，使用最多 1 GB 内存计算出现次数 Top 100 的 URL 和各自的出现次数。

环境

Python 3.8

实现思路

• 对已经生成的URL文件，考虑到其内存限制，将所有URL按照哈希值除以1000的余数分别写入到对应的文件中，每个哈希值对应的是一个文件
• 对每个哈希文件，用Python的字典记录其中URL的出现次数，将统计结果写入totalResult.txt文件中
• 在totalResult.txt文件中建立小根堆，存放读取到的最多出现次数的100个URL及对应出现次数
• 将小根堆的结果输出到Result.txt文件，即为结果

性能优化

• 最后查看最多出现的URL时用小根堆维护，只需要存储Top100的URL及次数
• 对URL进行哈希分片的时候，将1000个输出流提前打开，这样不用对每条URL哈希时都打开关闭文件一次

文件功能

• src/calcutator.py：统计每个哈希文件的全部URL出现次数并写入tmp/totalResult.txt文件中
• src/split.py：将data/data100mb.txt文件中的所有URL计算哈希并写入对应的哈希文件中
• src/heap.py：对tmp/totalResult.txt文件的URL及次数建立小根堆，记录Top100出现次数的URL及次数

补充思考

• 按照哈希分片的方式，基本能够满足题目要求。但是当出现了较多的重复URL的时候，可能会存在某个哈希文件过大的情况而超出内存要求。为了防止这种情况的影响，可以考虑对文件的大小进行检测，大于1G的情况下对文件内部分片，然后把分片的文件的统计结果整合
• 为了计算速度，可以使用分布式集群的系统，每个结点统计某些哈希文件的内容，然后汇总
• 由于本地磁盘空间有限，没有测试100G的数据，而是用100M数据进行测试。理论上符合需要，实际是否能够成功仍需测试。