Created
November 21, 2013 03:20
-
-
Save icsaas/7575603 to your computer and use it in GitHub Desktop.
simplest python k-way merging sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import heapq | |
import random | |
import threading | |
#k thrads | |
k=4 | |
#Generate n numbers for each thread to process. | |
n=10 | |
def GenerateNumbers(a,b): | |
numbers=[] | |
for i in xrange(n): | |
numbers.append(random.randint(a,b)) | |
return numbers | |
class SortingThread(threading.Thread): | |
def __init__(self): | |
super(SortingThread,self).__init__() | |
self.numbers=GenerateNumbers(1,100) | |
def run(self): | |
self.numbers.sort() | |
if __name__=='__main__': | |
#Parallel sort with multiple threads | |
# | |
sortingThreads=[] | |
for i in xrange(k): | |
sortingThreads.append(SortingThread()) | |
for i in xrange(k): | |
sortingThreads[i].start() | |
for i in xrange(k): | |
sortingThreads[i].join() | |
print i,sortingThrads[i].numbers | |
#use heap to output the final sorted list. | |
#We fill the heap with serval numbers firstly | |
# | |
theHeap=[] | |
for i in xrange(1): | |
for t in xrange(len(sortingThreads)): | |
number=sortingThreads[t].numbers[i] | |
heapq.heappush(theHeap,number) | |
sortedNumbers=[] | |
#In the while loop,people may replace the code by reading file routeings. | |
#Since IO is always the bottleneck,so single thread should be enough | |
p=1 | |
while (len(theHeap)>0): | |
if p<len(sortingThreads[t].numbers): | |
for t in xrange(len(sortingThreads)): | |
number=sortingThreads[t].numbers[p] | |
heapq.heappush(theHeap,number) | |
p+=1 | |
sortedNumbers.append(heappop(theHeap)) | |
#Done | |
print sortedNumbers |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment