snippetpythonMinor
Parallel quicksort algorithm taking way too long
Viewed 0 times
waylongtooquicksortalgorithmparalleltaking
Problem
Below is a Python implementation of the quicksort algorithm using parallelism. It takes about 1 second per every 10 items in the list, which is hilariously unacceptable. Why is it so slow?
EDIT
Thanks for the responses. As it turns out, switching to Threads and limiting the number of them I was spawning sped things up. However, my linear version of the algorithm still performed better.
from multiprocessing import *
def quicksort(lyst, connection=None):
if len(lyst) > 1:
pivot = lyst.pop(len(lyst)-1)
wall = 0
for i in range(len(lyst)):
if lyst[i] <= pivot:
lyst[wall], lyst[i] = lyst[i], lyst[wall]
wall += 1
receiveLeft, sendLeft = Pipe()
receiveRight, sendRight = Pipe()
Process(target=quicksort, args=(lyst[:wall], sendLeft)).start()
Process(target=quicksort, args=(lyst[wall:], sendRight)).start()
lyst = receiveLeft.recv() + [pivot] + receiveRight.recv()
if connection:
connection.send(lyst)
connection.close()
return lyst
if __name__ == '__main__':
quicksort([8,4,6,9,1,3,10,2,7,5])EDIT
Thanks for the responses. As it turns out, switching to Threads and limiting the number of them I was spawning sped things up. However, my linear version of the algorithm still performed better.
Solution
The problem seems to be the fact that you are not dealing with threads (as you should), but rather entire processes (which is more computationally demanding). Refer to this page for details on how to spawn threads.
Also, as a side node, it makes no sense to keep spawning new threads over and over again, since spawning a thread can take easily a couple of milliseconds, which would obliterate all performance gain. Instead, ask the user to pass the maximum amount of threads allowed, and do not spawn any more than that. Furthermore, it would be reasonable to cancel spawning a new thread in case the range to sort it receives is too small.
Hope that helps.
Also, as a side node, it makes no sense to keep spawning new threads over and over again, since spawning a thread can take easily a couple of milliseconds, which would obliterate all performance gain. Instead, ask the user to pass the maximum amount of threads allowed, and do not spawn any more than that. Furthermore, it would be reasonable to cancel spawning a new thread in case the range to sort it receives is too small.
Hope that helps.
Context
StackExchange Code Review Q#141078, answer score: 2
Revisions (0)
No revisions yet.