0

I am trying to make quick sort concurrent by using threading. But when i run the code with my threading approach, it only runs the same thread for all the partitions recursively.

Here is what I have tried. 

from threading import Thread
import threading
import time
import thread

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
    if (left < j):
        thread = Thread(target = qsort(sets,left,j))
        name =  threading.current_thread() 
        printp(sets,elements,name)
    if (i < right):
        thread1 = Thread(target=qsort(sets,i,right))
        name =  threading.current_thread()
        printp(sets,elements,name)
    return sets
Muhammad Tahir
  • 5,006
  • 1
  • 19
  • 36
yudhveer singh
  • 29
  • 1
  • 7
  • 3
    First, you don't start any of the created threads. Second (which, actually, should have been first), in Python multithreading won't give you any performance gain due to the infamous [GIL](https://wiki.python.org/moin/GlobalInterpreterLock). – bereal Apr 13 '16 at 10:44
  • i used thread.start() as well. No success. – yudhveer singh Apr 13 '16 at 10:56
  • and back to your reason of no use of multi threading in python due to GIL. I really don't care about that because i have a practical in 5 days and the problem statement is concurrent quick sort. – yudhveer singh Apr 13 '16 at 10:58
  • so instead of multithread, should i use multiproceesing? – yudhveer singh Apr 13 '16 at 11:00
  • Well, first you could of course make it work with threads, though without seeing how you start the threads and wait for them to complete it's hard to suggest anything. – bereal Apr 13 '16 at 11:05

2 Answers2

2

(besides the issues @bereal pointed out in the comment under the question) The root cause to the problem that you saw (they all ran in the same thread) is that you misused the second argument "target" of class Thread, which should be a callable object.

Below is the fixed code:

from threading import Thread
import threading
import time
import thread

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


'''testing below'''
ls = [1,3,6,9,1,2,3,8,6]
res = qsort(ls, 0, len(ls) - 1)
print(res)

Output:

thead <_MainThread(MainThread, started 49900)> is sorting [1, 3, 6, 9, 1, 2, 3,8]
thead <Thread(Thread-1, started 38136)> is sorting [3, 6, 9, 1, 2, 3, 8]
thead <Thread(Thread-2, started 42024)> is sorting [6, 9, 3, 2, 3, 8]
thead <Thread(Thread-3, started 36344)> is sorting [9, 3, 6, 3, 8]
thead <Thread(Thread-4, started 47684)> is sorting [6, 3]
thead <Thread(Thread-5, started 27760)> is sorting [6, 8]
[1, 1, 2, 3, 3, 6, 6, 8, 9]
Lei Shi
  • 757
  • 4
  • 8
  • Ah, right, he is calling the function... but besides that, sequence `thread.start(); thread.join()` eliminates the concurrency completely, since it will first wait for the 'left' thread, then start and wait for the 'right' thread instead of spawning them both. – bereal Apr 13 '16 at 11:13
  • before sorting 11 4 8 2 6 1 7 <_MainThread(MainThread, started 139722684020544)> 1 2 8 4 6 11 7 <_MainThread(MainThread, started 139722684020544)> 1 2 4 6 8 11 7 <_MainThread(MainThread, started 139722684020544)> 1 2 4 6 7 8 11 <_MainThread(MainThread, started 139722684020544)> 1 2 4 6 7 8 11 <_MainThread(MainThread, started 139722684020544)> 1 2 4 6 7 8 11 after sorting 1 2 4 6 7 8 11 – yudhveer singh Apr 13 '16 at 11:24
  • @yudhveersingh, the observation you got (based on my above code) is because your code for dump thread name is also incorrect. let me update my code (again) – Lei Shi Apr 13 '16 at 11:31
2

There is no reel parallel execution with threads in Python. Use Pool or Processs. fork is still possible. Alex

Alexsg69
  • 15
  • 1
  • 1
    Dear Bonoit, Do you know what is GIL in python ? Please read the many ressources like https://stackoverflow.com/questions/17130975/python-vs-cpython This is not because you can create thredas that you do reel parallelism in Python. TTHER IS NO REEL PARALLEL EXECUTION OF THREADS in Python. See also https://hackernoon.com/concurrent-programming-in-python-is-not-what-you-think-it-is-b6439c3f3e6a – Alexsg69 Feb 10 '19 at 17:36
  • 1
    Another Comment for Benoit. Let's write each one (you and me) a quick-sort Python prog, you with your threads and me with my Processes (mine is read and I teach it !). The less rapid one will send a sugar candy to the other one ! OK ? – Alexsg69 Feb 10 '19 at 18:00
  • Ok, I surrender. But it seams to be linked to the Cpython implementation and not the language itself so it mostly depends on his setup (ok, I will admit that I am only looking for a pretext here). I did some tests in the past with a thread pool, and I noticed some improvements, but they were only there because of a `time.sleep` in the module I was using (waiting for the appearance of a file), so it won't help here. I have since deleted my comment and thank you for the resource you sent, (maybe put them directly it the answer next time, for the next stupid guy like me). – Benoît P Feb 10 '19 at 21:07