首页 > 试题广场 >

58 到家有 10 个大小为 1G 的用户访问日志文件,每个

[问答题]

58 到家有 10 个大小为 1G 的用户访问日志文件,每个文件的每一行存放用户的所在访问城市,当然同一个用户可能在不同城市访问,同一个城市也存在多个用户访问,一个日志文件的典型内容为:“用户 A ,北京市 用户 B 上海市 用户 C 上海市 用户 A 上海市 用户 D 三沙市”现给定一台内存为 512M PC , 希望统计出访问频度最高的 100 个城市。请描述你的解决方案并给出主要的处理流程,列出其中用到的算法及算法的时间复杂度。 

下面这个思路是我自己的思路,也不太确定是否正确,但我个人感觉算是比较优化的。
        首先通过文件流分别按顺序读取10个大小为1G的文件,因为操作系统底层是有内存分页的机制,所以内存比较小的PC机也是可以分批读取大文件的。然后使用一个hash表,key为城市名,value为城市访问数,value的数据类型最好用long,因为数据量比较大。由于中国目前的城市数最多也不会超过1万,所以512M的内存是绝对够用的,然后在遍历文件内容的过程中,每遍历一行,就把对应的城市访问数+1,这里需要O(n)的时间复杂度。
        遍历完所有数据之后,我们可以对hash表根据value进行降序排序,再取前100的城市,这个步骤的时间复杂度为访问的城市数量的平方,考虑到城市数量是一定的,这个步骤并不会耗费很多时间。
        ps:其实我是想过在排序的时候利用快速排序的划分操作进行优化的,每次划分只取其中一边进行递归,这样可以把O(nlogn)的时间复杂度变成O(n),假如题目问的是统计访问频度第100高的城市,是可行的,但是由于这里题目问的是前100,所以并不可行。
编辑于 2017-03-04 15:30:52 回复(0)