Лучший параллелизм для перестановки элементов в списке - PullRequest
Новая
       11

Лучший параллелизм для перестановки элементов в списке

0 голосов
/ 04 апреля 2020

Я пытаюсь создать функцию, которая может работать параллельно, которая вычисляет перестановку элементов списка в словаре и возвращает их в словаре. Я пробовал с многопроцессорным пулом, но по какой-то причине он еще медленнее Интересно, есть ли способ реализовать мою функцию, используя dask.

Параллельно работает функция, которую я пытаюсь запустить: 

import time
def Joinx(numList):
    '''Convert  numbers of  a list to a only one number
       [1,2,3]=> 123'''
    s = ''.join(map(str, numList))
    return s
def permute(a, l, r,lco):
    if l==r:          
        b=a[:]
        lco[Joinx(a[1:])]=a[:]
    else: 
        for i in range(l,r+1): 
            if i!=l:
                a[0]=(-1)*int(a[0])#Sign for permutation
            a[l], a[i] = a[i], a[l] 
            permute(a, l+1, r,lco)             
            a[l], a[i] = a[i], a[l]                         
            if i!=l:#Sign for permutation
                a[0]=(-1)*int(a[0])

def permutations(dictx):
    dict_out={}
    for key in dictx:
        element=dictx[key]
        n = len(element)
        permute(element, 1, n-1,dict_out) 
    return dict_out

Это тест для моей функции: 

test_dic={'a':[-1, 'h', 'g', 'f', 'e'],'b':[1, 'p', 'q', 'r', 's'],'c':[1, 'a', 'u', 'c', 't']}
starttime = time.time()
print(permutations(test_dic))  
print('That took {} seconds'.format(time.time() - starttime))

вывод такой: 

