algorithm - Python中的并行Quicksort

Question

我想在python中实现并行快速排序。
我知道quicksort，你必须选择一个pivot，partition，但是如何在python中将它们作为独立的任务派生出来呢？
这是它的伪代码：

QS(A[1:n])
if n=1 then return A[1]
pivot <--any value from A (random)
L <- A[A[:] < pivot]
R <- A[A[:] > pivot]
A(L) <- spawn QS(L)
A(R) <- QS(R)
sync
return A(L) ++ A(R)

Answer 1

你可以这么做，但不太可能加速你的代码您可以使用ThreadPoolExecutor创建线程并从中获取结果下面是一个简单的示例，其中包含一个对数组求和的函数：

from concurrent.futures import ThreadPoolExecutor
pool = ThreadPoolExecutor(max_workers=1)
def add(arr):
    if len(arr)<2:
        return sum(arr)  #cheating a little
    mid = len(arr)//2
    f = pool.submit(add,arr[:mid])
    y = add(arr[mid:])
    return y+f.result()

submit()将函数名作为第一个参数，然后将函数的参数作为第一个参数。所以对于您的代码来说，它将类似于 f = pool.submit(QS,L)。
请记住，虽然python支持并发性，但不支持使用线程的并行性。看看他们的区别所以上面的代码实际上是在单线程中运行的现在可以使用 ProcessPoolExecutor来实现进程并行性，python很好地支持这种并行性。但数据IO中的开销可能会耗尽从进程并行性中获得的任何速度。