QuickSort com thread [RESOLVIDO]

henriquechanry28
(usa elementary OS)

Enviado em 02/12/2016 - 20:34h

Olá pessoal estou fazendo um quicksort em python com thread so que ele esta entrando em loop infinito podem me ajudar, aqui vai o código:

[code]:

from threading import Thread
import threading
import time
import thread
import random

def qsort(sets,left,right):

i = left
j = right
pivot = sets[(left + right)/2]
temp = 0
while(i <= j):
while(pivot > sets[i]):
i = i+1
while(pivot < sets[j]):
j = j-1
if(i <= j):
temp = sets[i]
sets[i] = sets[j]
sets[j] = temp
i = i + 1
j = j - 1

lthread = None
rthread = None

if (left < j):
lthread = Thread(target = lambda: qsort(sets,left,j))
lthread.start()

if (i < right):
rthread = Thread(target=lambda: qsort(sets,i,right))
rthread.start()

if lthread is not None: lthread.join()
if rthread is not None: rthread.join()
return sets

def vetrandom():
lista = []

for i in range(99999):
n = random.randint(1,99999)
lista.append(n)

return lista

def main():
vetale = []
vetord = []

vetale = vetrandom()

vetord = qsort(vetale, 0, len(vetale) - 1)

print vetord

if __name__ == "__main__":
main()

[code]:

Obrigado, desculpa de não foi identado , parece que a caixinha não deixa

ctw6av
(usa Nenhuma)

Enviado em 02/12/2016 - 21:22h

Coloque o código no pastebin e manda o link ou aqui mesmo só que entre

[code]código aqui[//code] 

Com uma barra só, tive que colocar duas porquê o site iria entender como outro código.



______________________________________________________________________
OS: Biebian
Kernel: x86_64 3.5.2-amd64
Resolution: 1320x768
CPU: Intel Core i3-4005U CPU @ 1.7GHz
RAM: 3852MiB
Distro: http://biebian.sourceforge.net/

henriquechanry28
(usa elementary OS)

Enviado em 02/12/2016 - 23:12h

from threading import Thread

import threading

import time

import thread

import random



def qsort(sets,left,right):



    print("thead {0} is sorting {1}".format(threading.current_thread(), sets[left:right]))



    i = left

    j = right

    pivot = sets[(left + right)/2]

    temp = 0

    while(i <= j):

         while(pivot > sets[i]):

             i = i+1

         while(pivot < sets[j]):

             j = j-1

         if(i <= j):

             temp = sets[i]     

             sets[i] = sets[j]

             sets[j] = temp

             i = i + 1

             j = j - 1



    lthread = None

    rthread = None



    if (left < j):

        lthread = Thread(target = lambda: qsort(sets,left,j))

        lthread.start()



    if (i < right):

        rthread = Thread(target=lambda: qsort(sets,i,right))

        rthread.start()



    if lthread is not None: lthread.join()

    if rthread is not None: rthread.join()

    return sets



def vetrandom():

     lista = []

     

     for i in range(99999):

        n = random.randint(1,99999)

        lista.append(n)  



     return lista                



def main():

    vetale = []

    vetord = []



    vetale = vetrandom()

    

    vetord = qsort(vetale, 0, len(vetale) - 1)



    print vetord



if __name__ == "__main__":

    main()            

 

ctw6av
(usa Nenhuma)

Enviado em 03/12/2016 - 09:44h

* O módulo Thread não é necessário já que você importou o threading logo em seguida.
* O módulo time não está senso usado.
* Esta linha abaixo, gera um erro já que o valor posicional da lista devem ser inteiros e dessa forma a operação abaixo retorna um valor do tipo float.

pivot = sets[(left + right) / 2] 

Adicionado duas barras "//" ela retorna um inteiro e resolve o problema.
* Alguns parênteses não são necessários
* A função lambda não é necessária
* O loop infinito, na verdade, não é loop infinito. Ele se dá pelo tamanho da lista passada com 99999 valores, processar todos demanda tempo e dependendo do pc pode demorar um bom tempo. Tente com um valor menor e verá.

OBS: Não alterei a parte lógica, foram apenas pequenos erros e de nada afetaram na parte lógica.

Depois de checar esses pontos o código ficou assim:

#!/usr/bin/env python3



from random import randint

import threading





def qsort(sets, left, right):

    print("thread {} is sorting {}".format(threading.current_thread(), sets[left:right]))



    i = left

    j = right

    pivot = sets[(left + right) // 2]

    temp = 0

    while i <= j:

        while pivot > sets[i]:

            i += 1

        while pivot < sets[j]:

            j -= 1

        if i <= j:

            temp = sets[i]

            sets[i] = sets[j]

            sets[j] = temp

            i += 1

            j -= 1



    lthread = None

    rthread = None



    if left < j:

        lthread = threading.Thread(target=qsort, args=(sets, left, j))

        lthread.start()



    if i < right:

        rthread = threading.Thread(target=qsort, args=(sets, i, right))

        rthread.start()



    if lthread is not None:

        lthread.join()

    if rthread is not None:

        rthread.join()

    return sets





def vetrandom():

    lista = []

    for i in range(100):

        n = randint(1, 100)

        lista.append(n)

    return lista





def main():

    vetale = vetrandom()

    vetord = qsort(vetale, 0, len(vetale) - 1)

    print(vetord)

    # print(set(vetord)) # Remove os valores repetidos da lista





if __name__ == "__main__":

    main() 

______________________________________________________________________
OS: Biebian
Kernel: x86_64 3.5.2-amd64
Resolution: 1320x768
CPU: Intel Core i3-4005U CPU @ 1.7GHz
RAM: 3852MiB
Distro: http://biebian.sourceforge.net/

henriquechanry28
(usa elementary OS)

Enviado em 03/12/2016 - 19:25h

Funcionou perfeitamente muito obrigado, mais uma pergunta, pq que com 99999 ele demora tanto e parece que esta em loop infinito

ctw6av
(usa Nenhuma)

Enviado em 03/12/2016 - 19:32h

São muitos valores e isso gera mais consumo de memória e processamento, imagine uma lista com 99999 posições e depois percorrer essa lista pelo menos duas vezes esse valor para ordenar as posições e seu processador sendo requerido por 99999 threads de uma vez. E muita coisa, não?




______________________________________________________________________
OS: Biebian
Kernel: x86_64 3.5.2-amd64
Resolution: 1320x768
CPU: Intel Core i3-4005U CPU @ 1.7GHz
RAM: 3852MiB
Distro: http://biebian.sourceforge.net/