{'hgfe': [-1, 'h', 'g', 'f', 'e'], 'hgef': [1, 'h', 'g', 'e', 'f'], 'hfge': [1, 'h', 'f', 'g', 'e'], 'hfeg': [-1, 'h', 'f', 'e', 'g'], 'hefg': [1, 'h', 'e', 'f', 'g'], 'hegf': [-1, 'h', 'e', 'g', 'f'], 'ghfe': [1, 'g', 'h', 'f', 'e'], 'ghef': [-1, 'g', 'h', 'e', 'f'], 'gfhe': [-1, 'g', 'f', 'h', 'e'], 'gfeh': [1, 'g', 'f', 'e', 'h'], 'gefh': [-1, 'g', 'e', 'f', 'h'], 'gehf': [1, 'g', 'e', 'h', 'f'], 'fghe': [1, 'f', 'g', 'h', 'e'], 'fgeh': [-1, 'f', 'g', 'e', 'h'], 'fhge': [-1, 'f', 'h', 'g', 'e'], 'fheg': [1, 'f', 'h', 'e', 'g'], 'fehg': [-1, 'f', 'e', 'h', 'g'], 'fegh': [1, 'f', 'e', 'g', 'h'], 'egfh': [1, 'e', 'g', 'f', 'h'], 'eghf': [-1, 'e', 'g', 'h', 'f'], 'efgh': [-1, 'e', 'f', 'g', 'h'], 'efhg': [1, 'e', 'f', 'h', 'g'], 'ehfg': [-1, 'e', 'h', 'f', 'g'], 'ehgf': [1, 'e', 'h', 'g', 'f'], 'pqrs': [1, 'p', 'q', 'r', 's'], 'pqsr': [-1, 'p', 'q', 's', 'r'], 'prqs': [-1, 'p', 'r', 'q', 's'], 'prsq': [1, 'p', 'r', 's', 'q'], 'psrq': [-1, 'p', 's', 'r', 'q'], 'psqr': [1, 'p', 's', 'q', 'r'], 'qprs': [-1, 'q', 'p', 'r', 's'], 'qpsr': [1, 'q', 'p', 's', 'r'], 'qrps': [1, 'q', 'r', 'p', 's'], 'qrsp': [-1, 'q', 'r', 's', 'p'], 'qsrp': [1, 'q', 's', 'r', 'p'], 'qspr': [-1, 'q', 's', 'p', 'r'], 'rqps': [-1, 'r', 'q', 'p', 's'], 'rqsp': [1, 'r', 'q', 's', 'p'], 'rpqs': [1, 'r', 'p', 'q', 's'], 'rpsq': [-1, 'r', 'p', 's', 'q'], 'rspq': [1, 'r', 's', 'p', 'q'], 'rsqp': [-1, 'r', 's', 'q', 'p'], 'sqrp': [-1, 's', 'q', 'r', 'p'], 'sqpr': [1, 's', 'q', 'p', 'r'], 'srqp': [1, 's', 'r', 'q', 'p'], 'srpq': [-1, 's', 'r', 'p', 'q'], 'sprq': [1, 's', 'p', 'r', 'q'], 'spqr': [-1, 's', 'p', 'q', 'r'], 'auct': [1, 'a', 'u', 'c', 't'], 'autc': [-1, 'a', 'u', 't', 'c'], 'acut': [-1, 'a', 'c', 'u', 't'], 'actu': [1, 'a', 'c', 't', 'u'], 'atcu': [-1, 'a', 't', 'c', 'u'], 'atuc': [1, 'a', 't', 'u', 'c'], 'uact': [-1, 'u', 'a', 'c', 't'], 'uatc': [1, 'u', 'a', 't', 'c'], 'ucat': [1, 'u', 'c', 'a', 't'], 'ucta': [-1, 'u', 'c', 't', 'a'], 'utca': [1, 'u', 't', 'c', 'a'], 'utac': [-1, 'u', 't', 'a', 'c'], 'cuat': [-1, 'c', 'u', 'a', 't'], 'cuta': [1, 'c', 'u', 't', 'a'], 'caut': [1, 'c', 'a', 'u', 't'], 'catu': [-1, 'c', 'a', 't', 'u'], 'ctau': [1, 'c', 't', 'a', 'u'], 'ctua': [-1, 'c', 't', 'u', 'a'], 'tuca': [-1, 't', 'u', 'c', 'a'], 'tuac': [1, 't', 'u', 'a', 'c'], 'tcua': [1, 't', 'c', 'u', 'a'], 'tcau': [-1, 't', 'c', 'a', 'u'], 'tacu': [1, 't', 'a', 'c', 'u'], 'tauc': [-1, 't', 'a', 'u', 'c']}
That took 0.0007135868072509766 seconds

