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

谢谢。

你知道这段代码没有运行，对不对？要么你从任何地方复制和粘贴它，要么你搞砸了格式 – 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数组的四个部分。

python 2.7如何并行合并排序？

相关推荐