Python中的并行基数排序

wnavrhmk  于 2023-03-11  发布在  Python
关注(0)|答案(1)|浏览(124)

我正在学习python并行编程,我得到了这样的代码

import multiprocessing
import random
import time

def merge_buckets(final_bucket,bucket):
    helper=0
    for i in bucket:
        for j in i:
            final_bucket[helper].append(j)
        helper += 1
    return final_bucket
def radix_sort(array,start,end,digit,helper,result_queue):
        bucket = [[] for _ in range(10)]
        #cisklus ktory prechadza polom cisel a rozdelujem ich do bucketov
        for k in range(start,end):

            num = array[k]
            print(num)
            string_number = str(num)
            if(num < digit):
                bucket[0].append(num)
            else:
                #print((max_digits-helper),"=",num)
                bucket[int(str(num)[len(str(num))-helper])].append(num)
        result_queue.put(bucket)
        #reset pola cisel do ktoreho sa znovu vyhodia novo usporiadane cisla z bucketu
        #musi byt dakde ale ne tu dakde v dajakom inom proces
        #navysenie pocitadiel

if __name__ == '__main__':
    cores = int(input("Cores : "))
    array = [random.randint(0, 100) for _ in range(1000)]
    lock = multiprocessing.Lock()
    #arr = multiprocessing.Array('i',[3, 5, 1, 18, 25, 4, 17, 22, 31, 6, 89, 92, 7], lock=lock)
    #bucket = multiprocessing.Array ('i',[[] for _ in range(10)],lock=lock)
    manager = multiprocessing.Manager()
    arr = manager.list([3, 5, 1, 18, 25, 4, 17, 22, 31, 6, 89, 92, 7])

    # vybere maximalnu hodnotu z pola
    max_val = max(array)
    print("Maximum of numbers: ", max_val)
    # digit znamena ze ci polom prechadzame ze 1 , 10 , 100 ako ide radix zoraduje od poslednej cislice
    digit = 1


    num = len(array)//cores

    zvysok = len(array)%cores

    parts = []
    for i in range(cores):
        if(zvysok != 0):
            parts.append(num + 1)
            zvysok -= 1
        else:
            parts.append(num)

    result_queue = multiprocessing.Queue()
    start = time.time()
    helper = 1
    while(max_val // digit > 0):
        print(array[:20])
        results = []
        result_queue = multiprocessing.Queue()
        processes = []
        j = 0
        bucket = [[] for _ in range(10)]
        for o in parts:
            p = multiprocessing.Process(target=radix_sort, args=(array,j,j+o,digit,helper,result_queue))
            p.start()
            processes.append(p)
            j += o

        for p in processes:
            p.join()

        results = []
        for _ in range(len(parts)):
            results.append(result_queue.get())
        for result in results:
            bucket = merge_buckets(bucket,result)
        array = []
        for i in bucket:
            for j in i:
                array.append(j)
        for p in processes:
            p.terminate()

        digit *= 10
        helper = helper + 1
    end = time.time()
    #array = radix_sort(array)
    print(array)
    print("Cas : ", end - start)

我想问你我该怎么做现在你可以看到我为数字中的每个位置制作线程,比如如果有2个数字,我设置8个核心程序,程序会制作16个。如果有3个数字,我会制作24个。所以我知道在多处理中有一些同步工具,但我不知道如何将它们应用到基数排序中。有人想不出如何做到这一点的方法。我会很高兴的。

tcbh2hod

tcbh2hod1#

我不知道Python的多线程是如何工作的,但是对于多线程基数排序,您只需要启动并等待每个线程完成。
多线程基数排序的典型实现首先执行单线程初始最高有效位传递,以将数据拆分为存储桶,例如基数256创建256个存储桶。如果创建足够多的存储桶,以便平均存储桶大小适合线程的本地缓存(通常是每个内核的L1和L2缓存),则会有所帮助。
假设一个处理器有效地支持K个线程。为了获得最佳效率,使用K个线程的线程池。要实现线程池,需要类似于Windows Wait For Multiple Objects的内容:
https://learn.microsoft.com/en-us/windows/win32/api/synchapi/nf-synchapi-waitformultipleobjects
Linux本身并不支持这个功能,但是有第三方库实现了它的等价物,我不知道Python。
K个线程中的每一个都开始对一个桶进行排序。一旦任何一个线程完成,该线程就被用来对下一个未排序的桶进行排序。一旦所有的桶都被排序,线程就被关闭,桶被连接起来形成一个排序数组。
更简单且可能更快的替代方案是将数组拆分为K个部分,并行执行K个基数排序,然后使用并行合并来合并排序后的子数组。例如,如果K = 8,则在基数排序完成后,4个线程将8个子数组合并为4个,2个线程将4个子数组合并为2个。然后单个线程执行2个子阵列到1个子阵列的最终合并。

相关问题