Мой словарь для может быть очень большим. Пример с набором larget будет: 

    Dic_Dd= {10169012: [  1, 3001016, 3009012,1002,1005,1006,2003,
  2004,2015], 20169012: [ -1, 3002016, 3009012,1001,1005,1006,2003,
  2004,2015], 10159012: [ -1, 3001015, 3009012,1002,1005,1006,2003,
  2004,2016], 20159012: [  1, 3002015, 3009012,1001,1005,1006,2003,
  2004,2016], 10162009: [ -1, 3001016, 3002009,1005,1006,1012,2003,
  2004,2015], 10092016: [  1, 3001009, 3002016,1005,1006,1012,2003,
  2004,2015], 10152009: [  1, 3001015, 3002009,1005,1006,1012,2003,
  2004,2016], 10092015: [ -1, 3001009, 3002015,1005,1006,1012,2003,
  2004,2016], 101620159012: [ -1, 3001016, 3002015, 3009012,1005,1006,2003,
  2004], 101520169012: [  1, 3001015, 3002016, 3009012,1005,1006,2003,
  2004], 10093012: [ -1, 3001009, 3003012,1002,1005,1006,2004,
  2015,2016], 10094012: [  1, 3001009, 3004012,1002,1005,1006,2003,
  2015,2016], 20093012: [  1, 3002009, 3003012,1001,1005,1006,2004,
  2015,2016], 20094012: [ -1, 3002009, 3004012,1001,1005,1006,2003,
  2015,2016], 10163005: [ -1, 3001016, 3003005,1002,1006,1012,2004,
  2009,2015], 10163006: [  1, 3001016, 3003006,1002,1005,1012,2004,
  2009,2015], 10164005: [  1, 3001016, 3004005,1002,1006,1012,2003,
  2009,2015], 10164006: [ -1, 3001016, 3004006,1002,1005,1012,2003,
  2009,2015], 10165015: [  1, 3001016, 3005015,1002,1006,1012,2003,
  2004,2009], 10166015: [ -1, 3001016, 3006015,1002,1005,1012,2003,
  2004,2009], 20163005: [  1, 3002016, 3003005,1001,1006,1012,2004,
  2009,2015], 20163006: [ -1, 3002016, 3003006,1001,1005,1012,2004,
  2009,2015], 20164005: [ -1, 3002016, 3004005,1001,1006,1012,2003,
  2009,2015], 20164006: [  1, 3002016, 3004006,1001,1005,1012,2003,
  2009,2015], 20165015: [ -1, 3002016, 3005015,1001,1006,1012,2003,
  2004,2009], 20166015: [  1, 3002016, 3006015,1001,1005,1012,2003,
  2004,2009], 10153005: [  1, 3001015, 3003005,1002,1006,1012,2004,
  2009,2016], 20153005: [ -1, 3002015, 3003005,1001,1006,1012,2004,
  2009,2016], 10153006: [ -1, 3001015, 3003006,1002,1005,1012,2004,
  2009,2016], 20153006: [  1, 3002015, 3003006,1001,1005,1012,2004,
  2009,2016], 10154005: [ -1, 3001015, 3004005,1002,1006,1012,2003,
  2009,2016], 10154006: [  1, 3001015, 3004006,1002,1005,1012,2003,
  2009,2016], 10155016: [ -1, 3001015, 3005016,1002,1006,1012,2003,
  2004,2009], 10156016: [  1, 3001015, 3006016,1002,1005,1012,2003,
  2004,2009], 20154005: [  1, 3002015, 3004005,1001,1006,1012,2003,
  2009,2016], 20154006: [ -1, 3002015, 3004006,1001,1005,1012,2003,
  2009,2016], 20155016: [  1, 3002015, 3005016,1001,1006,1012,2003,
  2004,2009], 20156016: [ -1, 3002015, 3006016,1001,1005,1012,2003,
  2004,2009], 101620153005: [  1, 3001016, 3002015, 3003005,1006,1012,2004,
  2009], 101620153006: [ -1, 3001016, 3002015, 3003006,1005,1012,2004,
  2009], 101620154005: [ -1, 3001016, 3002015, 3004005,1006,1012,2003,
  2009], 101620154006: [  1, 3001016, 3002015, 3004006,1005,1012,2003,
  2009], 101630054006: [ -1, 3001016, 3003005, 3004006,1002,1012,2009,
  2015], 101630056015: [ -1, 3001016, 3003005, 3006015,1002,1012,2004,
  2009], 101630064005: [  1, 3001016, 3003006, 3004005,1002,1012,2009,
  2015], 101630065015: [  1, 3001016, 3003006, 3005015,1002,1012,2004,
  2009], 101640056015: [  1, 3001016, 3004005, 3006015,1002,1012,2003,
  2009], 101640065015: [ -1, 3001016, 3004006, 3005015,1002,1012,2003,
  2009], 101520163005: [ -1, 3001015, 3002016, 3003005,1006,1012,2004,
  2009], 101520163006: [  1, 3001015, 3002016, 3003006,1005,1012,2004,
  2009], 101520164005: [  1, 3001015, 3002016, 3004005,1006,1012,2003,
  2009], 101520164006: [ -1, 3001015, 3002016, 3004006,1005,1012,2003,
  2009], 201630054006: [  1, 3002016, 3003005, 3004006,1001,1012,2009,
  2015], 201630056015: [  1, 3002016, 3003005, 3006015,1001,1012,2004,
  2009], 201630064005: [ -1, 3002016, 3003006, 3004005,1001,1012,2009,
  2015], 201630065015: [ -1, 3002016, 3003006, 3005015,1001,1012,2004,
  2009], 201640056015: [ -1, 3002016, 3004005, 3006015,1001,1012,2003,
  2009], 201640065015: [  1, 3002016, 3004006, 3005015,1001,1012,2003,
  2009], 101530054006: [  1, 3001015, 3003005, 3004006,1002,1012,2009,
  2016], 101530056016: [  1, 3001015, 3003005, 3006016,1002,1012,2004,
  2009], 201530054006: [ -1, 3002015, 3003005, 3004006,1001,1012,2009,
  2016], 201530056016: [ -1, 3002015, 3003005, 3006016,1001,1012,2004,
  2009], 101530064005: [ -1, 3001015, 3003006, 3004005,1002,1012,2009,
  2016], 101530065016: [ -1, 3001015, 3003006, 3005016,1002,1012,2004,
  2009], 201530064005: [  1, 3002015, 3003006, 3004005,1001,1012,2009,
  2016], 201530065016: [  1, 3002015, 3003006, 3005016,1001,1012,2004,
  2009], 101540056016: [ -1, 3001015, 3004005, 3006016,1002,1012,2003,
  2009], 101540065016: [  1, 3001015, 3004006, 3005016,1002,1012,2003,
  2009], 201540056016: [  1, 3002015, 3004005, 3006016,1001,1012,2003,
  2009], 201540065016: [ -1, 3002015, 3004006, 3005016,1001,1012,2003,
  2009], 1016201530054006: [  1, 3001016, 3002015, 3003005, 3004006,1012,2009], 1016201530064005: [ -1, 3001016, 3002015, 3003006, 3004005,1012,2009], 1015201630054006: [ -1, 3001015, 3002016, 3003005, 3004006,1012,2009], 1015201630064005: [  1, 3001015, 3002016, 3003006, 3004005,1012,2009], 30125016: [  1, 3003012, 3005016,1001,1002,1006,2004,
  2009,2015], 30126016: [ -1, 3003012, 3006016,1001,1002,1005,2004,
  2009,2015], 30125015: [ -1, 3003012, 3005015,1001,1002,1006,2004,
  2009,2016], 30126015: [  1, 3003012, 3006015,1001,1002,1005,2004,
  2009,2016], 30124005: [ -1, 3003012, 3004005,1001,1002,1006,2009,
  2015,2016], 30124006: [  1, 3003012, 3004006,1001,1002,1005,2009,
  2015,2016], 40125016: [ -1, 3004012, 3005016,1001,1002,1006,2003,
  2009,2015], 40126016: [  1, 3004012, 3006016,1001,1002,1005,2003,
  2009,2015], 40125015: [  1, 3004012, 3005015,1001,1002,1006,2003,
  2009,2016], 40126015: [ -1, 3004012, 3006015,1001,1002,1005,2003,
  2009,2016], 30054012: [  1, 3003005, 3004012,1001,1002,1006,2009,
  2015,2016], 30064012: [ -1, 3003006, 3004012,1001,1002,1005,2009,
  2015,2016], 301250166015: [ -1, 3003012, 3005016, 3006015,1001,1002,2004,
  2009], 301240065016: [ -1, 3003012, 3004006, 3005016,1001,1002,2009,
  2015], 301250156016: [  1, 3003012, 3005015, 3006016,1001,1002,2004,
  2009], 301240056016: [  1, 3003012, 3004005, 3006016,1001,1002,2009,
  2015], 301240065015: [  1, 3003012, 3004006, 3005015,1001,1002,2009,
  2016], 301240056015: [ -1, 3003012, 3004005, 3006015,1001,1002,2009,
  2016], 401250166015: [  1, 3004012, 3005016, 3006015,1001,1002,2003,
  2009], 300640125016: [  1, 3003006, 3004012, 3005016,1001,1002,2009,
  2015], 401250156016: [ -1, 3004012, 3005015, 3006016,1001,1002,2003,
  2009], 300540126016: [ -1, 3003005, 3004012, 3006016,1001,1002,2009,
  2015], 300640125015: [ -1, 3003006, 3004012, 3005015,1001,1002,2009,
  2016], 300540126015: [  1, 3003005, 3004012, 3006015,1001,1002,2009,
  2016]}

