开发者社区> 问答> 正文

有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重

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

展开
收起
问问小秘 2020-01-06 16:42:42 937 0
1 条回答
写回答
取消 提交回答
  • 还是典型的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),最后再进行合并。

    2020-01-06 16:43:00
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
数据采集:日志数...[jing.luojing].1477375627.pdf 立即下载
PostgresChina2018_赖思超_PostgreSQL10_hash索引的WAL日志修改版final 立即下载
低代码开发师(初级)实战教程 立即下载