现在的位置: 首页 > 综合 > 正文

84 有 10个文件,每个文件1G 按照 query 的频度排序

2018年01月19日 ⁄ 综合 ⁄ 共 608字 ⁄ 字号 评论关闭

3.有 10  个文件,每个文件 1G,
每个文件的每一行都存放的是用户的 query,每个文件的 query 都可能重复。
要求按照 query  的频度排序.

/*
3.有 10  个文件,每个文件 1G,
每个文件的每一行都存放的是用户的 query,每个文件的 query 都可能重复。
要求按照 query  的频度排序.

典型的TOP K算法,解决方案如下: 

方案1: 顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件(记为)中。
这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。 
找一台内存在2G左右的机器,依次对用hash_map(query, query_count)来统计每个query出现的次数。
利用快速/堆/归并排序按照出现次数进行排序。
将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件(记为)。
对这10个文件进行归并排序(内排序与外排序相结合)。
  
方案2: 一般query的总量是有限的,只是重复的次数比较多而已,可能对于所有的query,
一次性就可以加入到内存了。这样,我们就可以采用trie树/hash_map等直接来统计每个query出现的次数,
然后按出现次数做快速/堆/归并排序就可以了。
  
方案3: 与方案1类似,但在做完hash,分成多个文件后,可以交给多个文件来处理,
采用分布式的架构来处理(比如MapReduce),
最后再进行合并。
*/

抱歉!评论已关闭.