海量数据处理(一)

本文参考了July的教你如何迅速秒杀掉：99%的海量数据处理面试题和quicktest的Python处理海量数据的实战研究。写这篇文章意义是：1）记录自己的经验；2）对大量小文件数据的排序使用了“先Hash，后堆排序”的策略。对小文件先Hash，后堆排列的代码来自July提供的网址，做了微小修改，加了自己的理解。

场景：海量日志数据，提取出某日访问百度次数最多的K个IP

想法：

1.hash映射：顺序读取10个文件，按照hash(ip)%10的结果将数据写入到另外10个文件中。
2. hash统计：依次对小文件用hash_map(ip, ip_count)来统计每个ip出现的次数。
3.堆/快速/归并排序：利用快速/堆/归并排序按照出现次数进行排序，将排序好的ip和对应的ip_cout输出到文件中，这样得到了10个排好序的文件。最后，对这10个文件进行归并排序（内排序与外排序相结合）

实践：

0. 模拟海量数据分布式存储

0.1生成海量数据

from time import ctimeimport osimport heapqtempdir  = "e:\\temp"destfile = "e:\\sorted.txt"def decorated_file(f):    """ Yields an easily sortable tuple.     """    # 迭代函数，避免将数据一次读入内存    for line in f:        count, ip = line.split('\t',2)               yield (-int(count), ip)def mergefiles():    fs = []    if not os.path.exists(tempdir):        return    for f in range(0,10):        #已排序文件tmp_i,txt列表        fs.append(open(tempdir +"\\tmp_"+str(f)+".txt", 'r+'))    f_dest = open(destfile,"w")#存放最终排好序的结果    lines_written = 0    #调用堆排序算法 merge(*iterables)    for line in heapq.merge(*[decorated_file(f) for f in fs]):        f_dest.write(line[1])        lines_written += 1    return lines_writtenif __name__ == '__main__':    print("Start At: " + str(ctime()))    print("sorting completed, total queries: ", mergefiles())    print("End At: " + str(ctime()))

最终的结果ip按重复次数的从高到低保留在sorted.txt中。

总结：分布式数据，hash映射，hash统计，外\堆排序是处理海量数据的一把利器，有机会可以在Hadoop上实现reducer和mapper的过程。