Ответы [ 2 ]

1 голос
/ 04 апреля 2020

Вам нужно будет рассмотреть конфигурацию вашей системы; нет «лучшего параллелизма», как подсказывает ваш заголовок. Сколько у вас процессоров? Это исправлено, или параметр вашего алгоритма? Какая память доступна для каждого?

Для большинства таких простых приложений «наилучшим» способом обычно является простое распределение задач в равной степени между процессорами. Если у вас есть миллион таких задач и четыре процессора, разбейте свою структуру на кварталы и создайте отдельный процесс для лишних кварталов, выполняя одну четверть в родительском потоке.

0 голосов
/ 07 апреля 2020

Это две мои разные реализации с dask: 

import time
import dask
def Joinx(numList):
    '''Convert  numbers of  a list to a only one number
       [1,2,3]=> 123'''
    s = ''.join(map(str, numList))
    return s

def permute(a, l, r,lco):
    if l==r:          
        b=a[:]
        lco[Joinx(a[1:])]=a[:]

    else: 
        for i in range(l,r+1): 
            if i!=l:
                a[0]=(-1)*int(a[0])#Sign for permutation
            a[l], a[i] = a[i], a[l] 
            permute(a, l+1, r,lco)            
            a[l], a[i] = a[i], a[l]                         
            if i!=l:#Sign for permutation
                a[0]=(-1)*int(a[0])


