page contents

如何按照query的频度排序?

轩辕小不懂 发布于 2021-10-08 11:15
阅读 449
收藏 0
分类:Golang

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

2097
Nen
Nen
- 程序员

分析解答:对于这种题,如果query的重复度比较大,那么可以考虑一次性把所有query读入到内存中处理,如果query的重复率不高,那么可用的内存不足以容纳所有的query,那么就需要使用分治法或者其他的方法来解决。

方法一:map法如果query的重复率比较高,说明不同的query总数比较小,可以考虑把所有的query都加载到内存中的map中(由于map中针对每个不同的query只保存一个键值对,因此这些query占用的空间会远小于10G,有希望把它们一次性都加载到内存中)。接着就可以对map按照query出现的次数进行排序。

方法二:分治法这种方法需要根据数据量的大小以及可用内存的大小来确定问题划分的规模。对于本题而言,可以顺序遍历10个文件中的query,通过Hash函数hash(query)%10把这些query划分到10个文件中,通过这样的划分,每个文件的大小为1G左右,当然可以根据实际情况来调整Hash函数,如果可用内存很小,可以把这些query划分到更多的小的文件中。

如果划分后的文件还是比较大,可以使用相同的方法继续划分,直到每个文件都可以被读取到内存中进行处理为止,然后对每个划分后的小文件使用hash_map统计每个query出现的次数,然后根据出现次数排序,并把排序好的query以及出现次数写入到另外一个单独的文件中。这样针对每个文件,都可以得到一个按照query出现次数排序的文件。

接着对所有的文件按照query的出现次数进行排序,这里可以使用归并排序(由于无法把所有的query都读入到内存中,因此这里需要使用外排序)。

请先 登录 后评论