基于内存共享的并行排序算法慢谈（下）

2010Freeze

基于内存共享的并行排序算法慢谈（下）

<div id="cnblogs_post_body">题目再现：请用Python多线程对一个4G以上的文件, 进行外排序，尽量优化性能。假设系统内核数为8，Mem=512MB，关键字是字符串
6.实验
6.1python多线程
关于python多线程可以参考：http://www.cnblogs.com/holbrook/archive/2012/03/02/2376940.html
python的多线程机制和Java很像，这里就不多讲了。似乎没有涉及到共享变量，锁也不用了。
6.2问题解决思路

　　我也想过先划分数据再交给线程，但是没试过，感觉需要很多内存，搞不好还会浪费。
　　第三个非常恶劣的问题就是，线程里面新建线程会产生很多问题，具体我说不清楚。
　　第四个问题就是，pdb调试无法在线程里面 设置断点，线程的问题无法跟踪，可能是我太蠢了。
由于以上问题，我最好只能换了一种方法，就是用前面提到的算法间并行。
开始时主线程读取数据，每读到一定量时就开辟一个新的线程，把线程插入到一个队列里。
主线程把读到的数据块交给线程排序。线程启动，线程排完序后会将结果输出到文件。
主线程每次读新数据的时候，先判断下是否还有足够内存开瓶新的数据。若没有则等待线程队里的第一个线程结束。
因为第一个线程是最先开辟的，它结束后就可以释放内存了。
当主线程读完所有数据时，等待线程队列里的所有线程结束。
然后主线程使用归并思想对子文件数据进行归并，并输出到最终文件。
在归并的时候，若内存有多，尽量预取数据。
6.3完整代码
<div class="cnblogs_code" >产生待排序数据<div id="cnblogs_code_open_44de23ee-5f51-41b7-ad4b-8ef8fb0b32e9" class="cnblogs_code_hide"> 1 import random 2 3 def generatekey(num): 4     str = [] 5     while num > 0: 6         str.append(chr(random.randint(97, 122))) 7         num = num - 1 8     str.append('\n') 9     return ''.join(str)10 11 print 'please enter the number'12 N = input()13 f=open('unsortdata','w')14 while N > 0:15     str = generatekey(30)16     f.write(str)17     N = N - 118     19 f.close()