def permutations(element):
    dict_out={}
    n = len(element)
    permute(element, 1, n-1,dict_out)
    return dict_out

def comp(dics):
    lst=[]   
    for elem in dics:
        per=dask.delayed(permutations)(dics[elem])
        lst.append(per)
    return dask.compute(*lst)

test_dic={'a':[-1, 'h', 'g', 'f', 'e'],'b':[1, 'p', 'q', 'r', 's'],'c':[1, 'a', 'u', 'c', 't']}
from dask.distributed import Client, progress
client = Client()
starttime = time.time()
dfl=comp(test_dic)
print(dfl)  
print('That took {} seconds'.format(time.time() - starttime))

Время: 0,023533344268798828 секунд 

from dask.delayed import delayed
def Joinx(numList):
    '''Convert  numbers of  a list to a only one number
       [1,2,3]=> 123'''
    s = ''.join(map(str, numList))
    return s

def permute(a, l, r,lco):
    if l==r:          
        b=a[:]
        lco[Joinx(a[1:])]=a[:]
    else: 
        for i in range(l,r+1): 
            if i!=l:
                a[0]=(-1)*int(a[0])#Sign for permutation
            a[l], a[i] = a[i], a[l] 
            permute(a, l+1, r,lco)             
            a[l], a[i] = a[i], a[l]                         
            if i!=l:#Sign for permutation
                a[0]=(-1)*int(a[0])
@delayed
def permutations(dictx):
    dict_out={}#dask.delayed({})
    for key in dictx:
        element=dictx[key]
        n = len(element)
        permute(element, 1, n-1,dict_out) 
    return dict_out
client = Client()
test_dic={'a':[-1, 'h', 'g', 'f', 'e'],'b':[1, 'p', 'q', 'r', 's'],'c':[1, 'a', 'u', 'c', 't']}
from dask.distributed import Client, progress
starttime = time.time()
print(dask.compute(permutations(test_dic)))  
print('That took {} seconds'.format(time.time() - starttime))

Время: 0,01705622673034668 секунд

Когда словарь большой, эти реализации быстрее по сравнению с не параллельной реализацией

...