python 2.7如何並行合併排序？

我試過並行合併排序在Python 2.7中，但我不能這樣做。因爲我不知道是否應該使用線程或多處理來實現。請在此線程或多處理代碼中寫入並行代碼：python 2.7如何並行合併排序？

def merge(left, right): 
result = [] 
i ,j = 0, 0 
while i < len(left) and j < len(right): 
    print('left[i]: {} right[j]: {}'.format(left[i],right[j])) 
    if left[i] <= right[j]: 
     print('Appending {} to the result'.format(left[i]))   
     result.append(left[i]) 
     print('result now is {}'.format(result)) 
     i += 1 
     print('i now is {}'.format(i)) 
    else: 
     print('Appending {} to the result'.format(right[j])) 
     result.append(right[j]) 
     print('result now is {}'.format(result)) 
     j += 1 
     print('j now is {}'.format(j)) 
print('One of the list is exhausted. Adding the rest of one of the lists.') 
result += left[i:] 
result += right[j:] 
print('result now is {}'.format(result)) 
return result 

def mergesort(L): 
print('---') 
print('mergesort on {}'.format(L)) 
if len(L) < 2: 
    print('length is 1: returning the list withouth changing') 
    return L 
middle = len(L)/2 
print('calling mergesort on {}'.format(L[:middle])) 
left = mergesort(L[:middle]) 
print('calling mergesort on {}'.format(L[middle:])) 
right = mergesort(L[middle:]) 
print('Merging left: {} and right: {}'.format(left,right)) 
out = merge(left, right) 
print('exiting mergesort on {}'.format(L)) 
print('#---') 
return out 

mergesort([6,5,4,3,2,1])

謝謝。

來源

2016-11-26 Mahdi

你知道這段代碼沒有運行，對不對？要麼你從任何地方複製和粘貼它，要麼你搞砸了格式 – byxor

「請在線程中編寫並行代碼或對這些代碼進行多處理」這是一個命令嗎？ – TigerhawkT3

@ TigerhawkT3我正想問同樣的問題:) – mutantkeyboard

在這種情況下，我會說可能既不是線程也不是多處理必然會加快速度。

在CPython中，全局解釋器鎖（「GIL」）確保一次只有一個線程正在執行Python字節碼。這是爲了使內存管理更容易，除此之外。因此，假設要排序的數據在內存中，線程不會更快，因爲一次只有一個線程正在處理它。

除非您爲數據使用共享內存（如multiprocessing.Array），否則多處理需要醃製數據並將其發送給子進程以供它們使用。並且子進程也會將其發回。數據集越大，這導致的開銷就越多。 Array使用鎖定序列化訪問。 這是一件好事，但它可以減慢你的速度。您可以使用不使用鎖定的RawArray，但您必須非常小心地修改數據。

我能想到的最佳方法如下。在這種情況下，您可以排序的數據僅限於multiprocessing.sharedctypes.RawArray接受的任何數據。

創建兩個multiprocessing.sharedctypes.RawArray的情況下，A和B的陣列A包含未排序的數據，陣列B（這是同樣尺寸以B具有設置爲0。
如果CPU具有N個核的所有值，你創建一個帶有N個worker的multiprocessing.Pool（這是默認的），然後你創建一個元組序列，它將數組的索引分成N個連續的部分，假設你有一個16個數值的數組，並且N = 4，那麼序列將是((0,3), (4,7), (8,11), (12,15))然後你可以調用給定序列的Pool.map方法，然後每個工作人員接收一個元組，指示它應該使用哪個共享陣列的一部分
每個工作人員讀取它負責的列表部分，對數據進行排序並將排序後的數據寫入B列表的相同部分。
最後，父進程以正確的順序放置B數組的四個部分。

來源

2016-11-27 00:36:51

python 2.7如何並行合併排序？

回答

相關問題