9.9如何按照query的频度排序.py

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


"""
解决思路:
方法一:hash_map法:
如果query的重复度比较大,那么可以考虑一次性把所有query读入到内存中处理,如果query的重复率不高,那么可用的内存不足以容纳所有的query,
那么就需要使用分治法或其他的方法来解决.

方法二:分治法:
这种方法需要根据数据量的大小以及可用内存的大小来确定问题划分的规模.对于本题而言,可以顺序遍历10个文件中的query,通过hash函数
hash(query)%10把这些query划分到10个文件中,通过这样的划分,每个文件的大小为1GB左右,当然可以根据实际情况来调整hash函数,如果可用
内存很小,那么这些query划分到更多的小文件中.
如果划分后的文件还是比较大,那么可以使用相同的方法继续划分,直到每个文件都可以被读取到内存中进行处理为止,然后对每个划分后的小文件
使用hash_map统计每个query出现的次数,然后根据出现次数进行排序,并把排序号的query以及出现次数写入到另外一个单独的文件中.这样针对
每个文件,都可以得到一个按照query出现次数排序的文件.
接着,对所有文件按照query的出现次数进行排序,这里可以使用归并排序(由于无法全部读入内存,因此需要使用外排序.)
"""