Как использовать многопоточность с разделяй и властвуй? - PullRequest
Новая
       9

Как использовать многопоточность с разделяй и властвуй?

0 голосов
/ 11 ноября 2018

Я новичок в Python и пытаюсь использовать многопоточность.Уже существует подробный комментарий к Stackoverflow по этой теме, но у меня все еще есть некоторые вопросы.

Цель моей программы - создать и заполнить массив (хотя я предполагаю, чтотехнически его нужно было бы назвать «списком» в Python) и отсортировать его по алгоритму «разделяй и властвуй».К сожалению, термины «список» и «массив» кажутся многим пользователем смешанными, даже если они не совпадают.Если в моем комментарии используется «массив», имейте в виду, что я разместил различный код на разных ресурсах и ради уважения первоначального автора (ов) не изменил его содержание.

Мой коддля заполнения списка count было довольно просто 

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

После этого я использовал это очень удобное руководство по теме «разделяй и властвуй», чтобы создать два списка для сортировки, которыебыли объединены позже.Моя главная задача сейчас состоит в том, чтобы правильно использовать эти списки с многопоточностью.

В ранее упомянутом посте утверждалось, что, в принципе, для использования многопоточности требовалось всего несколько строк кода:

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

Я не знаю причину моей проблемы.

Любая помощь очень ценится!

1 Ответ

0 голосов
/ 11 ноября 2018

Я точно не знаю, что не так с вашим кодом, но вот полный рабочий пример многопоточной версии кода mergeSort, который вы связали с : 

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]

К сожалению, кажется, что это немного медленнее, чем однопоточная версия. Тем не менее, этот тип замедления составляет par для курса , когда речь идет о многопоточности задач, связанных с вычислениями в Python.

...