Python 2.7でどのように並列マージソート？

Question

私は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]) 

ありがとうございます。

Answer 1

この場合、おそらくスレッドもマルチプロセッシングも、必然的に高速化するとは言えません。

CPythonでは、グローバルインタプリタロック（ "GIL"）は、一度に1つのスレッドのみがPythonバイトコードを実行していることを確認します。これは、メモリ管理を容易にするために行われます。ソートされるデータがメモリ上にあると仮定すると、一度に1つのスレッドしか実際に処理していないため、スレッドはこれをより速くしません。

データにmultiprocessing.Arrayのような共有メモリを使用していない限り、マルチプロセッシングでデータをピクル処理して子プロセスに送信する必要があります。そして、子プロセスも同じことをして、それを送り返します。データセットが大きいほど、オーバーヘッドが多くなります。 Arrayでは、ロックを使用してアクセスをシリアライズします。 これは良いことですが、遅くなる可能性があります。ロックを使用しないRawArrayを使用できますが、データの変更には非常に注意する必要があります。

私が考えることができる最善のアプローチは次のとおりです。この場合、ソート可能なデータはmultiprocessing.sharedctypes.RawArrayが受け入れるデータに限定されます。次の2つのmultiprocessing.sharedctypes.RawArrayインスタンスを作成

• 、AおよびB配列Aがソートされていないデータを含む、あなたのCPUは、N個のコアを有している場合、均等Bに寸法決めされ、アレイBが（0
• に設定されたすべての値を有しますN個のワーカーを持つmultiprocessing.Poolを作成します（これがデフォルトです）。次に、配列のインデックスをN個の連続した部分で分割するタプルのシーケンスを作成します。シーケンスは((0,3), (4,7), (8,11), (12,15))となります。次に、指定されたシーケンスでPool.mapメソッドを呼び出します。各ワーカーは、共有配列のどの部分を扱うかを示すタプルを受け取ります。
• 各ワーカーは、担当リストの一部を読み取り、ソートしてソートしたデータをBリストの同じ部分に書き込みます。
• 最後に、親プロセスは、B配列の4つの部分を正しい順序で配置します。