Elaborei o seguinte código serial para realizar a ordenação Odd-even sort, que primeiro vai ordenando os índices par/ímpar e depois ímpar/par.
import time
def oddevenSort(x):
sorted = False
while not sorted:
sorted = True
#ordena indices par/impar
for i in range(0, len(x)-1, 2):
if x[i] > x[i+1]:
x[i], x[i+1] = x[i+1], x[i]
sorted = False
#ordena indices impar/par
for i in range(1, len(x)-1, 2):
if x[i] > x[i+1]:
x[i], x[i+1] = x[i+1], x[i]
sorted = False
print(x)
return x
tic = time.time()
oddevenSort([4,3,2,1,3,6,9,1,2,3,54,76,98,12,333,331,33,1,7,9])
toc = time.time()
print("tempo gasto para processar = " + str(toc-tic)+"s")
Agora eu preciso criar para este mesmo algoritmo de ordenação um código paralelo em python para poder calcular o speedup (ganho de tempo entre executar o código serial VS código paralelo).
A primeira abordagem que eu estava tendo era criar uma thread para a ordenação par/ímpar e outra para a ordenação ímpar/par, mas não consigo entender como vai ser o comportamento deste código. Na minha visão esse algoritmo deve executar toda a parte par/ímpar e depois em SEQUÊNCIA a parte ímpar/par. Assim, eu teria que sincronizar a thread 1 e a thread 2, impedindo de o código ocorrer em paralelo.
Exemplo thread 1 (par/ímpar):
for i in range(0, len(x)-1, 2):
if x[i] > x[i+1]:
x[i], x[i+1] = x[i+1], x[i]
sorted = False
Exemplo thread 2 (ímpar/par):
for i in range(1, len(x)-1, 2):
if x[i] > x[i+1]:
x[i], x[i+1] = x[i+1], x[i]
sorted = False
A segunda abordagem seria paralelizar a ordenação PAR/ÍMPAR (tipo thread 1 pega a primeira metade dos números e ordena enquanto a thread 2 pega a segunda metade e ordena). A mesma coisa para a parte ÍMPAR/PAR (thread 3 ordena metade e a thread 4 ordena a outra metade).
Exemplo:
Vetor completo: (9,8,7,6,5,4,3,2,1,0)
Thread 1 ordena: 9,8,7,6,5
Thread 2 ordena: 4,3,2,1,0
Resultado esperado thread 1: 5,6,7,8,9
Resultado esperado thread 2: 0,1,2,3,4
Resultado esperado da ordenação final: 0,1,2,3,4,5,6,7,8,9
Abordagem 3? Sugestões? Caso não haja outra forma mais eficiente, gostaria de ajuda para implementar uma das duas sugestões.