如何使用分而治之的多线程？

Question

我是 Python 的新手，一直在尝试使用多线程。已经有关于该主题的深入 comment on Whosebug，但我还有一些问题。

我的程序的目标是创建和填充一个数组（尽管我猜从技术上讲它必须在 Python 中称为 "list"）并按 [= 排序46=]算法。不幸的是，术语 "list" 和 "array" 似乎被许多用户混淆了，即使它们并不相同。如果在我的评论中使用 "array"，请记住我从各种资源中发布了不同的代码，并且为了尊重原始 author/s，没有更改其内容。

我填充列表的代码 count 非常简单

#!/usr/bin/env python3
count = []
i = 149
while i >= 0:
    count.append(i)
    print(i)
    i -= 1

之后我在"divide and conquer"的话题上用this very handy guide创建了两个排序列表，后来合并了。我现在主要关心的是如何通过多线程正确使用这些列表。

在 earlier mentioned post 中有人认为，基本上，使用多线程只需要几行代码：

from multiprocessing.dummy import Pool as ThreadPool 
pool = ThreadPool(4)

以及

results = pool.starmap(function, zip(list_a, list_b))

传递多个列表。

我尝试修改代码但失败了。我的函数的参数是def merge(count, l, m, r)（用来把列表count分成左右两部分）临时创建的两个列表分别叫L和R。

def merge(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r- m 

    # create temp arrays 
    L = [0] * (n1) 
    R = [0] * (n2)

但每次我运行程序，它只是响应以下错误消息：

Traceback (most recent call last):
  File "./DaCcountdownTEST.py", line 71, in <module>
    results = pool.starmap(merge,zip(L,R))
NameError: name 'L' is not defined

我不知道问题的原因。

非常感谢任何帮助！

Answer 1

我不确定你的代码到底出了什么问题，但这里有一个完整的多线程版本的工作示例 the mergeSort code you linked to:

from multiprocessing.dummy import Pool as ThreadPool 

# Merges two subarrays of arr[]. 
# First subarray is arr[l..m] 
# Second subarray is arr[m+1..r] 
def merge(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r- m 

    # create temp arrays 
    L = [0] * (n1) 
    R = [0] * (n2) 

    # Copy data to temp arrays L[] and R[] 
    for i in range(0 , n1): 
        L[i] = arr[l + i] 

    for j in range(0 , n2): 
        R[j] = arr[m + 1 + j] 

    # Merge the temp arrays back into arr[l..r] 
    i = 0     # Initial index of first subarray 
    j = 0     # Initial index of second subarray 
    k = l     # Initial index of merged subarray 

    while i < n1 and j < n2 : 
        if L[i] <= R[j]: 
            arr[k] = L[i] 
            i += 1
        else: 
            arr[k] = R[j] 
            j += 1
        k += 1

    # Copy the remaining elements of L[], if there 
    # are any 
    while i < n1: 
        arr[k] = L[i] 
        i += 1
        k += 1

    # Copy the remaining elements of R[], if there 
    # are any 
    while j < n2: 
        arr[k] = R[j] 
        j += 1
        k += 1

# l is for left index and r is right index of the 
# sub-array of arr to be sorted 
def mergeSort(arr,l=0,r=None):
    if r is None:
        r = len(arr) - 1

    if l < r: 
        # Same as (l+r)/2, but avoids overflow for 
        # large l and h 
        m = (l+(r-1))//2

        # Sort first and second halves
        pool = ThreadPool(2)
        pool.starmap(mergeSort, zip((arr, arr), (l, m+1), (m, r)))
        pool.close()
        pool.join()

        merge(arr, l, m, r)

下面是代码的简短测试：

arr = np.random.randint(0,100,10)
print(arr)
mergeSort(arr)
print(arr)

产生以下输出：

[93 56 55 60  0 28 17 77 84  2]
[ 0  2 17 28 55 56 60 77 84 93]

遗憾的是，它似乎确实比单线程版本慢了很多。但是，当涉及 Python 中的多线程计算密集型任务时，这种减速是 par for the course。

如何使用分而治之的多线程？

How to use multithreading with divide and conquer?

python

multithreading

python-multithreading

python-3.x